IBM Ponder this 2018 April

这题其实可以手算。

通过第六感可以得知，$3$次实验是不行的，$4$次实验隐隐约约是有解的。

然后脑内妄想一小时可以得到一个解

1 2 5
1 3 4
1 2 4
1 3 5

这题就做完了。

另外，我为了求稳还是写了一个小程序来证明$3$次实验无解。

首先，大小不超过$1$的和大小超过$3$的集合肯定是不能用的；其次大部分大小为$2$或$3$的集合其实也不能用；这样就只有$23$种集合了，把它们爆搜一遍显然是时间允许的(因为$\binom{23}{4}$很小)。(如果你不知道答案是$4$的话。。构造两分钟就能得到答案不超过$6$了吧，而$\binom{23}{6}$也很小嘛。)

在搜到一个方法之后，下一步就是对它进行检验：枚举所有第一位不是$1$的、$1\sim 9$的排列，如果存在一个排列，把这个排列带到答案里面去每个集合仍然不超过$9$，那么答案是不合法的。

虽然会枚举$8\times 8!$个排列，但是显然可以进行强剪枝：一步一步确定排列的数，如果已经有一个集合$>9$了就退出；然后就是搜到一个解就退出。这样就快如闪电了。

实验结果真的快如闪电，不开O2也只要0.03s。

#include <bits/stdc++.h>
using namespace std;

int w(int x) {
  int ans = 0;
  for (int i = 0; i < 9; i++)
    if ((x >> i) & 1)
      ans += i + 1;
  return ans;
}

int s[2333], l;

int ans = 6;
int way[10], ww[10];
int perm[10];
int wt[10];

int succ, used[10];
void dfs2(int n, int x) {
  if (x == 9) {succ = 1; return;}
  for (perm[x + 1] = 1; perm[x + 1] <= 9; perm[x + 1]++)
    if (!used[perm[x + 1]]) {
      int fuck = 0;
      for (int i = 1; i <= n; i++)
	if ((s[way[i]] >> (x - 1)) & 1) {
	  wt[i] += perm[x];
	  if (wt[i] > 9) fuck = 1;
	}
      if (!fuck) {
	used[perm[x + 1]] = 1;
	dfs2(n, x + 1);
	if (succ) return;
	used[perm[x + 1]] = 0;
      }
      for (int i = 1; i <= n; i++)
	if ((s[way[i]] >> (x - 1)) & 1)
	  wt[i] -= perm[x];
    }
}

int check(int n) {
  for (int i = 1; i <= n; i++) wt[i] = 0;
  for (int i = 1; i <= 9; i++) used[i] = 0;
  succ = 0;
  for (perm[1] = 2; perm[1] <= 9; perm[1]++) {
    used[perm[1]] = 1;
    dfs2(n, 1);
    used[perm[1]] = 0;
  }
  return succ ^ 1;
}

void dfs(int N) {
  if (N - 1 >= ans) return;
  if (check(N - 1)) {
    ans = N - 1;
    for (int k = 1; k < N; k++) ww[k] = s[way[k]];
    return;
  }
  for (way[N] = way[N - 1] + 1; way[N] <= l; way[N]++)
    dfs(N + 1);
}

int main() {
  for (int i = 0; i < (1<<9); i++)
    if (__builtin_popcount(i) > 1)
      if (w(i) <= 9)
	s[++l] = i;
  cerr << l << endl;
  dfs(1);
  cout << ans << endl;
  for (int i = 1; i <= ans; i++) {
    int u = ww[i];
    for (int j = 0; j < 9; j++)
      if ((u >> j) & 1) cout << j + 1 << " ";
    cout << endl;
  }
}

做IBM题最需要的是信心，其次是码速。