首頁  題目列表  狀態列表  排行榜  註冊  帳號: 密碼:
公告:支援C++11 (2014/08/18 21:39)
Problem 0098 : 刮鬍匹配
0098 -- 刮鬍匹配
Case Time Limit: 1000 ms    Memory Limit: 131072 KB
Total Testdata Count: 5
AC/Submit: 26/42    AC/Submit Users: 12/16

[回到列表]
題目敘述

在一個神祕的部落,當地有一個習俗就是每隔幾個月就要集體刮鬍。



這個儀式的流程是這樣的,所有刮鬍者與被刮鬍者站在一條沒有分歧的河流旁邊站成一列,刮鬍者要面向上游,被刮鬍者要面向下游,然後刮鬍者只能去刮剛好站在前面的人的鬍子,刮完之後就必須離開,被刮鬍者被刮鬍後也得離開。

現在給你$N$個人排排站的方式,問你最後會剩下多少人站在河邊。

輸入說明

第$1$行是一個正整數$N$,代表有N個人
第$2$行有$N$個數字,非$0$即$1$,以空格隔開,分別代表刮鬍者與被刮鬍者,而上游在第$N$個人那裏,下游在第$1$個人那裏。

輸出說明

一個整數$\xi$,代表河邊最後剩下來的人數。

範例輸入

#Sample input 1
5
0 1 0 0 1

#Sample input 2
4
0 0 1 1

#Sample input 3
6
1 1 1 0 0 0


範例輸出

#Sample output 1
1

#Sample output 2
0

#Sample output 3
6


備註

對於第一筆範測是這樣的:
左邊數來第1個人會去刮第2個人的鬍子,然後這兩個人走掉。(現在 : 0 0 1)
然後這時第2個人會去刮第3個人的鬍子,然後走掉。(現在 : 0)
剩下那個人沒有人讓他去刮鬍子。

第二筆範測是這樣的:
第2個人刮了第3個人的鬍子然後兩個走掉。(現在 : 0 1)
這時候剩下來第1個人剛好可以去掛第2個人的鬍子,所以兩個又走掉了。
剩下0個人在那邊

第3筆範測的話一開始根本沒有人可以去刮其他人的鬍子,所以大家都留在河邊了。

測資組$A$ : $N \leq 2000$
測資組$B$ : $N \leq 100000$

測資

測資組A : 1~2 (2筆測資),40 分
測資組B : 3~5 (3筆測資),60 分
[回到列表]