Codeforces Round #308 (Div. 2) C. Vanya and Scales

原题: http://codeforces.com/contest/552/problem/C

---

题目大意: 给两个数字,w和m, 再给一堆砝码, 砝码的重量是w^0,w^1,w^2….w^100, 且每种只有1个.是否能放到天平上来称出m(天平平衡). 砝码能放天平的两边.

---

分析: 首先观察一下题, 一看就是进制问题, 上来先把m变成w进制. 然后我们知道每个砝码只有一个, 所以我们要考虑怎么放才能平衡, 举个栗子, m是7, w是3, 我用一个叫into的数组, 把m变成w进制, 变成后就是 1,2,0, 因为 1*3^0 + 2*3^1. 然后我们观察一下这个数字, 假设我们把m放在天平的左边, 那么相当于左边已经放上了1个3^0 和2个3^1, 通过观察我们发现,

1. 如果数组元素为1, 那么我们可以通过直接放一个相同的砝码在右边的天平, 天平就可以平衡.
2. 如果数组元素为0, 那么我们可以不放任何砝码在右边就能使天平平衡.
3. 如果数组元素为w, 那么我们尝试去放一个比当前砝码大1的砝码到右边的天平上, 比如, 如果w=3, 数组的第二位,3^1的值是3, 那么3*3^1 = 3^2. 不失一般性的, 假设w = w, 数组第i位 w^i的值是w, 那么w*(w^i) = w^(i+1).
4. 如果数组元素为w-1, 那么我们放当前砝码在左边, 并且尝试放一个大1的砝码在右边. 这时,相当于天平的右边欠了左边一个差为w^(i+1), i为数组的位数的砝码, 为了弥补这个差,使得天平平衡, 我们需要把当前砝码放到左边, 并且尝试放一个更大的在右边. 举个栗子, w=4, m=12, 数组[0,3,0], 在第二位时, 相当于w+w^3 = 4+4^3 = 16 = 4^4. 不失一般性的, 假设w = w, 数组第i位w^i的值是w-1, 那么 (w-1)*(w^i) + w^i  = (w)^(i+1). 这个等号可以看成是一个天平, (w-1)*(w^i)是原数组m的. w^i是我们放一个大小i位的砝码在左边, 天平右边是(w)^(i+1). 所以天平就平衡了.

代码如下:

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int w = in.readInt();
        int m = in.readInt();
        int t = m;//extra
        int[] into = new int[50];
        int p = 0;
        while (m > 0){
            into[p] = m % w;
            m/=w;
            p++;
        }
        for (int i = 0; i < into.length-2; i++) {
            if (into[i] == w) {
                into[i] = 0;
                into[i+1]++;
            }else if (into[i] == w-1) {
                into[i+1]++;
            }else if (into[i] == 0 || into[i] == 1)
                continue;
            else {
                out.print("NO");
                return;
            }
        }
        out.print("YES");
        // extra: print the Scales
//        ArrayList<Integer> left = new ArrayList<>();
//        ArrayList<Integer> right = new ArrayList<>();
//        left.add(t);
//        for (int i = 0; i < into.length; i++) {
//            if (into[i] == 0){
//                continue;
//            } else if (into[i] == 1) {
//                right.add((int)Math.pow(w, i));
//            } else if (into[i] == w-1) {
//                left.add((int)Math.pow(w, i));
//            }
//        }
//        out.print("left" + left);
//        out.print("right" + right);
    }

我添加了打印天平的代码.