TopCoder

Thumb opengraph icon 200x200
Kevin_Zhang
\(I\ want\ to\ be\ better!\ But\ how.....\)

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

33.3% (2/6)

Description

你有玩過孔明棋嗎?

孔明棋,也叫單身貴族、獨立鑽石棋。源於18世紀法國的宮廷貴族,是一種自我挑戰的遊戲,可以鍛鍊邏輯思維能力。

孔明棋的玩法類似中國跳棋,但不能走步,只能跳。

棋子只能跳過相鄰的櫃子到空位上,並且把被跳過的棋子吃掉。

棋子可以沿格線橫、縱方向跳,但是不能斜跳,剩下越少棋子越好。

孔明棋與華容道、魔術方塊同被稱為智力遊戲界的三大不可思議。

一般認為,最後剩下6隻或以上棋子是「一般」;最後剩下5隻棋子是「頗好」;剩下4隻棋子是「很好」;剩下3隻棋子是「聰明」;剩下2隻棋子是「尖子」;剩下1隻棋子是「大師」;最後剩下1隻,而且在正中央是「天才」。

現在給你一個 1 x n 的孔明棋棋盤盤面,為了達到「天才」的境界,你決定檢查一下,這個盤面最少可以留下幾個棋子。

Input Format

本題有多組測試資料:

每組測試資料的:

第一行有一個數字 n ,代表棋盤是 1 x n 的 ( n < 24)
第二行有著 n 個字元,- 代表沒有棋子,o 代表有棋子

Output Format

請輸出一個數字 k ,代表盤面上最少可以留下 k 個棋子。

Sample Input

12
oooooooooo-o
12
oooooooooooo


Sample Output

1
12

Hints

Problem Source

原TIOJ1482 / 建中校內培訓第六次模擬考試。
Problem Setter:hallogameboy、peter50216
(Adapt From:Swedish National

Subtasks

No. Testdata Range Score
1 0 7
2 1 7
3 2 7
4 3 7
5 4 7
6 5 7
7 6 7
8 7 7
9 8 7
10 9 7
11 10 7
12 11 7
13 12 16

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6
6 1000 65536 262144 7
7 1000 65536 262144 8
8 1000 65536 262144 9
9 1000 65536 262144 10
10 1000 65536 262144 11
11 1000 65536 262144 12
12 1000 65536 262144 13