Един бедняк имал p котки и c кучета, които влачел със себе си от място на място. Веднъж стигнали до една дълбока река, която и най-храброто куче не смеело да преплува. На брега имало малка лодка, която за съжаление събирала само k животни. Налагало се реката да се прекосява няколко пъти, докато всички животни се окажат от другата страна. Задачата не е толкова проста, защото, ако част от животните останат без наблюдение и броят на кучетата е по-голям от броя на котките, това може да се окаже фатално за котките.
Задача
Напишете програма, която определя минималния брой преминавания на реката, необходими за безопасното транспортиране на всички животни на другия бряг.
Вход
Входният файл cd.in съдържа три положителни цели числа, разделени с интервал, p c k, означаващи съответно, брой котки, брой кучета и капацитет на лодката.
Изход
Изходният файл cd.out трябва да съдържа един ред, на който е записан търсеният минимален брой преминавания на реката.
Ограничения и пояснения
Пример
cd.in |
cd.out |
Обяснение |
5 7 3 |
9 |
Възможно решение с минимален брой преминавания на реката: 1) от
бряг 1 на бряг 2
с 3 кучета (на
брега остават
4 кучета и 5
котки) |
Време
за работа на
програмата:
0.4 секунди на
тест
prof.
Emanuela Cerchez
"Grigore Moisil"
Iaşi IT High School
Contact:emanuela.cerchez@gmail.com