3 тур - з 18.11 по 24.11.2013

точка входу для відправлення розв'язків http://93.171.173.139/cgi-bin/new-client?contest_id=18

Задача 1. Мішень (20 балів)

Ім'я вхідного файлу: darts.dat

Ім'я вихідного файлу: darts.ans

Програма: darts.*

Ліміт часу: 1 секунда

Петрику на день народження подарували гру «Дартс». Він повісив її на стіну. Запросив до себе друзів. Вони прочитали правила гри. Гравці по черзі кидають по 3 дротики.

Для визначення черговості кожен гравець кидає по дротику. Той, хто влучив ближче до центру розпочинає гру (набрав більше очок). Якщо кількість набраних очок однакова то першим кидає гравець з меншим номером. Сума очок, для кожного з гравців, нараховується після трьох виконаних кидків.

Найпоширеніша гра - «501». Кожен гравець має на рахунку 501 очко. Метод ведення рахунку полягає у відніманні одержаної кількості очок з тих, що залишилися. Переможцем вважається той, хто отримав найменшу кількість очок, або першим зумів звести свій рахунок до нуля. Якщо ви набрали більшу кількість очок, ніж потрібно для нульового завершення гри, то всі три останні кидки не зараховуються, і рахунок залишається колишнім, яким він був до серії кидка.

Суворі правила складають інтригу гри в якій гравець, що відстає, завжди має шанс наздогнати суперника, який попереду. Ближче до кінця гра набуває стратегічного характеру. Щоб перемогти потрібно розраховувати очки на декілька кидків вперед, а при промаху знову продумувати план. Один з двох найбільш титулованих гравців Джон Лоу в 1984 році одержав найбільший приз в історії дартсу, 102 000 фунтів, за те, що завершив один лег всього за дев'ять кидків. Другий легендарний спортсмен, Ерік Брістоу, розробив математичну таблицю (Калькулятор Брістоу) що допомагає дартсмену прорахувати найбільш оптимальну (з погляду Брістоу) і швидку комбінацію закінчення гри 3-ма дротиками.

Вхідні дані

Кількість гравців N (2≤N≤1000), в наступних рядках задано очки набрані гравцями під час гри за правилами.Очки лежать в межах від 0 до 100.

Вихідні дані.

Номер гравця, який виграв.

Приклад

Задача 2. Скарб (100 балів)

Ім'я вхідного файлу: treasure.dat

Ім'я вихідного файлу: treasure.ans

Програма treasure .*

Ліміт часу: 2 секунди

Ще одна цікаву логічна гру подарували Петрику – пошук скарбу пірата Флінта. Потрібно пройти через лабіринт та знайти скарб.

Не завжди існує шлях до скарбу, але гравець може проходити крізь стіни. Проходити крізь стіни дозволено обмежену кількість разів, а скарб потрібно забрати як найшвидше.

Карта має форму квадрата, з NxN квадратних клітинок. В середині квадрата уздовж сторін клітин можуть бути розташовані стіни. В кожний момент часу гравець знаходитись в одній клітинці. За один хід гравець переміщується в сусідню по горизонталі чи по вертикалі клітинку. Гравець може проходити через стіну K разів. За межі карти виходити не можна.

Завдання. Написати програму, що знаходить найменшу кількість кроків, за яку гравець може забрати скарб з координатами (x, y). Гравець стартує в клітинці з координатами (1, 1).

Вхідні дані. Вхідний текстовий в першому рядку містить числа N, K, X, Y (2≤N≤200, 0≤K≤250, 1≤X,Y≤N). Наступні N-1 рядків містять по N цілих чисел, які задають горизонтальні лінії між клітинками. Наступні N рядків містять по N-1 цілих чисел, які задають вертикальні лінії між клітинками. 1 означає лінію, а 0 – її відсутність.

Вихідні дані. Єдиний рядок вихідного текстового містить знайдену мінімальну кількість кроків, або число –1, при відсутності шлях.

Приклад