IBM Ponder this 2018 August

每天只能刷刷水题娱乐自己的大脑。。。

先翻译题面。。有$18$个数$W_{1\dots 9}$和$G_{1\dots 9}$，它们互不相同且其中至少$17$个是质数，且$\sum_{i=1}^9W_i=\sum_{i=1}^9G_i$。令$W=\sum W_i/10$，则每个人喝到$W$的水，即$\frac{G_i}{W_i-W}=\frac{G_j}{W_j-W}$。设$\frac{G_i}{W_i-W}=k$，则$\sum G_i=k\sum W_i-9kW=k\sum W_i/10$。所以$k=10$。也就是$G_i=10W_i-\sum_jW_j$。

枚举$\sum_jW_j=S$，然后求出所有的$G\le S$使得$(G+S)/10$是整数，且$G$和$(G+S)/10$中至少一个是质数。然后dp：$f[i][j][k][l]$表示考虑最小的$i$个$G$，从中选$j$个，和为$k$，$l$表示已选的数中有没有$G$或$(G+S)/10$不是质数的情况。对于一个$S$判定的复杂度是$O(S^2)$的。这个方法只能保证$G$中的数两两不同，并不能保证不出现$G_i=W_j$的情况。但是对绝大部分解肯定都有$G_i\ne W_j$。

贴代码

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

#define sz 4040
int good[sz], len_good, state[sz];
int isprime[sz];
int N = 4000;
int u = 9;
#define GOOD 1
#define OK 2
#define EVIL 3

void init_prime() {
  for (int i = 2; i <= N; i++) isprime[i] = 1;
  for (int i = 2; i <= N; i++)
    if (isprime[i])
      for (int j = i + i; j <= N; j += i) isprime[j] = 0;
}

void init(int S) {
  len_good = 0;
  for (int G = 1; G <= S; G++)
    if ((G + S) % (u + 1) == 0) {
      int W = (G + S) / (u + 1);
      if (isprime[G] || isprime[W]) {
        good[++len_good] = G;
        if (isprime[G] && isprime[W]) state[G] = GOOD;
        else state[G] = OK;
      } else state[G] = EVIL;
    }
}

int dp[sz][10][sz][2];
void doit(int S) {
  for (int i = 0; i <= len_good; i++)
    for (int j = 0; j <= u; j++)
      for (int k = 0; k <= S; k++)
        dp[i][j][k][0] = dp[i][j][k][1] = 0;

  dp[0][0][0][0] = 1;
  for (int i = 0; i < len_good; i++)
    for (int j = 0; j <= u; j++)
      for (int k = 0; k <= S; k++) {
        if (dp[i][j][k][0]) {
          dp[i + 1][j][k][0] = 1;
          if (k + good[i + 1] <= S)
            dp[i + 1][j + 1][k + good[i + 1]][state[good[i + 1]] == OK] = 1;
        }
        if (dp[i][j][k][1]) {
          dp[i + 1][j][k][1] = 1;
          if (k + good[i + 1] <= S && state[good[i + 1]] == GOOD)
            dp[i + 1][j + 1][k + good[i + 1]][1] = 1;
        }
      }
}

int G[11];
bool answer(int S) {
  int i = len_good, j = u, k = S, l = 0;
  if (!dp[i][j][k][l]) l = 1;
  if (!dp[i][j][k][l]) return false;
  printf("%d ", l);
  for (; i; i--)
    if (k >= good[i] && (l || state[good[i]] == GOOD))
      if (dp[i - 1][j - 1][k - good[i]][l - (state[good[i]] == OK)])
        l -= (state[good[i]] == OK), k -= (G[j--] = good[i]);
  printf("G=[");
  for (i = 1; i <= u; i++) printf("%d, ", G[i]);
  printf("],W=[");
  for (i = 1; i <= u; i++) printf("%d, ", (G[i] + S) / (u + 1));
  printf("]\n");
  return true;
}

int main() {
  init_prime();
  for (int S = 1; S <= sz; S++) {
    if (S % 1000 == 0) fprintf(stderr, "S=%d\n", S);
    init(S);
    if (len_good >= 8) {doit(S); answer(S);}
  }
  return 0;
}

import numpy as np
def prime(x) : return x != 1 and (not any([x % i == 0 for i in range(2, x)]))
def chk(w, g) :
	s = sum(w)
	print "sum =", s
	if s != sum(g): return 1
	if len(w) != 9 or len(g) != 9: return 2
	if len(np.unique(w + g)) != 18: return 3
	t = sum([prime(i) for i in w] + [prime(i) for i in g])
	if t < 17: return 4
	for i in range(9) :
		if w[i] * 10 - s != g[i]: return 5 + i
	print "info:", t, "primes"
	return 0

G = [3, 23, 43, 83, 103, 223, 383, 503, 523]
W = [189, 191, 193, 197, 199, 211, 227, 239, 241]
print chk(W,G)

G = [13, 53, 73, 113, 173, 193, 293, 353, 953]
W = [223, 227, 229, 233, 239, 241, 251, 257, 317]
print chk(W,G)

ps. 官方解法中发现了一个有趣的东西：我们可以暴力地(利用Green-Tao Theorem)将一个不满足素数条件的解变成满足素数条件的解。令$W=[45,46,47,48,49,50,51,52,58]$，$G=[4,14,24,34,44,54,64,74,134]$，则$W,G$满足条件。令$p_1,p_2,\dots,p_{134}$为长度为$131$的素数等差数列(Green-Tao Theorem：这种等差数列存在)，则$W'=[p_{45},p_{46},p_{47},p_{48},p_{49},p_{50},p_{51},p_{52},p_{58}]$，$G'=[p_4,p_{14},p_{24},p_{34},p_{44},p_{54},p_{64},p_{74},p_{134}]$满足条件且$18$个数都是素数。解法来自Kipp Johnson。