Перейти к содержимому

3

"Добро пожаловать в Code Jam" (Welcome to Code Jam) - задача C классификационного раунда 2009 года.

Задача

Итак, вы зарегистрированы. Мы послали вам сообщение, чтобы поприветствовать вас в Code Jam. Но возможно вы все еще не чувствуете себя причастным к Code Jam. Поэтому мы решили назвать задачу "Добро пожаловать в Code Jam". Надеемся, что после решения этой задачи вы наверняка почувствуете себя полноправным участником. По-настоящему поприветствованным участником Code Jam.

Если вы прочитали предыдущий параграф, возможно вы недоумеваете, к чему это он. Но если вы прочитаете его тщательно, вы сможете заметить, что мы написали слова "Добро пожаловать в Code Jam" ("Welcome to Code Jam" на английском, языке оригинала задачи, и число вхождений указано именно для этого языка - прим. перев.) несколько раз, 400263727 раз суммарно. В конце концов, легко пробежаться по предыдущему параграфу и отыскать букву 'w', затем отыскать буву 'e' далее по тексту, затем отыскать после этого букву 'l', и так далее. Ваша задача - написать программу, принимающую на вход любой текст и выводящую сколько именно раз этот текст содержит фразу "welcome to code jam".

Более точно, по данной строке текста, вы находите, сколько именно раз строка "welcome to code jam" входит как подпоследовательность в данную строку. Другими словами, найти последовательность s увеличивающихся индексов входной строки, такую, что конкатенация input[s[0]], input[s[1]], ..., input[s[18]] образует строку "welcome to code jam".

Результат вашего вычисления может быть огромным числом, поэтому, для удобства, мы требуем от вас найти только последние 4 цифры.
...читать далее "Добро пожаловать в Code Jam"