- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
«دکارتی» تردستی ماهر است. وقتی دست دکارتی از روی کارتی رد شود، کارت برعکس می‌شود. (یعنی اگر کارت رو باشد پشت می‌شود و اگر پشت باشد رو می‌شود.) آقای دکارتی می‌خواهد $t$ روز متوالی تردستی کند. در هر روز تعدادی کارت پیش روی او است و او در یک عملیات می‌تواند بازه‌ای دلخواه و متوالی از کارت‌ها را برعکس کند. او می‌خواهد حداقل تعداد عملیات که همه کارت‌ها به سمت رو تبدیل شوند را بداند!
ورودی
در خط اول $t$ می‌آید که نشان دهنده تعداد روزهایی است که آقای دکارتی تردستی می‌کند. $$1 \leq t \leq 1000$$
در $t$ خط بعد، در هر کدام یک رشته می‌آید که حرف $i$ام آن اگر 1 باشد یعنی کارت $i$ام رو است و اگر 0 باشد یعنی کارت $i$ام به پشت قرار دارد.
تعداد کارت‌های هر روز حداکثر ۵۰ است.
خروجی
در خط $i$ام از $t$ خط جواب مساله را خروجی دهید.
مثال
ورودی نمونه ۱
5
01
00010
11011
111000
101010101
خروجی نمونه ۱
1
2
1
1
4
- در روز اول بازه‌ی $[1,1]$ را برعکس کند.
- در روز دوم بازه‌های $[4,4]$ و $[1,5]$ را برعکس کند.
- در روز سوم بازه‌ی $[3,3]$ را برعکس کند.
- در روز چهارم بازه‌ی $[4, 6]$ را برعکس کند.
- در روز پنجم بازه‌های $[2, 2]$، $[4, 4]$، $[6 ,6]$ و $[8 ,8]$ را برعکس کند.
ارسال پاسخ برای این سؤال