Codechef 2011 August Long-contest report(one problem)

I join the long contest. It's my first long contest! And I think, it's good for me to join long contest (including marathon). However, I'm usually busy, so, if I'll be not busy, I'll join!

I solved a problem "Infinite Grid Game". I explain the algorithm.

To be easy,we regard the goal as (0,0). (We can parallel translate.)
If the vehicle is at (n,0) , (0,n) or (n,n) (n is natural number), next player is winner.
So, they shouldn't move to these points. However, if the vehicle is at (1,2) or (2,1), next player must move to these lose points.  i.e. the winner is put the vehicle at (1,2) or (2,1). So,(1,3),(1,4),... and so on, are lose points.
Run through these processes, we have a map which means who is winner.

For Example...
Bob's Win Point:(1,2),(2,1),(3,5),(5,3) ...
Alice's is other.

Make map, and print, We can solve this problem easily.

My rank is 116 in the contest.
Rate of long contest is up from non-rated to 2.787, rank is 1785.


#define NUM 1000

int main(void){
  int m,n,i,j,k,x,y;
  int t,p,q;
  short board[NUM][NUM];

      if(j>=1000) break;
      if(abs(i-j)>=1000) continue;
      if(board[j][abs(i-j)]!=0) continue;
      for(x=j+1;x<1000;x++) board[x][abs(i-j)]=1;
      for(y=abs(i-j)+1;y<1000;y++) board[j][y]=1;
      for(k=1;j+k<1000 && abs(i-j)+k<1000;k++) board[j+k][abs(i-j)+k]=1;
    scanf("%d %d %d %d",&m,&n,&p,&q);
    if(board[m-p][n-q]==0) puts("Bob");
    else puts("Alice");
  return 0;

0 件のコメント: