概述
Problem - 1713D - Codeforces
D. Tournament Countdown
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
This is an interactive problem.
There was a tournament consisting of 2n2n contestants. The 11-st contestant competed with the 22-nd, the 33-rd competed with the 44-th, and so on. After that, the winner of the first match competed with the winner of second match, etc. The tournament ended when there was only one contestant left, who was declared the winner of the tournament. Such a tournament scheme is known as the single-elimination tournament.
You don't know the results, but you want to find the winner of the tournament. In one query, you select two integers aa and bb, which are the indices of two contestants. The jury will return 11 if aa won more matches than bb, 22 if bb won more matches than aa, or 00 if their number of wins was equal.
Find the winner in no more than ⌈13⋅2n+1⌉⌈13⋅2n+1⌉ queries. Here ⌈x⌉⌈x⌉ denotes the value of xx rounded up to the nearest integer.
Note that the tournament is long over, meaning that the results are fixed and do not depend on your queries.
Input
The first line contains a single integer tt (1≤t≤2141≤t≤214) — the number of test cases.
The only line of input contains a single integer nn (1≤n≤171≤n≤17).
It is guaranteed that the sum of 2n2n over all test cases does not exceed 217217.
Interaction
The interaction for each test case begins by reading the integer nn.
To make a query, output "? a b" (1≤a,b≤2n1≤a,b≤2n) without quotes. Afterwards, you should read one single integer — the answer for your query. You can make at most ⌈13⋅2n+1⌉⌈13⋅2n+1⌉ such queries in each test case.
If you receive the integer −1−1 instead of an answer or a valid value of nn, it means your program has made an invalid query, has exceed the limit of queries, or has given incorrect answer on the previous test case. Your program must terminate immediately to receive a Wrong Answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.
When you are ready to give the final answer, output "! x" (1≤x≤2n1≤x≤2n) without quotes — the winner of the tournament. Giving this answer does not count towards the limit of queries. After solving a test case, your program should move to the next one immediately. After solving all test cases, your program should be terminated immediately.
After printing a query or the answer do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see documentation for other languages.
Hacks
To hack, use the following format.
The first line contains an integer tt (1≤t≤2141≤t≤214) — the number of test cases.
The first line of each test case contains a single integer nn (1≤n≤171≤n≤17).
The second line of each test case contains 2n2n numbers on a line — the number of wins of each participant. There should be a sequence of matches that is consistent with the number of wins.
The sum of 2n2n should not exceed 217217.
Example
input
Copy
1 3 2 0 2
output
Copy
? 1 4 ? 1 6 ? 5 7 ! 7
Note
The tournament in the first test case is shown below. The number of wins is [1,0,0,2,0,1,3,0][1,0,0,2,0,1,3,0].
--------------------------------------------------------------------------------------------------------------------------------
首先可以确定的是 ，最差的复杂度为2^n -1次， 
题目给定这一次数可以转化为
2/3 * 2^(n)次 向上取整， 这就意味着，我们要用2次实现3次的效果。
首先看3次是什么效果
经过三次对比，我们角逐出来了4这个答案。现在我们考虑通过2次来直接筛选出来4
我们四个四个来看，1 2 3 4中，很容易发现，被选出去的 1 4,然而没被选出去的2 3的胜场皆为0
5 6 7 8中，没被选出的 5 8胜场皆为 0,1 4 6 7 中 ，未被选出去的 1 6，胜场皆为1，这就启示我们，一旦我们询问当前4个中的任意两个，二者胜场相等，则必定不是最终获胜者，那么剩下的另外两个必定是了，这是一种情况，耗费2，符合标准
那么一旦我们询问的两个恰好不相等，该如何是好呢，不妨看一下不相等的情况都有哪些
1 2 3 4，为例， 1 3不等 1 4不等 2 4不等 ，2 3相等，得出结论，一旦第一次选择的二者不等，较大者必定是最终角逐者之一，较小者一定不是最终角逐者，只需要比较较大者与较小者所在区间的另一个即可，1 3的时候，再比较1 4,1 4 的时候比较2 4,2 4 的时候比较1 4
每次把最终角逐出来的胜利者加入新数组，再把旧数组修改为新数组即可
# include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int a[(1<<18)],b[(1<<18)];
int val[10000];
void ask(int x,int y)
{
cout<<"? "<<x<<" "<<y<<endl;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int nowlen=(1<<n);
for(int i=1; i<=(1<<n); i++)
{
a[i]=i;
// cin>>val[i];
}
while(1)
{
if(nowlen==1)
{
cout<<"! "<<a[1]<<endl;
break;
}
if(nowlen==2)
{
ask(a[1],a[2]);
int x;
cin>>x;
if(x==1)
{
cout<<"! "<<a[1]<<endl;
}
else
{
cout<<"! "<<a[2]<<endl;
}
break;
}
else
{
int templen=0;
for(int i=1; i<=nowlen; i+=4)
{
ask(a[i],a[i+2]);
int x;
cin>>x;
if(x==0)
{
ask(a[i+1],a[i+3]);
cin>>x;
if(x==1)
{
templen++;
b[templen]=a[i+1];
}
else
{
templen++;
b[templen]=a[i+3];
}
}
else
{
if(x==1)
{
ask(a[i],a[i+3]);
cin>>x;
if(x==1)
{
templen++;
b[templen]=a[i];
}
else
{
templen++;
b[templen]=a[i+3];
}
}
else
{
ask(a[i+1],a[i+2]);
cin>>x;
if(x==1)
{
templen++;
b[templen]=a[i+1];
}
else
{
templen++;
b[templen]=a[i+2];
}
}
}
}
for(int i=1; i<=templen; i++)
{
a[i]=b[i];
}
nowlen=templen;
}
}
//cout<<cnt<<endl;
}
return 0;
}
最后
以上就是精明时光为你收集整理的D. Tournament Countdown -交互 递归的全部内容，希望文章能够帮你解决D. Tournament Countdown -交互 递归所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复