Masala #0822

Xotira 20 MB Vaqt 1000 ms

Aniq hajm

Tasavvur qiling siz ko'l oldida turibsiz. Oldingizda \(M\) va \(N\) litrli idishlar bor shu idishlardan foydalanib eng optimal usulda (eng kam amal bajargan holda) \(K\) litr suv olishingiz kerak.
Bunda quyidagicha amallar bajarish mumkin:

Ixtiyoriy idishga ko'ldan to'ldirib suv olish mumkin. (Faqat to'ldirib!)
Bir idishdan ikkinchi idishga birinchi idish bo'shaguncha yoki ikkinchi idish to'lguncha suv quyish mumkin.
Idishdagi suvni ko'lga quyib bo'shatish mumkin.(Idishni to'la bo'shatish shart!)
Bularning har biri bir amal hisoblanadi.
Bir vaqtda bir idishga suv to'ldirib, ikkinchi idishni bo'shatish mumkin emas!

Kiruvchi ma'lumotlar:

Bir satrda uchta natural son \(M,N,K(1\le M,N,K \le 10^9\ va\ K<max(M,N) )\) kiritiladi.

Chiquvchi ma'lumotlar:

\(K\) litr suv olish jarayonidagi har bir amaldan keyin alohida satrlarda idishlardagi suvlar miqdorini \("m \ n"\) shaklida chop etib boring. Amallar to \("K\ 0"\) yoki \("0\ K"\) natijaga erishilguncha davom etadi. Kerakli natijaga erishilgach, keyingi satrda nechta amal bajarganingizni chop eting. (Yechim eng optimali bo'lsin!)

Misollar

#	input.txt	output.txt
1	7 3 5	0 0 7 0 4 3 4 0 1 3 1 0 0 1 7 1 5 3 5 0 9

Izoh:

Dastlab ikkala idish ham bo'sh bo'lib \(("0\ 0")\) ,bu holat har bir test boshida chiqarilishi kerak.
So'ralgan hajmdagi suvning olib bo'linishi kafolatlanadi.
Eng optimal yechim doimo yagona bo'ladi!