【CF1375F】Integer Game

题目

题目链接:https://codeforces.com/problemset/problem/1375/F
这是一道交互题

有三堆石子,个数分别为\(a,b,c\)。游戏的规则如下:

  • 先手每次给定一个数\(k\),后手需要给这三堆石子的某一堆的个数加上\(k\)。
  • 后手不能连续对同一堆石子进行操作。
  • 当存在两堆石子个数相等时,先手胜;当回合数超过1000时,后手胜。

你可以自行决定当先手还是后手。

\(a,b,c \leq 10^9,k \leq 10^{12}\)。

思路

考虑先手如何获胜:显然只有在三堆石子形成等差数列且上一次操作石子最多的那一堆时才可以获胜。
然后我就不会了
考虑以下操作:我们直接给一堆石子加上一个很大的数让它成为石子数最多的。假设此时三堆石子的数量分别为 \(a,b,c(a<b<c)\),那么我们直接加上 \(2c-a-b\)。因为此时后手只能选择 \(a,b\) 中的一组,无论选择哪一组,石子数都会变成一个等差数列,且下一次能操作的只剩下较少的两堆石子了。
所以先手必胜。

代码

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

ll a[4];
int x,y;

int main()
{
	scanf("%lld%lld%lld",&a[1],&a[2],&a[3]);
	printf("First\n");
	fflush(stdout);
	printf("100000000000\n");
	fflush(stdout);
	scanf("%d",&x);
	a[x]+=100000000000;
	printf("%lld\n",3LL*a[x]-a[1]-a[2]-a[3]);
	fflush(stdout);
	scanf("%d",&y);
	a[y]+=3LL*a[x]-a[1]-a[2]-a[3];
	sort(a+1,a+4);
	printf("%lld\n",a[2]-a[1]);
	fflush(stdout);
	return 0;
}
上一篇:牛客小白月赛30J 小游戏 dp


下一篇:LuoguP7222 信息学竞赛