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). 所以天平就平衡了.

代码如下:

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