Метание камней по воде
Как член Международной Лиги Камнепрыжков, вы каждую неделю отправляетесь к новому озеру, чтобы участвовать в соревнованиях по прыжкам камней. Цель — бросить камень так, чтобы он сделал как можно больше прыжков. Правила для определения победителя описаны ниже. Чтобы сделать соревнования более интересными, IRSL часто выбирает озера с бревнами, песчаными отмелями и другими препятствиями. Вам предоставляется вид сбоку, "карта" уровня воды в озере, как показано в верхней строке примера ниже. (Числа 0..29 под картой даны только для справки.) Точка (".") обозначает чистую воду, где камень может прыгать; любой другой символ указывает на препятствие, которое остановит камень.
...=...**..#...@....:.:.:..=.. ______________________________ 11111111112222222222 012345678901234567890123456789
Вы стоите на левом берегу озера. Вы можете бросить камень так, чтобы он приземлился в любой точке на озере и затем прыгал с любым фиксированным интервалом. Таким образом, бросок определяется парой (i, d), где i ≥ 0 — начальная позиция приземления, а d > 0 — расстояние между прыжками. Обратите внимание, что d должно быть положительным. Счет броска — это количество раз, когда он прыгает по воде. Длина — это позиция его последнего контакта с водой или препятствием. Чтобы сравнить два различных броска, используйте следующие критерии в порядке приоритета, пока не будет определен победитель: счет (выигрывает наибольший); длина (выигрывает наибольшая); начальная позиция (выигрывает наибольшая); расстояние между прыжками (выигрывает наименьшее).
Для карты, показанной выше, бросок (27, 2) попадает в препятствие на позиции 27; у него счет 0 и длина 27. Бросок (16, 1) прыгает на позициях 16, 17, 18 и 19, затем попадает в препятствие на позиции 20; у него счет 4 и длина 20, поэтому он побеждает бросок (27, 2). Бросок (2, 7) прыгает на позициях 2, 9, 16 и 23, затем перепрыгивает через озеро; у него счет 4 и длина 23, поэтому он побеждает бросок (16, 1). Бросок (1, 4) прыгает на позициях 1, 5, 9, 13, 17, 21, 25 и 29, затем перепрыгивает через озеро; у него счет 8 и длина 29, и это лучший возможный бросок для этого озера.