TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

36.8% (7/19)

Tags

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 1

7
RBGBRGB

Sample Output 1

其中一種可能的輸出:
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

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

Testdata and Limits

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