Кидання камінців по воді
Як член Міжнародної Ліги Метання Камінців, ви щотижня подорожуєте до різних озер, щоб змагатися у конкурсі з метання камінців. Мета полягає в тому, щоб кинути камінь так, щоб він підстрибнув якомога більше разів; точні правила для визначення переможця наведені нижче. Щоб зробити змагання цікавими, МЛМК часто обирає озера з колодами, піщаними мілинами та іншими перешкодами. Вам надається бічний вигляд, "карта" рівня води в озері, як показано у верхньому рядку прикладу нижче. (Числа 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, і є найкращим можливим кидком для цього озера.