Masala #0822
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!
Bir satrda uchta natural son \(M,N,K(1\le M,N,K \le 10^9\ va\ K<max(M,N) )\) kiritiladi.
\(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!)
| # | 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 |
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!
Telegram kanalimizga obuna bo'ling