Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Сбор яблок

Автор задачи: Hal Burch, 2004

Первоисточник: USACO NOVEMBER 2004 QUALIFYING CONTEST

URL первоисточника: www.usaco.org

Задачу добавил: prosputko

Успешно сдано решений: 12

Известно, что коровы любят яблоки. На поле фермера Джона есть
две яблони (которые имеют номера 1 и 2), полные поспевших яблок.
Бесси не может достать яблоки, когда они висят на дереве, поэтому она должна
ждать их падения. Тогда Бесси может ловить в воздухе созревшие яблоки, 
пока они падают. (Известно, что никто не хочет есть битые яблоки). 
Бесси умеет быстро есть, так что съедает пойманное яблоко за несколько секунд.

Каждую минуту с одного из двух деревьев падает одно яблоко. Бесси,
имея большой опыт, может словить яблоко, если она стоит под
деревом, с которого яблоко падает. Хотя Бесси может быстро бегать между
двумя деревьями (это занимает не более минуты), она может оставаться под
одним деревом некоторое время. Более того, коровы не тренируются в беге, 
поэтому Бесси не будет бегать туда-сюда между деревьями постоянно 
(и потеряет некоторое количество яблок).

Яблоки падают (по одному в минуту) в течение T минут (1 <= T <= 1000).
Бесси курсирует туда и обратно не более W раз(1 <= W <= 30)
Известно, с какого конкретного дерева падает яблоко в определенную минуту.
Определить максимальное количество яблок, которое Бесси может словить.
Бесси стартует под деревом номер 1.

{БАЛЛЫ: 500}

{ЗАДАЧА NAME: bcatch}

ФОРМАТ ВВОДА:

* Строка 1: Два разделенных пробелом целых числа: T и W

* Строки 2..T+1: 1 или 2: Номер дерева, с которого падает яблоко в данную
                 минуту.

ПРИМЕР ВВОДА({file bcatch.in}):

7 2
2
1
1
2
2
1
1

ПОЯСНЕНИЕ ВВОДА:

Упало семь яблок - одно с дерева 2, затем два с дерева 1, затем 
два с дерева 2, затем два с дерева 1. Бесси может бегать от одного 
дерева к другому дважды.

ФОРМАТ ВЫВОДА:

* Строка 1: Максимальное количество яблок, которые Бесси может поймать, 
        перебегая между деревьями не более W раз.

ПРИМЕР ВЫВОДА ({file bcatch.out}):

6

ПОЯСНЕНИЕ ВЫВОДА :

Бесси может поймать шесть яблок: оставаясь под деревом 1, пока первые два
яблока с него упадут, затем перейдет к дереву 2 за следующими двумя,
затем вернется к дереву 1 за последними двумя.

Сдать задачу

Задать вопрос жюри по этой задаче