読者です 読者をやめる 読者になる 読者になる

ichirin2501's diary

いっちりーん。

第6回JOI予選

0510(aoj) : 得点
0511(aoj) : 未提出者は誰だ
0512(aoj) : シーザー暗号
0513(aoj) : カードの並び替え
0514(aoj) : 品質検査
0515(aoj) : 通学経路



0510

やるだけ

// 0510
#include <iostream>
int main()
{
   int a[4],b[4];
   int A,B;
   A=B=0;
   for(int i=0; i<4; i++)std::cin>>a[i],A+=a[i];
   for(int i=0; i<4; i++)std::cin>>b[i],B+=b[i];
   printf("%d\n",A>B?A:B);
   return 0;
}



0511

配列によるハッシュ化、やるだけ

// 0511
#include <iostream>
#include <cstring>
int main()
{
   int number[31];
   memset(number,0,sizeof(number));
   for(int i=0; i<30; i++){
      int a; std::cin>>a;
      number[a] = 1;
   }
   for(int i=1; i<31; i++)
      if( !number[i] )printf("%d\n",i);
   return 0;
}



0512

3文字に決まってるので特に工夫なし、やるだけ。
シーザー暗号と言えば過去にヒドイコードを…。

// 0512
#include <iostream>
#include <cstring>
int main()
{
   char str[1<<10];
   std::cin>>str;
   int n = strlen(str);
   for(int i=0; i<n; i++){
      if( str[i]<'D' ){
         str[i] = str[i]+23;
      }else{
         str[i] = str[i]-3;
      }
   }
   printf("%s\n",str);
   return 0;
}



0513

やるだけ、シミュレーション問題。
ICPC花札シャッフルを思い出した。

// 0513
#include <iostream>
int main()
{
   int n,m,k;
   int card[200];
   int tmp[200];
   std::cin>>n>>m;
   
   for(int i=0; i<200; i++)card[i] = i+1;
   
   for(int i=0; i<m; i++){
      std::cin>>k;
      if( k==0 ){
         int t = 0;
         for(int j=0; t<n;){
            tmp[j] = card[t];
            j++;
            tmp[j] = card[n+t];
            j++;
            t++;
         }
      }else{
         for(int j=0; j<2*n-k; j++)tmp[j]=card[j+k];
         for(int j=0; j<k; j++)tmp[2*n-k+j] = card[j];
      }
      
      for(int j=0; j<2*n; j++)card[j]=tmp[j];

   }
   for(int i=0; i<2*n; i++)
      printf("%d\n",card[i]);
   return 0;
}



0514

幸いなことに部品が3種類固定なので、ある検査結果が不合格のとき、
2種類の部品が正常だと確定したときに限り、最後の部品が故障だと判断できます。
故障だと判断した部品は他の部品に新しい影響を与えません。
よって、正常な部品が2個含まれてる検査リストのみを確認すればいい。

// 0514
#include <iostream>
#include <cstring>
int main()
{
   int a,b,c;
   int N;
   while(std::cin>>a>>b>>c,a|b|c){
      std::cin>>N;
      int data[1024][4];
      int check[301];
      for(int i=0; i<301; i++)check[i]=2;
      for(int i=0; i<N; i++){
         scanf("%d%d%d%d",&data[i][0],&data[i][1],
                          &data[i][2],&data[i][3]);
         if( data[i][3]==1 ){
            check[data[i][0]]=1;
            check[data[i][1]]=1;
            check[data[i][2]]=1;
         }
      }
      for(int i=0; i<N; i++){
         if( data[i][3]==0 ){
            int sum = 0;
            if( check[data[i][0]]==1 )sum++;
            if( check[data[i][1]]==1 )sum++;
            if( check[data[i][2]]==1 )sum++;
            if( sum==2 ){
               for(int j=0; j<3; j++){
                  if( check[data[i][j]]!=1 )
                     check[data[i][j]]=0;
               }
            }
         }
      }
      for(int i=0; i<a+b+c; i++){
         printf("%d\n",check[i+1]);
      }
   }
   return 0;
}



0515

Project Euler15も同様の解法。
アルゴリズマーの記事に全く同じ例題が取り上げられてた。これ

// 0515
#include <iostream>
#include <cstring>
int main()
{
   int H,W,n;
   int mp[18][18];
   int check[18][18];
   
   while(std::cin>>W>>H,W|H){
      memset(mp,0,sizeof(mp));
      memset(check,0,sizeof(check));
      std::cin>>n;
      for(int i=0; i<n; i++){
         int x,y; std::cin>>x>>y;
         check[H-y+1][x] = -1;
      }
      mp[H][1] = 1;
      
      for(int i=H; i>0; i--){
         for(int j=1; j<=W; j++){
            if( check[i][j]==-1 )continue;
            mp[i][j] += mp[i+1][j] + mp[i][j-1];
         }
      }
      printf("%d\n",mp[1][W]);
   }
   return 0;
}