TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

60.0% (3/5)

Description

還記得切義大利餅問題嗎?

這回你買了一個義大利蛋糕,打算切給一些人吃。

這蛋糕很特別,形狀是凸 n 邊形的,而且在頂點的地方都會有一些顏色,

很碰巧地,所有的頂點都是紅色、綠色、藍色三種顏色之一,

另外你還發現三種顏色都出現在蛋糕的頂點上,且任一兩個相鄰頂點顏色都不一樣

你每次都會在蛋糕的頂點到頂點之間切一刀,切出一塊三角形的小蛋糕,

為了讓吃蛋糕的人感到這義大利蛋糕的特別,所以你希望切出來的蛋糕的每種顏色都有(亦即三個頂點三種顏色,三種願望一次滿足)

因為你的訪客眾多,所以你希望蛋糕切的越多越好,因此要如何切才能切出最多的蛋糕成為重要的問題。

為了研究這個問題,你決定寫個程式解決他,但因為方法可能有很多種,所以這題採用互動式方式。

在程式碼的最上端,請引入 #include "lib1455.h"該標頭檔。

  • void TakeCake():向商店購買一個蛋糕。
  • void How_Many_Cut(int X):要切成最多的蛋糕要切幾刀
  • void Cut(int X,int Y):從頂點X與頂點Y之間切一刀(第三個點在X,Y之間,並且X到Y為順時針)。
  • void Finish():結束一連串動作。

Input Format

本題只有一筆測試資料:

請在讀入前呼叫TakeCake(),否則你會買不到蛋糕而WA。

在呼叫後,
Input中會出現兩行文字
第一行有一個數字 n ( 0 < n < 1000 ) ,代表這個蛋糕是 n 邊形的。
第二行有連在一起的 n 個字母,代表順時針由 1 開始編號到 n ,字母只可能是'R','G','B'其中一種

Output Format

本題沒有輸出。
請在處理之後按照順序呼叫一次How_Many_Cut()以及多次Cut()

Sample Input

7
RBGBRGB

Sample Output

其中一種可能的輸出:
How_Many_Cut(4);
Cut(1,3);
Cut(7,3);
Cut(5,7);
Cut(5,3);
Finish();

Hints

Problem Source

原TIOJ1455 / 建中校內培訓第三次模擬考試。
Problem Setter:hallogameboy、peter50216
(Adapt From:算法藝術P.20)

Subtasks

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