Nosaukums
Šokolādes tāfelīte (shoko)
Laika limits
1.00s
Atmiņas limits
256.0 MB
Grūtība
67%

Definīcija

Aloizam ir taisnstūrveida šokolādes tāfelīte, kas sastāv no n x m gabaliņiem. Tāfelīti drīkst lauzt tikai pa gabaliņus sadalošajām taisnajām līnijām (tādējādi no viena taisnstūra iegūstot divus). Protams, ka nepieciešamības gadījumā drīkst lauzt arī iepriekš iegūtos šokolādes gabalus. Aloizs vēlas iepriecināt savu draugu Olafu vārdadienā, uzcienājot to ar tieši k gabaliņiem šokolādes (var nebūt vienā gabalā).

Zīmējumā redzams piemērs, kā no tāfelītes 5*7 ar diviem lauzieniem iespējams iegūt 19 gabaliņus (3*5 + 1*4). Pie kam ar mazāku lauzienu skaitu to izdarīt nav iespējams.

Uzrakstiet programmu, kas dotiem šokolādes tāfelītes izmēriem un vajadzīgajam gabaliņu kopskaitam nosaka, kāds mazākais lauzienu skaits jāizdara, lai šo gabaliņu kopskaitu iegūtu!


Ievaddatu raksturojums

Ievaddatu vienīgajā rindā dotas trīs veselu skaitļu n (tāfelītes platums), m (tāfelītes garums) un k (vajadzīgais gabaliņu kopskaits) vērtības. Zināms, ka 0<n<=100; 0<m<=100; 0<k<=n*m. Starp katriem diviem blakus skaitļiem ir viens tukšumsimbols.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā jāizvada vesels skaitlis - mazākais lauzienu skaits, kāds nepieciešams, lai summā iegūtu k gabaliņus šokolādes.


Piezīmes

Uzdevums izmantots Latvijas 15.informātikas olimpiādes II(rajona) kārtā. 

Ideja - Baltkrievijas informātikas olimpiāde.


Paraugdati

Stdin
5 7 19
Stdout
2

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.