cd

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

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

Timp maxim de executie/test: 0.4 secunde

prof. Emanuela Cerchez
 Liceul de Informatica "Grigore Moisil" Iasi
 Contact:emanuela.cerchez@gmail.com