As a member of the International Rock-Skipping League, you travel to a different lake each week and compete in a rock-skipping contest. The goal is to throw a rock so that it skips as many times as possible; the exact rules for determining the winner are given below. To make the competitions interesting, the IRSL often chooses lakes with logs, sandbars, and other obstacles. You are provided with a side-view, water-level "map" of the lake as shown in the top line of the example below. (The numbers below the map are just for reference.) A period (".") indicates clear water, where a rock will skip; any other character indicates some kind of obstacle that will stop a rock.
...=...**..#...@....:.:.:..=.. ______________________________ 11111111112222222222 012345678901234567890123456789 \You stand at the left end of the lake. You can throw a rock so that it lands at any position in the lake, and then skips at any fixed interval thereafter. So a throw can be defined as a pair , where i \geq 0 is the initial landing position and d > 0 is the distance between skips. Note that must be positive. The count of a throw is the number of times that it skips on the water. The length is the position of its last contact with either the water or an obstacle. To rank two distinct throws, use the following criteria, in order, until a winner is determined: count (highest wins); length (greatest wins); initial position (greatest wins); distance between skips (smallest wins).
For the map shown above, throw hits the obstacle at position ; it has count and length . Throw skips at positions 16, 17, 18, and , then hits the obstacle at position ; it has count and length , so it beats throw . Throw skips at positions 2, 9, 16, and , then skips over the lake; it has count and length , so it beats throw . Throw skips at positions 1, 5, 9, 13, 17, 21, 25, and , then skips over the lake; it has count and length , and is the best possible throw for this lake.
Esempio 1