TopCoder

Thumb 100
archerop
afeaspixfjoaflmhsdisihovpsjiopjv,opsjdpoi

User's AC Ratio

81.2% (13/16)

Submission's AC Ratio

48.6% (18/37)

Description

你(小志)醒了,身邊是殘破的建築物、正在燃燒的車子還有空無一人的街道。

「這裡是...」,正當你在回想過去的記憶時,突然你聽到了一聲大叫「啊--」。
是誰在尖叫呢?「沒時間想這些了,還是先過去看看要緊。」於是你往叫聲的方向跑去。
「啊啊--搭咧嘎塔斯K爹」,轉過街道後,你看到一群僵屍正在向一個小女孩慢慢逼近。「喔喔喔!!是隻小蘿莉耶。」你興奮的叫著,「不對不對!現在不是注意這個的時候,而且我也不是蘿莉控,只是我要救的女孩剛好是隻蘿莉而已然後救她之後順便把她帶回家嘿嘿嘿嘿嘿...」

你確認了一下現在的情況,有N隻殭屍A1,A2,...AN成一排正逐步往小蘿莉靠近,而不知從何而來的記憶讓你想起殭屍依照病毒的感染類型總共分成兩種,J殭屍和I殭屍,你還知道J殭屍的行動比較緩慢。
而你身上有一把藥物注射槍,它可以讓某個殭屍的類型改變,比如你對Ai殭屍發射,如果他本來是I殭屍就會變成J殭屍,反之亦然。
你還有一把藥物噴射槍,他可以讓某個殭屍和在他前面的所有殭屍的類型都改變,比如你對Ai殭屍發射,Ai,Ai−1,Ai−2,...,A1的型態都會改變。

不過很遺憾的是你身上並沒有任何可以殺死殭屍的武器,因此你擬訂了一個計畫,「利用這些藥物槍讓這些殭屍都變成行動緩慢的J殭屍,然後帶著小蘿莉逃走然後跟她嘿嘿嘿嘿嘿...」你這樣幻想著。
而你身上的彈藥有限,你希望你藥物注射槍和藥物噴射槍發使用次數的總和越小越好,請問你最少要發射幾次呢?

Input Format

第一行有一個數字N代表殭屍的數量,第二行有長度為N的0−1字串,其中第i個字元是1就代表Ai是J類型的殭屍,第i個字元是0就代表Ai是I類型的殭屍。

測資組A : N≤10
測資組B : N≤1000
測資組C : N≤105
測資組D : N≤107

Output Format

一個數字,代表最少共要發射多少次。

Sample Input

#Sample Input 1
5
00100

#Sample Input 2
8
10001101

#Sample Input 3
10
1111111111

Sample Output

#Sample Output 1
2

#Sample Output 2
3

#Sample Output 3
0

Hints

對於#Sample 1,你最好的方式是對著A5發射藥物噴射槍,然後再對A3發射藥物注射槍。
對於#Sample 3,你什麼都不用做,就可以把蘿莉帶走了。

Problem Source

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 3, Score: 20
For Testdata: 4 ~ 6, Score: 30
For Testdata: 7 ~ 9, Score: 40
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 131072 65536
1 1000 131072 65536
2 1000 131072 65536
3 1000 131072 65536
4 1000 131072 65536
5 1000 131072 65536
6 1000 131072 65536
7 1000 131072 65536
8 1000 131072 65536
9 1000 131072 65536