cd

Един бедняк имал p котки и c кучета, които влачел със себе си от място на място. Веднъж стигнали до една дълбока река, която и най-храброто куче не смеело да преплува. На брега имало малка лодка,  която за съжаление събирала само k животни. Налагало се реката да се прекосява няколко пъти, докато всички животни се окажат от другата страна. Задачата не е толкова проста, защото, ако част от животните останат без наблюдение и броят на кучетата е по-голям от броя на котките, това може да се окаже фатално за котките.

Задача

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

Вход

Входният файл cd.in съдържа три положителни цели числа, разделени с интервал, p c k, означаващи съответно, брой котки, брой кучета и капацитет на лодката.

Изход

Изходният файл cd.out трябва да съдържа един ред, на който е записан търсеният минимален брой преминавания на реката.

Ограничения и пояснения

 

Пример

 

cd.in

cd.out

Обяснение

5 7 3

9

Възможно решение с минимален брой преминавания на реката:

1) от бряг 1 на бряг 2 с 3 кучета  (на брега остават 4 кучета и 5 котки)
2) обратно на бряг 1 с празна лодка
3) от бряг 1 на бряг 2 с две котки и едно куче (на бряг 1 остават 3 котки и 3 кучета)
4) от бряг 2 на бряг 1, заедно с 2 кучета
5) от бряг 1 на бряг 2 с 3 котки  (на бряг 1 има 5 кучета)
6) обратно на бряг 1 с празна лодка
7) от бряг 1 на бряг 2 с 3 кучета (на бряг 1 остават 2 кучета)
8) обратно на бряг 1 с празна лодка
9) от бряг 1 на бряг 2 с 2 кучета

Време за работа на програмата:  0.4 секунди на тест

prof. Emanuela Cerchez
"Grigore Moisil" Iaşi IT High School
Contact:emanuela.
cerchez@gmail.com

 

Превод на български: Стоян Капралов