2011/10/13

EPOCH@まつやま2011予選 (ソースだけ)

※ This article is written only Japanese!

EPOCH@まつやま2011の予選のソースのみ書いておきます。


[問題1]

#include<stdio.h>
#include<stdlib.h>
#define NUM 500000

int comp(const void *p1,const void *p2){
  return *((const int *)p2)-*((const int *)p1);
}

int main(void){
  int data[NUM];
  int a=0,b=0,lasta;
  int i,j,k,n;
  scanf("%d",&n);
  for(i=0;i<n;i++) scanf("%d",data+i);
  qsort(data,n,sizeof(int),comp);
  for(i=0;i<n;i++){
    if(b==0 && data[i]==data[i+1]) b=data[i];
    else{
      if((i!=n-1 && data[i]==data[i+1]) || (i!=0 && data[i]==data[i-1])) continue;
      lasta=data[i];
      a++;
    }
    if(b!=0 && a==b){
      printf("%d\n",data[i]);
      return 0;
    }else if(b!=0 && a>b){
      for(j=0;j<i;j++){
if((j!=n-1 && data[j]==data[j+1]) || (j!=0 && data[j]==data[j-1])) continue;
if(--b==0){
 printf("%d\n",data[j]);
 return 0;
}
      }
    }
  }
  printf("%d\n",lasta);
  return 0;
}

[問題2]

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

int chkdel(char *str1,char *str2,int len_1);
int chkadd(char *str1,char *str2,int len_1);
int chkchg(char *str1,char *str2,int len_1);

int main(void){
  char *pointqueue;
  char nowstr[256],nextstr[256];
  int now_Q=0;
  int i,j,k,n,l1,l2;
  long long int point;
 
  scanf("%d",&n);
  pointqueue=(char *)calloc(n,sizeof(char));
  scanf("%s",nextstr);
  l2=strlen(nextstr);
  while(--n){
    l1=l2;
    strcpy(nowstr,nextstr);
    scanf("%s",nextstr);
    l2=strlen(nextstr);
    if(l1-1==l2){
      if(chkdel(nowstr,nextstr,l1)) *(pointqueue+now_Q++)=0;
      else now_Q=0;
    }else if(l1+1==l2){
      if(chkadd(nowstr,nextstr,l1)) *(pointqueue+now_Q++)=1;
      else now_Q=0;
    }else if(l1==l2){
      switch(chkchg(nowstr,nextstr,l1)){
      case 0:
now_Q=0;
break;
      case 1:
*(pointqueue+now_Q++)=2;
break;
      case 2:
*(pointqueue+now_Q++)=3;
break;
      }
    }else{
      now_Q=0;
    }
  }
  point=0;
  for(i=0;i<now_Q;i++){
    switch(*(pointqueue+i)){
    case 0:
      --point;
      break;
    case 1:
      ++point;
      break;
    case 2:
      point+=2;
      break;
    case 3:
      point*=2;
      break;
    }
  }
  printf("%lld\n",point);
  return 0;
}

int chkdel(char *str1,char *str2,int len_1){
  int i,c=0;
  for(i=0;i<len_1;i++){
    if(*(str1+i+c)==*(str2+i)) continue;
    if(++c>=2) break;
    i--;
  }
  if(c==1) return 1;
  return 0;
}
int chkadd(char *str1,char *str2,int len_1){
  return chkdel(str2,str1,len_1+1);
}

int chkchg(char *str1,char *str2,int len_1){
  int i,c=0;
  for(i=0;i<len_1;i++) c+=(*(str1+i)==*(str2+i));
  if(c==len_1-1) return 1;
  else if(c== len_1) return 2;
  return 0;
}

[問題3]

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

short check(char num[],short aketa,short bketa,short cketa);

int main(void){
  char num[1001];
  short aketa,bketa,cketa;
  short count=0,len,n,i;
 
  scanf("%hd",&n);
  for(i=0;i<n;i++){
    scanf("%s",num);
    len=strlen(num);
    for(cketa=len/3;cketa<=len/2;cketa++){
      aketa=cketa;
      bketa=len-cketa-aketa;
      if(check(num,aketa,bketa,cketa)){
printf("line %d is OK\n",i);
count++;
break;
      }
      aketa=cketa-1;
      bketa=len-cketa-aketa;
      if(check(num,aketa,bketa,cketa)){
printf("line %d is OK\n",i);
count++;
break;
      }  
      bketa=cketa;
      aketa=len-cketa-bketa;
      if(check(num,aketa,bketa,cketa)){
printf("line %d is OK\n",i);
count++;
break;
      }    
      bketa=cketa-1;
      aketa=len-cketa-bketa;
      if(check(num,aketa,bketa,cketa)){
printf("line %d is OK\n",i);
count++;
break;
      }
    }
  }
  printf("%hd\n",count);
  return 0;
}

short check(char num[],short aketa,short bketa,short cketa){
  short i,r=1;
  short tmp,kuri;
  char *a,*b,*c;
  a=(char *)calloc(aketa+1,sizeof(char));
  b=(char *)calloc(bketa+1,sizeof(char));
  c=(char *)calloc(cketa+1,sizeof(char));
  strncpy(a,num,aketa);
  strncpy(b,num+aketa,bketa);
  strncpy(c,num+aketa+bketa,cketa);
  for(i=1;i<=cketa;i++){
    if(i>aketa && i>bketa) tmp=kuri;
    else if(i>aketa) tmp=(int)(b[bketa-i]-'0'+kuri);
    else if(i>bketa) tmp=(int)(a[aketa-i]-'0'+kuri);
    else tmp=(int)(a[aketa-i]+b[bketa-i]-'0'-'0'+kuri);
    kuri=(tmp>9)?1:0;
    tmp%=10;
    if(tmp!=c[cketa-i]-'0'){
      r=0;
      break;
    }
  }
  if(r==1){
    puts(a);
    puts(b);
    puts(c);
    putchar('\n');
  }
  free(a);
  free(b);
  free(c);
  return r;
}

0 件のコメント:

コメントを投稿