SRM 489 DIV 2 500P
2010年11月30号晚上8点参加了久违的【SRM 489 DIV 2】，但有点生疏了。
250P是个极简单的题，子串匹配，可是Java字符串的方法记不得了，晕死，对照API，21分钟。
500P是个搜索题，之前做过些USACO，所以一上来就想到DFS了，测试通过时，感觉真好，还特意测试了上界，不超时，嘿嘿，36分钟。
1000P就不做了哈。
coding完排在room第二，challenge时，知道有个人最后几秒钟提交的250P代码可能是瞎写的，在犹豫要不要cha他时，被浙大的一人率先cha掉了，呵呵，以后要猛点。
最后居然得了个room第一，汗...
500P Problem
已知(int[] roses, int[] lilies)，roses[i]表示第i个花篮有多少朵玫瑰，lilies[i]表示第i个花篮有多少朵百合，最多16个花篮。
现在任选一些花篮，将这些花篮里的花摆成一个R*C的矩阵，并且相邻边的花种要求不一样。
求abs(R-C)最小值，没有合法的返回-1。
500P Solution
Brute Force
我的解法：用DFS枚举花篮的所有组合，然后判断玫瑰数和百合数的差在1以内，然后判断花数和的两个约数差值是否最小。
public class BuyingFlowers {// Better than minepublic int buy(int[] roses, int[] lilies) {int res = 100000000;int size = roses.length;int a, b;int up = 1<<size;for(int i = 1; i < up; i++) {a = b = 0;for(int j = 0; j < size; j++) {if((i&(1<<j)) != 0) {a += roses[j];b += lilies[j];}}if(Math.abs(a-b) < 2) {int s = a + b;for(int r = (int)Math.sqrt(s); r > 0; r--) {if(s%r == 0) {if(res > Math.abs(r-s/r)) {res = Math.abs(r-s/r);}break;}}}}if(res == 100000000) {return -1;}return res;}}