PIIMA

Xotira 256 MB Vaqt 750 ms

14

Ali va Vali

Bir kuni Ali bilan Vali o'yin o'ynashmoqchi bo'lishibdi. O'yinda ularga $s$ binar satr beriladi. Dastlab, berilgan faqat 0 va 1 lardan iborat $s$ binar satri o'nlik sanoq sistemasiga o'tkaziladi, o'girilgan sonni $n$ deb olaylik. Ali va Vali bu $n$ soni ustida quyidagi amallarni o'yin tugagunicha bajarishadi:

Agar $n$ soni toq bo'lsa, Ali unga 1ni qo'shadi. n $\leftarrow$ n + 1

Agar $n$ soni juft bo'lsa, Vali uni 2ga bo'ladi. $n\leftarrow \frac{n}{2}$

O'yin $n$ soni 1ga teng bo'lgunicha davom etadi, ya'ni $n=1$ da o'yin tugaydi. Siz Ali va Valining har biri nechtadan amal bajaranligini toping. $s$ satrining dastlabki raqami 0dan farqli bo'lishi kafolatlanadi.

Kiruvchi ma'lumotlar:

Yagona qatorda $s$ binar satri beriladi. $1 \leq |s| \leq 10^6$

Chiquvchi ma'lumotlar:

Ali va Vali nechtadan amal bajarganligini chop eting. Birinchi Ali, keyin esa Vali.

Misollar

#	input.txt	output.txt
1	11	1 2
2	100	0 2

Izoh:

$11_2 = 3_{10}$ . n toqligi sabab, Ali 1ni qo'shadi: $n=3+1=4$ .

Endi esa, Vali sonni ikki marta ikkiga bo'ladi: $n = \frac{4}{2}$ ,

$n = \frac{2}{2} = 1$ .

Masala B

Ali va Vali