google code jam, задание C

[Farsh]

google code jam, задание C

Добрый вечер. Сейчас идет google code jam, я никак не могу врубиться в смысл одного задания. И так, вот оно:

So you've registered. We sent you a welcoming email, to welcome you to code jam. But it's possible that you still don't feel welcomed to code jam. That's why we decided to name a problem "welcome to code jam." After solving this problem, we hope that you'll feel very welcome. Very welcome, that is, to code jam.

If you read the previous paragraph, you're probably wondering why it's there. But if you read it very carefully, you might notice that we have written the words "welcome to code jam" several times: 400263727 times in total. After all, it's easy to look through the paragraph and find a 'w'; then find an 'e' later in the paragraph; then find an 'l' after that, and so on. Your task is to write a program that can take any text and print out how many times that text contains the phrase "welcome to code jam".

To be more precise, given a text string, you are to determine how many times the string "welcome to code jam" appears as a sub-sequence of that string. In other words, find a sequence s of increasing indices into the input string such that the concatenation of input[s[0]], input[s[1]], ..., input[s[18]] is the string "welcome to code jam".

The result of your calculation might be huge, so for convenience we would only like you to find the last 4 digits.

Я вообще не понимаю. По сути вначале просто говорится, что нужно найти число вхождений подстроки в строку ( но это не так ). Откуда тогда число 400263727 ? Ведомая фраза :

In other words, find a sequence s of increasing indices into the input string such that the concatenation of input[s[0]], input[s[1]], ..., input[s[18]] is the string "welcome to code jam".

Что в переводе есть что-то:

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

Может кто-нибудь объяснит, в чем суть то .. ? Спрашиваю, так как не могу закрыть это и забыть

-~{}~ 03.09.09 20:49:

А, ну и вот пример входящих строк и числа тех самый вхождений ( впереди дополнено нулям ):

elcomew elcome to code jam 0001
wweellccoommee to code qps jam 0256
welcome to codejam 0000

 

[zerkms]

Farsh
чо непонятного-то - число способов прочтения фразы "welcome to code jam" из всего параграфа.

wweellccoommee to code qps jam 0256

256 перестановок потому что:
w (первая), e (третья), l (пятая) ...
w (вторая), e (третья), l (пятая) ...

 

[Farsh]

zerkms
врубился, спасибо

 

[maxwell]

О, у нас на подготовке к IOI было такое-же