2011/07/02

Codeforces Beta Round #76(Div.2) report

It's my top score contest!

After starting, I get accepted Problem A(10min). It's very simple problem.

I start problem B.Wrong answer twice(0:19,0:21). I found my wrong in reading, I get accepted(0:22).

Problem C。It's a problem about select folders. I like this problem, it's interesting! I submitted wrong answer twice, however I found a miss, I get accepted(0:42).

It is happy to be able to solve Problem D. Once I read this problem, I think this is greedy algorithm.  Surprisingly, I accepted this only one submit(1:18).

I can't solve Problem E in programming time.

Problems is here。3816,8/1070. It's excellent! I'm grad and celebrate this. I'm ranked up to blue.
A.Only comparing two strings.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(void){
  char str[81],num[10][11],sub[11];
  int i,j,k;
  scanf("%s",str);
  for(i=0;i<10;i++) scanf("%s",num[i]);
  for(i=0;i<8;i++){
    for(j=0;j<10;j++) sub[j]=str[j+10*i];
    sub[11]='\0';
    for(j=0;j<10;j++){
      if(strncmp(sub,num[j],10)==0){
printf("%d",j);
break;
      }
    }
  }
  putchar('\n');
  return 0;
}

    
B.If we use array, it's simple.
#include<stdio.h>

int main(void){
  int in1,in2,people[5];
  int m,n,i,flg=0;
  for(i=0;i<5;i++) people[i]=0;
  scanf("%d",&m);
  for(i=0;i<m;i++){
    scanf("%d %d",&in1,&in2);
    people[in1-1]++;
    people[in2-1]++;
  }
  for(i=0;i<5;i++){
    if(people[i]!=2){
      puts("WIN");
      flg=1;
      break;
    }
  }
  if(flg!=1) puts("FAIL");
  return 0;
}

C.Think each case. Answer is only "1" "2", or "3".
#include<stdio.h>
typedef unsigned int u_int;
int main(void){
  u_int m,n,a,b,a_pos,b_pos,a_line,b_line,k;
  scanf("%u %u %u %u",&m,&n,&a,&b);
  a_pos=(a-1)%n+1;
  b_pos=(b-1)%n+1;
  a_line=(a-1)/n;
  b_line=(b-1)/n;
  if(b==m) b_pos=n;
  if(a_line==b_line){
    k=1;
  }else if(a_pos==1 && b_pos==n){
    k=1;
  }else if(a_pos==1 || b_pos==n){
    k=2;
  }else if(b_pos+1==a_pos){
    k=2;
  }else if(a_line+1==b_line){
    k=2;
  }else{
    k=3;
  }
  printf("%d\n",k);
  return 0;
}

D.It's typical greedy algorithm.
#include<stdio.h>

#define MIN(x,y) ((x<y)?(x):(y))

int main(void){
  int n,m,w;
  double milk[50];
  double cup[50];
  double goals,pour;
  int i,j,k,now,flg;
  
  scanf("%d %d %d",&n,&w,&m);
  for(i=0;i<n;i++) milk[i]=w;
  for(i=0;i<m;i++) cup[i]=0;
  goals=(double)w*(double)n/(double)m;
  now=0;
  flg=0;
  for(i=0;i<m;i++){
    pour=MIN(goals-cup[i],milk[now]);
    cup[i]+=pour;
    milk[now]-=pour;
    if(milk[now]<1E-6){
      now++;
      flg=0;
    }else{
      flg++;
    }
    if(flg==2){
      puts("NO");
      return 0;
    }
    if(cup[i]<goals-(1E-6)){
      i--;
    }
  }

  for(i=0;i<n;i++) milk[i]=w;
  for(i=0;i<m;i++) cup[i]=0;
  now=0;
  puts("YES");
  for(i=0;i<m;i++){
    pour=MIN(goals-cup[i],milk[now]);
    cup[i]+=pour;
    milk[now]-=pour;
    printf("%d %.6f",now+1,pour);
    if(milk[now]<1E-6) now++;
    if(cup[i]<goals-(1E-6)){
      putchar(' ');
      i--;
    }else{
      putchar('\n');
    }
  }

  return 0;
}

0 件のコメント:

コメントを投稿