Un om sarman
avea p pisici si c
câini, pe care-i purta dupa el, din loc în loc. Într-o buna
azi a ajuns la un râu adânc si învolburat, pe care nici macar
cel mai viteaz câine nu l-ar fi trecut înot. Pe malul râului
omul nostru a gasit o barca, dar din nefericire în barca încapeau
cu el doar maxim k animale.
Asa ca omul nostru a hotarât sa traverseze râul de mai multe ori,
pâna când toate animalele ajung pe malul celalalt.
Problema nu este atât de simpla, pentru ca, datorita unor patanii legendare,
daca animalele ramân neînsotite pe mal, iar numarul câinilor
este strict mai mare decât numarul pisicilor, atunci câinii vor
ataca mortal pisicile.
Cerinta
Scrieti un program care
sa determine numarul minim de traversari pe care omul nostru trebuie sa le faca
pentru a transporta toate animalele tefere pe malul celalalt.
Date de intrare
Fisierul de intrare cd.in
contine o singura linie pe care se afla trei numere naturale separate prin câte
un spatiu p c k, cu semnificatia
din enunt.
Date de iesire
Fisierul de iesire cd.out
va contine o singura linie pe care va fi scris numarul minim de traversari necesare.
Restrictii si precizari
0 <= p, c < 256
1 <= k <= 100
Pentru datele de test
exista intotdeauna solutie.
Exemple
cd.in
cd.out
Explicatie
5 7 3
9
O solutie cu numar
minim de traversari poate fi:
traverseaza de pe
malul 1 pe malul 2
cu 3 câini (ramân 4 câini si 5
pisici pe malul 1)
traverseaza de pe malul 2
pe malul 1 cu barca goala
traverseaza de pe malul 1
pe malul 2 cu doua pisici
si un câine (pe malul 1 ramân 3 pisici
si 3 câini)
traverseaza de pe malul 2
pe malul 1 cu 2
caini
traverseaza de pe malul 1
pe malul 2 cu 3
pisici (pe malul 1 ramân 5 câini)
traverseaza de pe malul 2
pe malul 1
traverseaza de pe malul 1
pe malul 2 cu 3 câini (pe malul 1 ramân 2 câini)
traverseaza de pe malul 2
pe malul 1
traverseaza de pe malul 1
pe malul 2 cu 2 câini