TopCoder

Thumb c eyvrnvoaalwfw
rareone0602
我好喜歡貓

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

20.0% (1/5)

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

For Testdata: 0 ~ 0, Score: 7
For Testdata: 1 ~ 1, Score: 7
For Testdata: 2 ~ 2, Score: 7
For Testdata: 3 ~ 3, Score: 7
For Testdata: 4 ~ 4, Score: 7
For Testdata: 5 ~ 5, Score: 7
For Testdata: 6 ~ 6, Score: 7
For Testdata: 7 ~ 7, Score: 7
For Testdata: 8 ~ 8, Score: 7
For Testdata: 9 ~ 9, Score: 7
For Testdata: 10 ~ 10, Score: 7
For Testdata: 11 ~ 11, Score: 7
For Testdata: 12 ~ 12, Score: 16
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144
11 1000 65536 262144
12 1000 65536 262144