Internet Problem Solving Contest

IPSC 2017

Solution to Problem S – St. Ives

There is a catch in the original riddle. Read the first two lines again:

As I was approaching St. Ives, out came a man with seven wives, …

The man with his wives, sacks, and whatnot was not going to St. Ives at all – they were all leaving the town! Only you (i.e., the narrator) are going to St. Ives!

Thus, in the easy subproblem S1 the correct answer to any test case is 1. (You may have noted that we tried to disguise this by carefully chosing the example in the problem statement.)

Once you solved S1, you were informed that S2 is the problem you may have solved initially: count all objects that were leaving St. Ives. This is, obviously, 1 + a0 + a0a1 + ⋯ + a0a1an − 2.

The constraints are small, hence this value always fits into an ordinary 32-bit integer.