Hi Everyone,
Today I encountered a new type of problem which involved an interactive task. The problem link is as follows:
https://atcoder.jp/contests/abc269/tasks/abc269_e
These kind of problems are new to me. Nevertheless, I tried solving it and here is my solution (in C++):
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll t,i,n,a[4];
cin>>n;
while(true){
for(i=0;i<4;i++) a[i]=(rand()%n)+1;
cout<<"? "<<a[0]<<" "<<a[1]<<" "<<a[2]<<" "<<a[3]<<endl;
// cout<<flush;
cin>>t;
if(t==0){
cout<<"! "<<a[1]<<" "<<a[3]<<endl;
// cout<<flush;
exit(0);
}
if(t==-1) exit(0);
}
return 0;
}
I received WA after submitting this solution. I also tried adding "cout<<flush" which are commented now, but that did not help.
Can someone pls help me to correct the solution?
Why do you think random numbers can be a solution?
There can be 1000 rows and 1000 columns, but you are only allowed to make 20 queries at most.
I actually do not know, I interpreted the question as asking random numbers to the judge. Please let me know what it should be if it is wrong.
What you have to do in this question is figure out the only square (i, j) where there is no rook in the i(th) row and j(th) column. You can do this by asking the judge queries about the board as described int he question. The difficulty of this question lies in the fact that you can only ask 20 queries. So you have to create a program that will manufacture queries which will give the maximum possible information no matter the result.
I would actually suggest not doing interactive questions at the moment since they are quite tricky and have some nuances in implementation.
Oh okay
I haven't read this problem but generally binary search is useful in interactive problems
Interactive Problems: Guide for Participants
Thanks a lot!