题解 [email protected]洛谷 | [email protected] 【Integer Game】

题意:交互题,三堆石子,石子个数分别为 a,b,c[1,109]Za,b,c\in\left[1,10^9\right]\cap\rm{Z},选择先手或者后手进行游戏。先手给定一个数 k[1,1012]Zk\in\left[1,10^{12}\right]\cap\rm{Z},后手将一堆石子个数增加 kk,不能连续增加同一堆两次。如果有两堆石子个数一样,后手输;如果 10310^3 次内先手没有赢,则后手赢。问谁有必胜策略。


首先,我们考虑什么时候后手会输。

假设此时 a<b<ca\lt b\lt c

  1. 如果 bacbb-a\ne c-b,则不论可以修改哪个,后手均不会输。
  2. 如果 ba=cbb-a=c-b,此时如果不能修改 cc,则可以构造出 k=ba=cbk=b-a=c-b 使得后手必败;如果可以修改 cc,则不能保证。

得出结论:当且仅当 a,b,ca,b,c 成等差数列,且最大数不能被修改时后手败。

我们考虑是否能构造一种方法,使得在若干步后,三堆石子满足这一条件。

考虑如何能得到等差数列,且最大数不能修改?设原来三堆石子为 a<b<ca\lt b\lt cx=cb,y=cax=c-b,y=c-a,并且最大数不能被修改,那么就可以构造 k=x+y=c×3(a+b+c)k=x+y=c\times 3-(a+b+c) 满足条件。

为啥?假设修改 aa,则三个数变为 a+c×3(a+b+c),b,ca+c\times 3-(a+b+c),b,c,即为 2×cb,b,c2\times c-b,b,c,其中 (2×cb)c=cb(2\times c-b)-c=c-b,符合上面的描述。修改 bb 同理。

此时我们发现,中位数为 cc,即原来的最大数;公差可以根据这一点推出:用 cc 减去另一个没有变化的数。

问题转化为如何固定最大值不能动。我们一开始构造 k=infk=\inf,即大于任何一个数的数,此时被修改的不管是哪个,都是修改后的最大值。记录这个最大值,然后按照上面说的做即可。


总结:首先构造 k=infk=\inf,获得最大值位置,用指针记录。然后根据最大值,构造 k=c×3sk=c\times 3-s,其中 cc 为这个最大值,ss 为三个数的和。最后得到一个最大数不能修改的等差数列,构造 kk 为公差即可。

没错你没看错,先手在三步以内必胜。


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e10;

ll a[3], *p, k, s;
ll interact(ll x) {
	printf("%lld\n", x);
	fflush(stdout);
	ll res;
	scanf("%lld", &res);
	if(!res) exit(0);
	a[--res] += x;
	return res;
}

int main() {
	scanf("%lld%lld%lld", &a[0], &a[1], &a[2]);
	puts("First"); fflush(stdout);
	s = a[0] + a[1] + a[2] + inf;
	k = interact(inf);
	p = &a[k];
	k = interact((*p)*3-s);
	ll _ = 3 - (p - a) - k;
	k = interact((*p)-a[_]);
	return 0;
}