Description
Nahid Khaleh decides to invite the kids of the "Shahr-e Ghashang" to her wedding anniversary. She wants to prepare a square-shaped chocolate cake with known size. She asks each invited person to determine the size of the piece of cake that he/she wants (which should also be square-shaped). She knows that Mr. Kavoosi would not bear any wasting of the cake. She wants to know whether she can make a square cake with that size that serves everybody exactly with the requested size, and without any waste.
Input
The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by input data for each test case. Each test case consist of a single line containing an integer s, the side of the cake, followed by an integer n (1 ≤ n ≤ 16), the number of cake pieces, followed by n integers (in the range 1..10) specifying the side of each piece.
Output
There should be one output line per test case containing one of the words KHOOOOB! or HUTUTU! depending on whether the cake can be cut into pieces of specified size without any waste or not.
Sample Input
2
4 8 1 1 1 1 1 3 1 1
5 6 3 3 2 1 1 1
Sample Output
KHOOOOB!
HUTUTU!
题目意思还是比较简单的，就是给定一个正方形的边长，要求分成指定边长、指定个数的小正方形，判断是否能恰好分完。
20 个解决方案
#1
不一定要给出算法完全实现代码，只需给出较详细的算法说明也行
#2
1）计算所有小正方形的体积和；
2）计算大正方形的边长，若边长不为整数，结束；
3）放置可以用回溯来做，总是先放最左上的空格；
选择一个能放入大正方形的小正方形，使小正方形的最左上的单元格跟大正方形的最左上的空格重合；
2）计算大正方形的边长，若边长不为整数，结束；
3）放置可以用回溯来做，总是先放最左上的空格；
选择一个能放入大正方形的小正方形，使小正方形的最左上的单元格跟大正方形的最左上的空格重合；
#3
1,根体积和有什么关系？
2,边长不为整数？不太明白，输入不是要求给整数吗？
2,边长不为整数？不太明白，输入不是要求给整数吗？
#4
题目是给定一系列小正方形；
求是否能构成一个大正方形；
大正方形的面积=sum(小正方形的面积)
大正方形的边长是要计算的；
求是否能构成一个大正方形；
大正方形的面积=sum(小正方形的面积)
大正方形的边长是要计算的；
#5
终于看懂题目和output了
大面积=小的面积之和肯定是必要的。
如果任何两个小的边长之和大于大正方形边长也不可以
我试试
大面积=小的面积之和肯定是必要的。
如果任何两个小的边长之和大于大正方形边长也不可以
我试试
#6
谢谢楼上两位，这两点我都考虑过了，但是仍然没有想到一个准确的判断算法
#7
昨天晚上画了一会还是木有想出算法
只恨自己才疏学浅！
只恨自己才疏学浅！
#8
3）放置可以用回溯来做，总是先放最左上的空格；
不是把算法都说出来了么？
不会一定要写出代码才能看明白吧？
不是把算法都说出来了么？
不会一定要写出代码才能看明白吧？
#9
唉，回溯学得不太好啊。。。。
#10
再说“左上”这个词也未免含糊了点吧。。。
#11
装箱问题,0-1规划.
1.穷举法 把所有可能的解一一代入，然后比较满足约束的解，使目标函数最达到最优的解是最优解。这不失为一种方法，但不是一种好方法。如果问题规模大，则无法在可接受的时间内求得最优解。这也是求解整数规划的困难所在。
2.隐枚举法I 是穷举法的改进，其思路是先给出一个可行解，然后代入目标函数算出函数值得到一个上界（如果求最小值）或下界（如果是求最大值）。然后一一检验其它的解，如果该解大于上界或小于下界，则不用检验可行性，因为它不可能是最优解，否则的话就要检验可行性，如果是可行解，则修改上界或下界，继续检验其它的解，否则不用修改上界或下界，直接检验其它的解。这种方法通过上界或下界来控制是否需要进行可行性检验，提高了效率。但是，要找可行解也得花一定的时间，当约束和变量较多时，工作量异常的大，退一步来说，即使可行解比较容易找到，但其产生的上界太大，或是下界太小，则其过滤的效果也不明显。这是这种方法的缺陷。
3.隐枚举法II 这种方法先把问题转化成标准型，然后按照分枝定界法的思想，尽量少的检验可行解来寻找最优解。这种方法比较麻烦，我在这里也描述不清楚，过几天理解透了再来写这一部分。
4.隐枚举法III 这是在程冬时，张声年在江西电力职业技术学院学报上发表的一篇文章《关于0-1型整数规划的若干问题》中提出来的，大致的思路是：把所有可能的解都代入目标函数算出值，然后把这些目标函数值进行排序，如果是求最大值，则降序排列，如果是求最小值则升序排列。然后按这个顺序一个一个的检验对应的解的可行性，当碰到第一个可行解时即得到最优解，因为其它的解不会优于此解了。这种方法的缺陷也是明显的，如果变量为N个，则需求2的N次个目标函数值，然后还要进行排序，这又是项工作量很大的工作，再一个就是，如果排序结果是把可行解排在最后一个，那还是得进行2的N次方次检验。
4.启发式算法 遗传算法，蚁群算法等都可归于此类。这都是随机算法，说白了就是听天由命，即使算出了最优解你也不知道是不是最优解，因为此类算法的收敛性都只是依概率收敛的，真正在算的过程中是否已得到最优只有上帝知道。启发式算法是万不得已的情况下才使用的，我们用这种方法只能保证得到的解比其它方法得到的好，但不一定就说得到了最优了。
1.穷举法 把所有可能的解一一代入，然后比较满足约束的解，使目标函数最达到最优的解是最优解。这不失为一种方法，但不是一种好方法。如果问题规模大，则无法在可接受的时间内求得最优解。这也是求解整数规划的困难所在。
2.隐枚举法I 是穷举法的改进，其思路是先给出一个可行解，然后代入目标函数算出函数值得到一个上界（如果求最小值）或下界（如果是求最大值）。然后一一检验其它的解，如果该解大于上界或小于下界，则不用检验可行性，因为它不可能是最优解，否则的话就要检验可行性，如果是可行解，则修改上界或下界，继续检验其它的解，否则不用修改上界或下界，直接检验其它的解。这种方法通过上界或下界来控制是否需要进行可行性检验，提高了效率。但是，要找可行解也得花一定的时间，当约束和变量较多时，工作量异常的大，退一步来说，即使可行解比较容易找到，但其产生的上界太大，或是下界太小，则其过滤的效果也不明显。这是这种方法的缺陷。
3.隐枚举法II 这种方法先把问题转化成标准型，然后按照分枝定界法的思想，尽量少的检验可行解来寻找最优解。这种方法比较麻烦，我在这里也描述不清楚，过几天理解透了再来写这一部分。
4.隐枚举法III 这是在程冬时，张声年在江西电力职业技术学院学报上发表的一篇文章《关于0-1型整数规划的若干问题》中提出来的，大致的思路是：把所有可能的解都代入目标函数算出值，然后把这些目标函数值进行排序，如果是求最大值，则降序排列，如果是求最小值则升序排列。然后按这个顺序一个一个的检验对应的解的可行性，当碰到第一个可行解时即得到最优解，因为其它的解不会优于此解了。这种方法的缺陷也是明显的，如果变量为N个，则需求2的N次个目标函数值，然后还要进行排序，这又是项工作量很大的工作，再一个就是，如果排序结果是把可行解排在最后一个，那还是得进行2的N次方次检验。
4.启发式算法 遗传算法，蚁群算法等都可归于此类。这都是随机算法，说白了就是听天由命，即使算出了最优解你也不知道是不是最优解，因为此类算法的收敛性都只是依概率收敛的，真正在算的过程中是否已得到最优只有上帝知道。启发式算法是万不得已的情况下才使用的，我们用这种方法只能保证得到的解比其它方法得到的好，但不一定就说得到了最优了。
#12
fun( int idx)
{
if (idx==n)
{
找到有解退出;
}
r=查找大正方形内有空格的最顶的行号；
c=在该行内查找最左边的空格的列号；
foreach(剩下的尚未放置的n-idx个小正方形)
{
k=当前小正方形的边长;
if(大正方形的(r,c）到 (r+k-1,c+k-1)的小区域内都是空格， 也就是该小个正方形能在(r,c)点放下)
{
放置该小个正方形；置大正方形的(r,c）到 (r+k-1,c+k-1)的单元格为非空格状态；
fun(idx+1);
拿起该小正方形，置大正方形的(r,c）到 (r+k-1,c+k-1)的单元格为空格状态；
}
}
}
调用方式：
置大正方形的所有单元格为空格状态；
fun(0);
#13
上面是side==4的情况；
实际上题目并没有所是正方形，而是正s边形；
对于非正4边形，还没想到通用的分解方法；
实际上题目并没有所是正方形，而是正s边形；
对于非正4边形，还没想到通用的分解方法；
#14
问题描述里面square shape就是指正方形吧
#15
Each test case consist of a single line containing an integer s, the side of the cake;
#16
ls强啊
原来回溯是这样子啊，学习
另外 the side of the cake 应该是指边长吧，n边形也太恐怖了
原来回溯是这样子啊，学习
另外 the side of the cake 应该是指边长吧，n边形也太恐怖了
#17
嗯，我也是这么认为，另外这道题目ＩＤ是１０３０，有兴趣的可以自已在北大的ＡＣＭ网站上自已提交一下试试看
#18
对，仔细看了下side确实是边长的意思，
#19
to duduniao85
这不是北大ACM 1030题
刚去看来一下 不一样
这不是北大ACM 1030题
刚去看来一下 不一样
#20
非常抱歉，是１０２０
#21
#1
不一定要给出算法完全实现代码，只需给出较详细的算法说明也行
#2
1）计算所有小正方形的体积和；
2）计算大正方形的边长，若边长不为整数，结束；
3）放置可以用回溯来做，总是先放最左上的空格；
选择一个能放入大正方形的小正方形，使小正方形的最左上的单元格跟大正方形的最左上的空格重合；
2）计算大正方形的边长，若边长不为整数，结束；
3）放置可以用回溯来做，总是先放最左上的空格；
选择一个能放入大正方形的小正方形，使小正方形的最左上的单元格跟大正方形的最左上的空格重合；
#3
1,根体积和有什么关系？
2,边长不为整数？不太明白，输入不是要求给整数吗？
2,边长不为整数？不太明白，输入不是要求给整数吗？
#4
题目是给定一系列小正方形；
求是否能构成一个大正方形；
大正方形的面积=sum(小正方形的面积)
大正方形的边长是要计算的；
求是否能构成一个大正方形；
大正方形的面积=sum(小正方形的面积)
大正方形的边长是要计算的；
#5
终于看懂题目和output了
大面积=小的面积之和肯定是必要的。
如果任何两个小的边长之和大于大正方形边长也不可以
我试试
大面积=小的面积之和肯定是必要的。
如果任何两个小的边长之和大于大正方形边长也不可以
我试试
#6
谢谢楼上两位，这两点我都考虑过了，但是仍然没有想到一个准确的判断算法
#7
昨天晚上画了一会还是木有想出算法
只恨自己才疏学浅！
只恨自己才疏学浅！
#8
3）放置可以用回溯来做，总是先放最左上的空格；
不是把算法都说出来了么？
不会一定要写出代码才能看明白吧？
不是把算法都说出来了么？
不会一定要写出代码才能看明白吧？
#9
唉，回溯学得不太好啊。。。。
#10
再说“左上”这个词也未免含糊了点吧。。。
#11
装箱问题,0-1规划.
1.穷举法 把所有可能的解一一代入，然后比较满足约束的解，使目标函数最达到最优的解是最优解。这不失为一种方法，但不是一种好方法。如果问题规模大，则无法在可接受的时间内求得最优解。这也是求解整数规划的困难所在。
2.隐枚举法I 是穷举法的改进，其思路是先给出一个可行解，然后代入目标函数算出函数值得到一个上界（如果求最小值）或下界（如果是求最大值）。然后一一检验其它的解，如果该解大于上界或小于下界，则不用检验可行性，因为它不可能是最优解，否则的话就要检验可行性，如果是可行解，则修改上界或下界，继续检验其它的解，否则不用修改上界或下界，直接检验其它的解。这种方法通过上界或下界来控制是否需要进行可行性检验，提高了效率。但是，要找可行解也得花一定的时间，当约束和变量较多时，工作量异常的大，退一步来说，即使可行解比较容易找到，但其产生的上界太大，或是下界太小，则其过滤的效果也不明显。这是这种方法的缺陷。
3.隐枚举法II 这种方法先把问题转化成标准型，然后按照分枝定界法的思想，尽量少的检验可行解来寻找最优解。这种方法比较麻烦，我在这里也描述不清楚，过几天理解透了再来写这一部分。
4.隐枚举法III 这是在程冬时，张声年在江西电力职业技术学院学报上发表的一篇文章《关于0-1型整数规划的若干问题》中提出来的，大致的思路是：把所有可能的解都代入目标函数算出值，然后把这些目标函数值进行排序，如果是求最大值，则降序排列，如果是求最小值则升序排列。然后按这个顺序一个一个的检验对应的解的可行性，当碰到第一个可行解时即得到最优解，因为其它的解不会优于此解了。这种方法的缺陷也是明显的，如果变量为N个，则需求2的N次个目标函数值，然后还要进行排序，这又是项工作量很大的工作，再一个就是，如果排序结果是把可行解排在最后一个，那还是得进行2的N次方次检验。
4.启发式算法 遗传算法，蚁群算法等都可归于此类。这都是随机算法，说白了就是听天由命，即使算出了最优解你也不知道是不是最优解，因为此类算法的收敛性都只是依概率收敛的，真正在算的过程中是否已得到最优只有上帝知道。启发式算法是万不得已的情况下才使用的，我们用这种方法只能保证得到的解比其它方法得到的好，但不一定就说得到了最优了。
1.穷举法 把所有可能的解一一代入，然后比较满足约束的解，使目标函数最达到最优的解是最优解。这不失为一种方法，但不是一种好方法。如果问题规模大，则无法在可接受的时间内求得最优解。这也是求解整数规划的困难所在。
2.隐枚举法I 是穷举法的改进，其思路是先给出一个可行解，然后代入目标函数算出函数值得到一个上界（如果求最小值）或下界（如果是求最大值）。然后一一检验其它的解，如果该解大于上界或小于下界，则不用检验可行性，因为它不可能是最优解，否则的话就要检验可行性，如果是可行解，则修改上界或下界，继续检验其它的解，否则不用修改上界或下界，直接检验其它的解。这种方法通过上界或下界来控制是否需要进行可行性检验，提高了效率。但是，要找可行解也得花一定的时间，当约束和变量较多时，工作量异常的大，退一步来说，即使可行解比较容易找到，但其产生的上界太大，或是下界太小，则其过滤的效果也不明显。这是这种方法的缺陷。
3.隐枚举法II 这种方法先把问题转化成标准型，然后按照分枝定界法的思想，尽量少的检验可行解来寻找最优解。这种方法比较麻烦，我在这里也描述不清楚，过几天理解透了再来写这一部分。
4.隐枚举法III 这是在程冬时，张声年在江西电力职业技术学院学报上发表的一篇文章《关于0-1型整数规划的若干问题》中提出来的，大致的思路是：把所有可能的解都代入目标函数算出值，然后把这些目标函数值进行排序，如果是求最大值，则降序排列，如果是求最小值则升序排列。然后按这个顺序一个一个的检验对应的解的可行性，当碰到第一个可行解时即得到最优解，因为其它的解不会优于此解了。这种方法的缺陷也是明显的，如果变量为N个，则需求2的N次个目标函数值，然后还要进行排序，这又是项工作量很大的工作，再一个就是，如果排序结果是把可行解排在最后一个，那还是得进行2的N次方次检验。
4.启发式算法 遗传算法，蚁群算法等都可归于此类。这都是随机算法，说白了就是听天由命，即使算出了最优解你也不知道是不是最优解，因为此类算法的收敛性都只是依概率收敛的，真正在算的过程中是否已得到最优只有上帝知道。启发式算法是万不得已的情况下才使用的，我们用这种方法只能保证得到的解比其它方法得到的好，但不一定就说得到了最优了。
#12
fun( int idx)
{
if (idx==n)
{
找到有解退出;
}
r=查找大正方形内有空格的最顶的行号；
c=在该行内查找最左边的空格的列号；
foreach(剩下的尚未放置的n-idx个小正方形)
{
k=当前小正方形的边长;
if(大正方形的(r,c）到 (r+k-1,c+k-1)的小区域内都是空格， 也就是该小个正方形能在(r,c)点放下)
{
放置该小个正方形；置大正方形的(r,c）到 (r+k-1,c+k-1)的单元格为非空格状态；
fun(idx+1);
拿起该小正方形，置大正方形的(r,c）到 (r+k-1,c+k-1)的单元格为空格状态；
}
}
}
调用方式：
置大正方形的所有单元格为空格状态；
fun(0);
#13
上面是side==4的情况；
实际上题目并没有所是正方形，而是正s边形；
对于非正4边形，还没想到通用的分解方法；
实际上题目并没有所是正方形，而是正s边形；
对于非正4边形，还没想到通用的分解方法；
#14
问题描述里面square shape就是指正方形吧
#15
Each test case consist of a single line containing an integer s, the side of the cake;
#16
ls强啊
原来回溯是这样子啊，学习
另外 the side of the cake 应该是指边长吧，n边形也太恐怖了
原来回溯是这样子啊，学习
另外 the side of the cake 应该是指边长吧，n边形也太恐怖了
#17
嗯，我也是这么认为，另外这道题目ＩＤ是１０３０，有兴趣的可以自已在北大的ＡＣＭ网站上自已提交一下试试看
#18
对，仔细看了下side确实是边长的意思，
#19
to duduniao85
这不是北大ACM 1030题
刚去看来一下 不一样
这不是北大ACM 1030题
刚去看来一下 不一样
#20
非常抱歉，是１０２０