Сбор яблок
Автор задачи: Hal Burch, 2004
Первоисточник: USACO NOVEMBER 2004 QUALIFYING CONTEST
URL первоисточника: www.usaco.org
Задачу добавил: prosputko
Успешно сдано решений: 13
Известно, что коровы любят яблоки. На поле фермера Джона есть
две яблони (которые имеют номера 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 за последними двумя.