背景
阿祁:冠成,你要不要幫我灌程式
冠成:甚麼程式?
阿祁:有關於城市模擬的那一種程式
冠成:等等...所以你要請我幫你灌城市程式嗎?
阿祁:對,總而言之就是請冠成灌城市程式
冠成:我知道了,我「已經」幫你灌好了
阿祁:所以是完成式的概念?
冠成:應該是吧,冠成灌城市程式是完成式
阿祁:那你要教我寫正三角形的題目嗎?
冠成:給題目嗎?
題目
給你$\color{black}{N}$個等大小的正三角形,在以下條件下,問你能不能利用全部的正三角形,恰好拼出一個任意、實心的凸$\color{black}{K}$邊形?
條件:
(1)每個三角形一定至少有一邊和另一個三角形相接
(2)兩個三角形相接的方式一定要是「一個邊對一個邊」整個接在一起。
如上圖,左邊的擺放是好的;而右邊的話有兩個錯誤,首先它不是凸多邊形,另外它的三角形的相接並不是完整的「一個邊對一個邊」相接。
限制:
$\color{black}{2 ≤ N ≤ 10^4}$
$\color{black}{3 ≤ K ≤ 100}$
第一行有一正整數$\color{black}{T}$代表測資筆數$\color{black}{(1 ≤ T ≤ 10)}$,也就是代表你在這個測試資料中需要解答$\color{black}{T}$筆詢問。
接著有$\color{black}{T}$行,每行兩個數$\color{black}{N、K}$。
對於每筆測資輸出yes
、no
,分別代表擺放方式的有無。
5 2 3 2 4 4 5 6 6 7 7
no yes no yes no
範例測資說明:
如上圖,其中凸四邊形、凸六邊形分別可以透過2、6個相同正三角形組成,所以答案為yes
,另外我們可以證明剩下三個$\color{black}{(N,K)}$的三角形不存在。
配分:
$\color{black}{10\%}$ : $\color{black}{N ≤ 10}$
$\color{black}{10\%}$ : $\color{black}{N ≤ 100}$
$\color{black}{10\%}$ : $\color{black}{K ≤ 4}$
$\color{black}{70\%}$ : 無其他限制