#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
const int maxn=20;
const int size=15;
const int maxdep=2;
const int oo=931012;
int a[maxn][maxn];
int data[maxn][maxn];
int f[maxn][maxn];
//data统计出现情况的次数，data[i][j]表示i子连珠，且阻挡情况是j的出现次数
int p;
struct point
{
point():score(0),x(-1),y(-1){}
point(int score,int x,int y):score(score),x(x),y(y){}
int score;
int x,y;
};
int check=0;
struct board
{
void output(point &ans) //输出某一结果
{
a[ans.x][ans.y]=p;
printf("%d %d\n",ans.x,ans.y);
fflush(stdout);
}
void search(int i,int j,int dx,int dy,int vis[maxn],int &opt,int &num,int col,int index)
{
int x=i,y=j;
while (true)
{
if ((x<0)||(x>=size)||(y<0)||(y>=size)||(a[x][y]==3-col))
{
opt++;
break;
}
if (a[x][y]==0) break;
num++;
vis[index++]=true;
x=x+dx;
y=y+dy;
}
}
int count(int opt,int num)
{
if (num>=5) return 200;
if ((num==4)&&(opt==0)) return 100;
if ((num==4)&&(opt==1)) return 60;
if ((num==3)&&(opt==0)) return 70;
if ((num==3)&&(opt==1)) return 20;
if ((num==2)&&(opt==0)) return 40;
if ((num==2)&&(opt==1)) return 10;
if ((num==1)&&(opt==0)) return 10;
if ((num==1)&&(opt==1)) return 1;
return 0;
}
int score() //对整个局面进行估价
{
int vis[size],i,j,e[3]={0,0,0};
for (int i=0;i<size;i++) //横向评估
{
memset(vis,false,sizeof(vis));
for (int j=0;j<size;j++)
if ((vis[j]==false)&&(a[i][j]!=0))
{
int opt=0,num=0;
if ((j==0)||(a[i][j-1]==3-a[i][j])) opt++;
search(i,j,0,1,vis,opt,num,a[i][j],j);
e[a[i][j]]+=count(opt,num);
}
}
for (int i=0;i<size;i++) //纵向评估
{
memset(vis,false,sizeof(vis));
for (int j=0;j<size;j++)
if ((vis[j]==false)&&(a[j][i]!=0))
{
int opt=0,num=0;
if ((j==0)||(a[j-1][i]==3-a[j][i])) opt++;
search(j,i,1,0,vis,opt,num,a[j][i],j);
//printf("2:?%d %d %d\n",num,opt,count(opt,num));
e[a[j][i]]+=count(opt,num);
}
}
for (int i=4;i<size*2-5;i++) //左下到右上
{
memset(vis,false,sizeof(vis));
for (int j=0;j<size;j++)
{
int ii,jj;
if (i<15)
{
ii=i-j;
jj=j;
}
else
{
ii=14-j;
jj=(i-14)+j;
}
if ((ii<0)||(ii>=size)||(jj<0)||(jj>=size)) continue;
if ((vis[j]==false)&&(a[ii][jj]!=0))
{
int opt=0,num=0;
if ((jj==0)||(i==14)||(a[ii+1][jj-1]==3-a[ii][jj])) opt++;
search(ii,jj,-1,1,vis,opt,num,a[ii][jj],j);
//printf("2:?%d %d %d\n",num,opt,count(opt,num));
e[a[ii][jj]]+=count(opt,num);
}
}
}
for (int i=4;i<size*2-5;i++) //右下到左上
{
memset(vis,false,sizeof(vis));
for (int j=0;j<size;j++)
{
int ii,jj;
if (i<15)
{
ii=i-j;
jj=j;
}
else
{
ii=14-j;
jj=(i-14)+j;
}
ii=14-ii;
if ((ii<0)||(ii>=size)||(jj<0)||(jj>=size)) continue;
if ((vis[j]==false)&&(a[ii][jj]!=0))
{
int opt=0,num=0;
if ((jj==0)||(i==0)||(a[ii-1][jj-1]==3-a[ii][jj])) opt++;
search(ii,jj,1,1,vis,opt,num,a[ii][jj],j);
//printf("2:?%d %d %d\n",num,opt,count(opt,num));
e[a[ii][jj]]+=count(opt,num);
}
}
}
return e[p]-e[3-p];
}
}chess;
int min(int a,int b)
{
if (a>b) return b;else return a;
}
int max(int a,int b)
{
if (a>b) return a;else return b;
}
int random(int p)
{
return (rand()*rand()*rand()%p+p)%p;
}
void find(int i,int j,int &num,int &opt,int dx,int dy,int col)
{
int x,y,k;
for (k=1;k<5;k++)
{
x=i+k*dx;
y=j+k*dy;
if ((x<0)||(x>=size)||(y<0)||(y>=size))
{
opt++;
break;
}
if (a[x][y]==col) num++;
if (a[x][y]==3-col)
{
opt++;
break;
}
if (a[x][y]==0) break;
}
}
void count(int i,int j,int col)
{
int num,opt;
//横
num=1;opt=0;
find(i,j,num,opt,0,-1,col); //左
find(i,j,num,opt,0,1,col); //右
if (num>5) num=5;
data[num][opt]++;
//竖
num=1;opt=0;
find(i,j,num,opt,-1,0,col); //上
find(i,j,num,opt,1,0,col); //下
if (num>5) num=5;
data[num][opt]++;
//左上右下斜
num=1;opt=0;
find(i,j,num,opt,-1,-1,col); //左上
find(i,j,num,opt,1,1,col); //右下
if (num>5) num=5;
data[num][opt]++;
//右上左下斜
num=1;opt=0;
find(i,j,num,opt,-1,1,col); //右上
find(i,j,num,opt,1,-1,col); //左下
if (num>5) num=5;
data[num][opt]++;
}
int score(int i,int j) //对(i,j)进行估价
{
int ans[3]={0,0,0};
if (a[i][j]!=0) return -oo;
for (int k=1;k<=2;k++)
{
memset(data,0,sizeof(data));
count(i,j,k);
if ((data[5][0])||(data[5][1])||(data[5][2])) ans[k]+=500;
if ((data[4][0])||(data[4][1]>=2)||((data[4][1])&&(data[3][0]))) ans[k]+=400;
if (data[3][0]>=2) ans[k]+=300;
if ((data[3][0]==1)&&(data[3][1]==1)) ans[k]=80;
if (data[3][0]==1) ans[k]=70;
if ((data[4][1]==1)&&(data[3][0]==0)) ans[k]=60;
if (data[3][1]>=2) ans[k]=50;
if (data[2][0]>=2) ans[k]=40;
if (data[3][1]==1) ans[k]=30;
if (data[2][0]==1) ans[k]=20;
if (data[2][1]>=1) ans[k]=10;
ans[k]+=min(min(i,size-i),min(j,size-j));
}
//ans[p]=int(ans[p]*1.1);
int t=max(ans[1],ans[2]);
t+=random(15);
return t;
}
bool over(point &ans)
{
int i,j;
bool check=false;
int t=-oo;
//判断直接必赢情况
for (i=0;i<size;i++)
for (j=0;j<size;j++)
if (a[i][j]==0)
{
memset(data,0,sizeof(data));
count(i,j,p);
if ((data[5][0])||(data[5][1])||(data[5][2]))
{
int temp=score(i,j);
if (temp>t)
{
t=temp;
ans=point(temp,i,j);
}
check=true;
}
}
if (check) return true;
//判断直接必输情况
for (i=0;i<size;i++)
for (j=0;j<size;j++)
if (a[i][j]==0)
{
memset(data,0,sizeof(data));
count(i,j,3-p);
if ((data[5][0])||(data[5][1])||(data[5][2]))
{
int temp=sco
