「题目描述」

么么哒的小威同学得到一个好玩的玩具。小威同学对它爱不释手。它包含若干根木 棒,小威可以用这些木棒对称地摆成一个正九边形。愚人节到了,小威最好的朋 (ji) 友 小斌同学决定捉弄一下么么哒的小威同学,就声称他带走了其中的若干根木棒。小威想 先看看到底有没有少木棒,然后再考虑怎么整小斌。小威判断有没有少木棒的做法很简 单,就是剩下的木棒能不能对称地摆成一个正九边形(木棒都要用上)。可是小威的智 商比较捉急,他弄了半个小时还是没有判断出来,只好找你来帮忙。

「输入格式」

从 enneagon.in 中输入数据
第一行,一个整数 T,表示数据的组数
接下来每一行,第一个数 n,表示这组数据共有 n 个木棒,接下来 n 个数表示 n

根木棒的长度。

「输出格式」

输出到 enneagon.out 中
对于每组数据输出一行,”OK” 表示没有少木棒,”LOST” 表示少了木棒。

「样例输入」

3
91111111111
11 1 1 1 1 2 2 2 2 2 2 2 10 1 2 3 3 3 3 3 3 3 3

「样例输出」

OK OK LOST

「数据规模与约定」

对于 50% 的数据保证:T ≤ 50,n ≤ 50.
对于 100% 的数据保证:T ≤ 100,n ≤ 90,每根木棒长度 ≤ 30

题解

尼玛我bool函数末尾没写返回值1，本机都没问题，交上去全wa

这世界

POJ2362 的翻版,原题是判定能不能拼成一个正方形。本题的要求是能不能对称的 摆成一个正九边形。

注意,因为要求对称,其实我们要摆的也就只有 4.5 条边。 剪枝:

1. 所有木棍的和能被 9 整除。

2. 相同长度的木棍两两配对,最多剩下一个不能配对。

3. 如果边长为奇数,那么一定要有一根木棍不能配对,则这根木棍的长度必须是奇 数

4. 如果边长为偶数且有一根木棍不能配对,那么这个木棍的长度必须是偶数

5. 最长的木棍应该比边长小或相等。

6. 如果某长度的木棍不能完成某个子问题,那么和它一样长的也不能完成。

7. 在本来要拼成一根棒的时候子问题不能完成所有任务,那么整体不可能完成。

8. 用某长度的木棍拼接了以后应继续选取比它小或相等的木棍。

9. 如果能够成功拼出 3.5 根木棍的话就完成目标。