集訓(xùn)隊作業(yè)0059-burmuda題目0059Burmuda百慕大三角的蛋糕

1、題目 0059 Burmuda（百慕大三角的蛋糕）題目來源：Tehran01者：林希德一、英文原文The Bermuda Trianglehe hidden region of the Bermuda Triangle make everything they needPeopleriangularshs. One day, someone decided to break the rule and bake a hexagonally shd cake. But asusual, he has to serve the cake in triangular pie. The pieare e

2、quilateral triangles but indifferent sizes for different people. He can use as many triangles as needed to cut the cakeopie, sucht nothing remains from the cake. For exle, the following figure showsayt a hexagon with side 9 can be cuto triangles with side 2 and 3. (The cake is cut along thethick lin

3、es, thin lines are drawn to show the sizes).Input is a hexagon and triangle types (specified by the length of their sides) and the goal is to decide if the hexagon can be compley divided by the given triangle types.Inputeger t (1 t 10), the number of test cases,Theline of the input file contains a s

4、inglefollowed by the input data for each test case. Each test case consists of a single line, containing s(1 s 25), the length of the hexagone, followed by n, the number of triangle types (1 n 10), followed by ninclusive).Outputegers representing the length of each triangle typee (betn 1 and 25,Ther

5、e should be one output line per test case containing either YES or NO depending on whetherthe hexagon can be compley divided by the given triangle types.S357le Input2 2 32 3 213 2 2 3Sle OutputNO NOYES二、中文翻譯百慕大三角的蛋糕一位百慕大三角的糕點師傅打算用一些正三角形的蛋糕拼成一塊正六邊形的蛋糕?，F(xiàn)在給你正六邊形蛋糕的邊長 s（s25）以及 n（n10）種正三角形蛋糕的邊長（正三角形蛋糕數(shù)量不

6、限），請你告訴糕點師傅打算能否成功實現(xiàn)。例如下圖就是用邊長為 2 和 3 的正三角形蛋糕拼成的邊長為 9 的正六邊形蛋糕。輸入文件第一行包含整數(shù) t (1 t 10)表示有 t 個測試數(shù)據(jù)。每個測試數(shù)據(jù)僅由一行組成，頭兩個數(shù)是整數(shù) s 和 n，其后有 n 個不超過 25 的正整數(shù)，表示 n 種正三角形蛋糕的邊長。輸出針對每個數(shù)據(jù)輸出 YES 或者 NO 表示糕點師傅的愿望能否實現(xiàn)。樣例輸入35 2 2 37 2 3 213 2 2 3樣例輸出NO NOYES三、初步情況搜索搜吧！典型的搜索題。搜索吧！昆只想到搜索除了搜沒別的想法璟除了搜索，應(yīng)該有數(shù)學(xué)方法吧？恐怕真的是NP沒什么思路。應(yīng)該是搜索

7、吧。復(fù)雜的搜索題目。我目前沒好的猜想，不過建議把問題化簡，變成正方形，這樣會得到的好的猜想以及剪枝條件。這道題目，可以用數(shù)學(xué)方法在判斷繼續(xù)劃分無解時有一定的優(yōu)化，不過有時可能時間復(fù)雜度更高，暫時沒很好的判定方法由于是正六邊形，不像正方形那樣規(guī)則，題目的數(shù)據(jù)量又較小，所以還是用搜索來解決比較好。不知道是否可以貪心從一個角上開始用某種邊長的正三角形覆蓋一個小的正六邊形、或是平行四邊形？林希德仍然是搜索，不過有一些優(yōu)化：1、 將正六邊形分成 6 個正三角形，轉(zhuǎn)而判斷正三角形是否可被覆蓋2、 將正六邊形分成 3 個菱形，轉(zhuǎn)而判斷菱形是否可被覆蓋3、 將正六邊形分成 2 個梯形，轉(zhuǎn)而判斷梯形是否可被覆蓋

8、4、 最后判斷正六邊形是否可被覆蓋從數(shù)據(jù)規(guī)模上看，出題人只想到了搜索。但是即使是搜索也有優(yōu)化的余地，例如先看六變形的 1/6 是否有解，再看 1/3 是否有解，再看 1/2 是否有解，這樣可以通過大多數(shù)數(shù)據(jù)。好像可以先將正六邊形分成 6 個一樣的正三角形，然后看每個正三角形是否能被完全覆蓋；的話可以考慮分成 3 個一樣的菱形；再的話分成 2 個一樣的梯形；最后則為正六邊形。這樣可能可以稍微減少一點搜索的復(fù)雜度。目前還沒有自己做過。我覺得，如果搜索的話，不要先急著去搜索整個六邊形，可以先試著搜索能不能拼成正六邊形的 1/6（就是正三角形），如果再去搜索能不能拼成正六邊形的 1/3（就是兩個整三角形拼成的菱形），再就去搜索正六邊形的