Pie kam ar mazāku lauzienu skaitu to izdarīt nav iespējams.
Aloizam ir taisnstūrveida šokolādes tāfelīte, kas sastāv no n“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!
Teksta faila shoko.in 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.
Teksta faila shoko.out vienīgajā rindā jāizvada vesels skaitlis - mazākais lauzienu skaits, kāds nepieciešams, lai summā iegūtu k gabaliņus šokolādes.
| shoko.in | shoko.out |
5 7 19 |
2 |