Masala #0822

Xotira 20 MB Vaqt 1000 ms Qiyinchiligi 60 %
14

  

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!

 

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin