i253. 正三角形非常好......差不多一樣凸多邊形
標籤 : 幾何
通過比率 : 7人/11人 ( 64% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-05-19 11:48

內容

背景

阿祁:冠成,你要不要幫我灌程式

冠成:甚麼程式?

阿祁:有關於城市模擬的那一種程式

冠成:等等...所以你要請我幫你灌城市程式嗎?

阿祁:對,總而言之就是請冠成灌城市程式

冠成:我知道了,我「已經」幫你灌好了

阿祁:所以是完成式的概念?

冠成:應該是吧,冠成灌城市程式是完成式

阿祁:那你要教我寫正三角形的題目嗎?

冠成:給題目嗎?

 

題目

給你$\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}$。

輸出說明

對於每筆測資輸出yesno,分別代表擺放方式的有無。

範例輸入 #1
5
2 3
2 4
4 5
6 6
7 7
範例輸出 #1
no
yes
no
yes
no
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
提示 :

範例測資說明:

如上圖,其中凸四邊形、凸六邊形分別可以透過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\%}$ : 無其他限制

標籤:
幾何
出處:
Chi's Coding Problem [管理者: Ststone1687 (Ststone) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
36679 r1cky (hehe) i253
題解
119 2023-08-02 13:39