還記得切義大利餅問題嗎?
這回你買了一個義大利蛋糕,打算切給一些人吃。
這蛋糕很特別,形狀是凸 n 邊形的,而且在頂點的地方都會有一些顏色,
很碰巧地,所有的頂點都是紅色、綠色、藍色三種顏色之一,
另外你還發現三種顏色都出現在蛋糕的頂點上,且任一兩個相鄰頂點顏色都不一樣。
你每次都會在蛋糕的頂點到頂點之間切一刀,切出一塊三角形的小蛋糕,
為了讓吃蛋糕的人感到這義大利蛋糕的特別,所以你希望切出來的蛋糕的每種顏色都有(亦即三個頂點三種顏色,三種願望一次滿足)
因為你的訪客眾多,所以你希望蛋糕切的越多越好,因此要如何切才能切出最多的蛋糕成為重要的問題。
為了研究這個問題,你決定寫個程式解決他,但因為方法可能有很多種,所以這題採用互動式方式。
在程式碼的最上端,請引入 #include "lib1455.h"該標頭檔。
本題只有一筆測試資料:
請在讀入前呼叫TakeCake(),否則你會買不到蛋糕而WA。
在呼叫後,
Input中會出現兩行文字
第一行有一個數字 n ( 0 < n < 1000 ) ,代表這個蛋糕是 n 邊形的。
第二行有連在一起的 n 個字母,代表順時針由 1 開始編號到 n ,字母只可能是'R','G','B'其中一種
本題沒有輸出。
請在處理之後按照順序呼叫一次How_Many_Cut()以及多次Cut()
原TIOJ1455 / 建中校內培訓第三次模擬考試。
Problem Setter:hallogameboy、peter50216
(Adapt From:算法藝術P.20)
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 |