2011/09/04

Codeforces Beta Round #85(Div.2) report

I think this contest's problems are very good because it's short! And I submitted all problem! I think, it's my first "all-problem-submitted contest". However,  only two sources were accepted because I have careless misses.

A: I solved this 0:07. Using strcmp.

B: I solved this 0:17. A little thinking, we get very simple answer.

C: I solved this 0:39. However, I don't see y<n case. So it's hacked, and I solved after contest. Algorithm is good.

D: I solved this 0:56. However, I use unsigned short, and I should use unsigned int. So, WA at System test. I solved after contest.Algorithm is good, too.

E: I submitted this, but I can't get good algorithm.

Problems are here.
Result:1418,442/1273. Rate 1419->1418.
If you want to know C or D's algorithm, please read my source!

I'm going to write Codeforces #83's report next.

[A]

#include<stdio.h>
#include<string.h>
#include<ctype.h>

int main(void){
  char str[2][128];
  int i;
  scanf("%s%*c",str[0]);
  scanf("%s%*c",str[1]);
  for(i=0;i<strlen(str[0]);i++) str[0][i]=tolower(str[0][i]);
  for(i=0;i<strlen(str[1]);i++) str[1][i]=tolower(str[1][i]);
  i=strcmp(str[0],str[1]);
  if(i<0) puts("-1");
  else if(i==0) puts("0");
  else puts("1");
  return 0;
}

[B]

#include<stdio.h>

int main(void){
  int n,x,y;
  scanf("%d %d %d",&n,&x,&y);
  if((x==n/2 || x==n/2+1)&&(y==n/2 || y==n/2+1)) puts("NO");
  else puts("YES");
  return 0;
}

[C](Accepted answer after contest)

#include<stdio.h>

typedef unsigned long long int u_long;

int main(void){
  u_long x,y,n;
  u_long i,j,k;
  u_long sum=0;
  scanf("%I64u %I64u %I64u",&n,&x,&y);
  if(y<n){
    puts("-1");
    return 0;
  }
  sum=(y-n+1)*(y-n+1);
  sum+=(n-1);
  if(sum<x){
    puts("-1");
  }else{
    printf("%I64u\n",(y-n+1));
    for(i=1;i<n;i++) puts("1");
  }
  return 0;
}


[D](Accepted answer after contest)

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main(void){
  unsigned int div[100000];
  unsigned int i,j,k,n,x,y,now,count;
 
  memset(div,0,sizeof(div));
  scanf("%u",&n);
  for(now=1;now<=n;now++){
    scanf("%u %u",&x,&y);
    count=0;
    for(i=0;(i+1)*(i+1)<=x;i++){
      if(x%(i+1)!=0) continue;
      j=x/(i+1)-1;
      if(div[i]==0 || div[i]<now-y) count++;
      div[i]=now;
      if(div[j]==0 || div[j]<now-y) count++;
      div[j]=now;
    }
    printf("%u\n",count);
  }
  return 0;
}


[E](Wrong answer in contest)


#include<stdio.h>
#include<string.h>
#define MIN(n,m) (((n)<(m))?(n):(m))

int main(void){
  int n,m,board[40][40],i,j,k,out=0;
  scanf("%d %d",&n,&m);
  memset(board,0,sizeof(board));
  for(i=0;i<m;i++){
    for(j=0;j<n;j++){
      if(j!=0 && board[i][j-1]==0 && board[i][j]==0){
board[i][j]=2;
out++;
      }
      if(i!=0 && board[i-1][j]==0){
board[i][j]=2;
out++;
      }
      if(i==m-1 && j!=0 && j!=n-1 && board[i][j-1]==0 && board[i][j+1]==0){
board[i][j]=2;
out++;
      }
      if(board[i][j]==2){
if(j-1!=0) board[i][j-1]=1;
if(i-1!=0) board[i-1][j]=1;
if(i+1<m) board[i+1][j]=1;
if(j+1<n) board[i][j+1]=1;
      }
    }
  }
  printf("%d\n",n*m-out);
  return 0;
}

0 件のコメント:

コメントを投稿