菜是原罪。
英语不好更是原罪。
\(\mathrm{A - Grid game}\)
题解
\(4 \times 4\) 的格子，两种放法。
发现这两种在一起时候很讨厌，于是强行拆分这个格子
上面 \(2 \times 4\) 给横的，下面给竖的。
\(\mathrm{Code}\)
#include<bits/stdc++.h>
using namespace std;
template <typename Tp>
void read(Tp &x){
x=0;char ch=1;int fh;
while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
if(ch=='-') ch=getchar(),fh=-1;
else fh=1;
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
x*=fh;
}
int n;
char s[1007];
int a[8][8];
void del(){
for(int i=1;i<=4;i++){
int sum=0;
for(int j=1;j<=4;j++){
sum+=a[i][j];
}
if(sum==4){
for(int j=1;j<=4;j++) a[i][j]=0;
}
}
}
int ex1[3][3],ex2[3][3];
void solve(int x){
if(x==1){
if(!ex1[1][1]){
printf("%d %d\n",1,1);
ex1[1][1]=1;
}
else if(!ex1[1][2]){
printf("%d %d\n",1,3);
ex1[1][2]=1;
}
else if(!ex1[2][1]){
printf("%d %d\n",2,1);
ex1[2][1]=1;
}
else if(!ex1[2][2]){
printf("%d %d\n",2,3);
ex1[2][2]=1;
}
if(ex1[1][1]&&ex1[1][2]) ex1[1][1]=ex1[1][2]=0;
if(ex1[2][1]&&ex1[2][2]) ex1[2][1]=ex1[2][2]=0;
}
else{
if(!ex2[1][1]){
printf("%d %d\n",3,1);
ex2[1][1]=1;
}
else if(!ex2[1][2]){
printf("%d %d\n",3,2);
ex2[1][2]=1;
}
else if(!ex2[2][1]){
printf("%d %d\n",3,3);
ex2[2][1]=1;
}
else if(!ex2[2][2]){
printf("%d %d\n",3,4);
ex2[2][2]=1;
}
if(ex2[1][1]&&ex2[1][2]&&ex2[2][1]&&ex2[2][2]) ex2[1][1]=ex2[1][2]=ex2[2][1]=ex2[2][2]=0000;
// if(ex1[1][1]&&ex1[1][2]) ex1[1][1]=ex1[1][2]=0;
// if(ex1[2][1]&&ex1[2][2]) ex1[2][1]=ex1[2][2]=0;
}
}
int main(){
cin>>(s+1);
n=strlen(s+1);memset(a,1,sizeof(a));
for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) a[i][j]=0;
for(int qwq=1;qwq<=n;qwq++){
int k=s[qwq]-'0';
solve(k);
}
return 0;
}\(\mathrm{B - Game with modulo}\)
题解
真是一个神仙交互题。
首先需要想到一个结论，函数 \(f(x)=x mod a\) 是一个周期函数， \(T=a\) 。
这个题目一开始的想法就是二分，但是由于 \(a\) 取模的问题，不太满足可二分性。
但是在一个周期内，是可以二分的。
于是倍增确定 \(a\) 的取值范围，二分答案。
\(60\) 次询问卡的紧紧的...
cyz同学问了 \(61\) 次...
\(\mathrm{Code}\)
#include<bits/stdc++.h>
using namespace std;
template <typename Tp>
void read(Tp &x){
x=0;char ch=1;int fh;
while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
if(ch=='-') ch=getchar(),fh=-1;
else fh=1;
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
x*=fh;
}
string s;
int main(){
while(1){
cin>>s;
if(s=="end") break;
if(s=="mistake") break;
int l=0,r=1;
while(1){
printf("? %d %d\n",l,r);
fflush(stdout);
cin>>s;
if(s=="y") l=r,r*=2;
else break;
}
int ans;
while(l<r-1){
int mid=(l+r)>>1;
printf("? %d %d\n",mid,l);
fflush(stdout);
cin>>s;
if(s=="x") l=mid;
else r=mid;
}
++l;
printf("! %d\n",l);
fflush(stdout);
}
return 0;
}