文章目录

交互题:Jump 做题笔记

发布于

题意

给定 $n$,你要猜一个长度为 $n$ 的 01 串。$n$ 是一个偶数。

每次你给出一个长度为 $n$ 的 01 串,如果

  • 全部猜中,返回 $n$
  • 你恰好猜中一半,返回 $\dfrac n2$
  • 否则,返回 $0$

最多询问 $n + 500$ 次。
$2 \leq n \leq 1000$

题解

查看题解
随机至多 $499$ 次,找到一个二进制串 $S$,使得刚好才对一半。

然后把 $S_1$ 取反(0 变 1, 1 变 0)。

然后枚举 $2 \leq i \leq n$,把 $S_1$ 和 $S_i$ 取反后询问。如果得到 $\dfrac n2$,则表示 $S_i$ 和 $S_1$ 不同。否则说明 $S_i$ 和 $S_1$ 相同。

最后 $2$ 次,第一次尝试 $S_1 = 0$ 的情况。
若不成功,尝试 $S_1 = 1$ 的情况。

考虑随机 $499$ 次,恰好猜中一半的概率。
恰好对一半的 01 串的个数为 $n$ 个位置里选 $\dfrac n2$ 个取反的方案数,即 $\dbinom n{\dfrac n2}$。
每次猜中的概率就是
$$\frac{\dbinom n{\dfrac n2}}{2^n}$$

代入 $n = 1000$,每次猜中一半的概率大约是 $0.0252250181783608$。

为了方便下面的计算,我们设
$$f\left(n\right) = \frac{\dbinom n{\dfrac n2}}{2^n}\\g\left(n\right) = 1 - f\left(n\right)$$

精确计算猜 $499$ 次成功的概率:
猜 $499$ 次成功的概率就是 $1$ 减去猜 $499$ 次都成功的概率,即
$$1 - g\left(n\right)^{499}$$

代入 $n = 1000$,概率是 $0.99999709408611$。相当高。

查看代码

// Please submit with C++17!
#pragma region HEAD   // Spectre
#include <algorithm>  // By rbtree (https://rbtr.ee)
#include <array>
#include <bitset>
#include <cmath>
#include <complex>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_map>
#include <utility>
#include <vector>
#ifdef ___RB_DEBUG___
#include "rb_debug.h"
#else
#define dbg(...)
#endif
#define ra (scanf("%lld", &__TEMP_READ_VALUE), __TEMP_READ_VALUE)
#define LIKELY(exp) __builtin_expect(bool(exp), 1)
#define UNLIKELY(exp) __builtin_expect(bool(exp), 0)

typedef long long tp;
tp __TEMP_READ_VALUE;
using namespace std;
#pragma endregion HEAD

////////////////////////////////////////////////////////////////////////////////

class RANDOM {
  unsigned long long __seed, __coefficient;

 public:
  RANDOM() : __seed(217), __coefficient(17) {}

  unsigned long long operator()(unsigned long long l, unsigned long long r) {
    return rand() % (r - l + 1) + l;
  }
} rd;

signed main() {
  tp n = ra;
  array<bool, 1003> a, diff;
  function<tp()> q = [&]() -> tp {
    for (tp i = 1; i <= n; ++i) {
      printf("%lld", (tp)a[i]);
    }
    puts("");
    fflush(stdout);
    return ra;
  };
  while (1) {
    for (tp i = 1; i <= n; ++i) {
      a[i] = rd(0, 1);
    }
    if (tp x = q(); x == n) {
      return 0;
    } else if (x == n / 2) {
      break;
    }
  }
  a[1] ^= 1;
  for (tp i = 2; i <= n; ++i) {
    a[i] ^= 1;
    diff[i] = q() == n / 2;
    a[i] ^= 1;
  }
  a[1] ^= 1;
  for (tp i = 2; i <= n; ++i) {
    a[i] ^= diff[i];
  }
  if (q() != n) {
    for (tp i = 1; i <= n; ++i) {
      a[i] ^= 1;
    }
    q();
  }
  return 0;
}

////////////////////////////////////////////////////////////////////////////////


暂无评论

发表评论