IBM Ponder this 2016 August

IBM最近的题水得不正常→_→

这个月的题目翻译就是，有$10$个袋子，里面各有$N$个硬币。有的袋子里只有10g的真币，有的袋子里只有9g的假币。允许你只用一个准确的秤称量一次，要求确定哪些袋子里的是假币。$N\ge 1024$。

这太水辣!第$i$个袋子取出$2^{i-1}$个，称总重量，二进制分解就好。

现在顶多三个袋子的假币，且$N=174$，求一种称量方法。解决$N$更小的问题就有bonus。

注：这篇博客里没有答案。。想要答案的自己跑程序去。

目前做到了$N=157$。。。用了一个小程序。

令$f_i$表示从第$i$个袋子里拿出多少，那么要求就是所有$f_i$，所有$f_i+f_j(i\ne j)$，所有$f_i+f_j+f_k(i,j,k\text{两两不同})$都不相同。

怎么判断一个$f$是否合法呢?令$G_a$表示$a$能否表示成$f_i$或$f_i+f_j$或$f_i+f_j+f_k$。考虑把数一个一个加入，加入的时候用$G$判断与之前的是否产生冲突， 加入之后更新$G$。具体见代码的okay()和add()函数。

现在要产生$f$了。。就乱搞。。每次随机加入一个$[1,N]$内的数到$f$中，如果$[1,N]$中没有加入后仍合法的数就随机删一个$f$中已经有的数。

这个方法效果不错。。不过还是要看脸(随机数种子)，随机数种子好的话一下就出解，不好的话要等很久(反正我几秒没跑出来就掐了。。也许永远也跑不出来呢)。

跑出来了就可以手动调$N$的值了。

#include <bits/stdc++.h>
using namespace std;
int f[233], G[23333];
int n;
int okay(int v){
  if (G[v]) return 0;
  for (int j = 1; j <= n; j++) if (G[f[j] + v]) return 0;
  for (int j = 1; j <= n; j++)
    for (int k = j + 1; k <= n; k++)
      if (G[f[j] + f[k] + v]) return 0;
  return 1;
}
void add(int v, int d){
  //d == 1 -> add, d == 0 -> del
  G[v] = d;
  for (int j = 1; j <= n; j++) G[f[j] + v] = d;
  for (int j = 1; j <= n; j++)
    for (int k = j + 1; k <= n; k++)
      G[f[j] + f[k] + v] = d;
}

void add(int x){add(x, 1); f[++n] = x;}
void del(int x){swap(f[x], f[n]); n--; add(f[n + 1], 0);}

int V = 174;
int dead(){
  for (int i = 1; i <= V; i++) if (okay(i)) return 0;
  return 1;
}

int main(){
  srand(time(0));
  while (1){
    if (n == 10){
      for (int i = 1; i <= n; i++) printf("%d ", f[i]);
      return 0;
    }
    if (dead()) del(rand() % n + 1);
    else{
      int x;
      do {x = rand() % V + 1;} while (!okay(x));
      add(x);
    }
  }
  return 0;
}

upd 8.4

我好像得到了两颗星。。ibm说两颗星的条件是求出最小的$N$。。(然而我并没有证明这个$N$是最小的啊，我都没有意料到呢

但是这个一定是可以证明的。。不然ibm也不敢咬定$157$是最小的。。这个就当一个坑了

upd 9.4

ibm的题解也没证明157是最小的。。而且它的解跟我给的完全一样。。