---- *0171 Dice Puzzle http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0171 サイコロを８個組み合わせて、2*2*2の大きなさいころを作るという問題。 サイコロの面同士を合わせる時サイの目に描かれている文字が同じアルファベット大文字と小文字でないといけません。 yとYやaとＡのような組み合わせのみ組み合わせることができます。 解法 良い解法思いつきませんでした。 さいを回転する関数を作り、さいころを回しては追加し深さ優先探索で全探索します。 探索中check関数で今まで組み立てた部分が条件を満たすか調べて枝がりをします。 もっと賢い解法もあると思うので調べてみるとよいでしょう。 #include<stdio.h> #include<stdlib.h> #include<string.h> int ok=abs('A'-'a'); char xais[8][7]; char permXais[8][7]; bool allOK; bool addOKs[8]; bool check(int deep){ int sa1,sa2,sa3; if(allOK==true) return false; if(deep==1){ return abs(permXais[0][2]-permXais[1][3])==ok; }else if(deep==2){ return abs(permXais[0][4]-permXais[2][1])==ok; }else if(deep==3){ sa1=abs(permXais[1][4]-permXais[3][1]); sa2=abs(permXais[2][2]-permXais[3][3]); return (sa1==ok && sa2==ok); }else if(deep==4){ return abs(permXais[4][5]-permXais[0][0])==ok; }else if(deep==5){ sa1=abs(permXais[5][5]-permXais[1][0]); sa2=abs(permXais[5][3]-permXais[4][2]); return (sa1==ok && sa2==ok); }else if(deep==6){ sa1=abs(permXais[6][5]-permXais[2][0]); sa2=abs(permXais[6][1]-permXais[4][4]); return (sa1==ok && sa2==ok); }else if(deep==7){ sa1=abs(permXais[7][5]-permXais[3][0]); sa2=abs(permXais[7][1]-permXais[5][4]); sa3=abs(permXais[7][3]-permXais[6][2]); return (sa1==ok && sa2==ok && sa3==ok); } return true; } bool flatRound(char* xai,int deep){ char t=xai[2]; xai[2]=xai[1]; xai[1]=xai[3]; xai[3]=xai[4]; xai[4]=t; return check(deep); } bool northRound(char* xai,int deep){ char t=xai[0]; xai[0]=xai[1]; xai[1]=xai[5]; xai[5]=xai[4]; xai[4]=t; return check(deep); } bool eastRound(char* xai,int deep){ char t=xai[0]; xai[0]=xai[3]; xai[3]=xai[5]; xai[5]=xai[2]; xai[2]=t; return check(deep); } void saiki(int deep){ if(deep==8){ allOK=true; return; } char temp[7]; for(int k=0;k<8;k++){ if(addOKs[k]==true){ addOKs[k]=false; memcpy(&permXais[deep],&xais[k],7); for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ if(flatRound(permXais[deep],deep))saiki(deep+1); if(allOK==true) return; } northRound(permXais[deep],deep); } eastRound(permXais[deep],deep); for(int i=0;i<4;i++){ if(flatRound(permXais[deep],deep))saiki(deep+1); if(allOK==true) return; } for(int i=0;i<2;i++){ northRound(permXais[deep],deep); } for(int i=0;i<4;i++){ if(flatRound(permXais[deep],deep))saiki(deep+1); if(allOK==true) return; } addOKs[k]=true; } } } bool setData(){ scanf("%s",&xais[0]); if(xais[0][0]=='0') return false; memset(addOKs,true,8); for(int i=1;i<8;i++){ scanf("%s",&xais[i]); } allOK=false; saiki(0); printf("%s\n",allOK?"YES":"NO"); return true; } int main(){ while(setData()==true){ } } ---- *0173 Haunted House http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0173 午前と午後のお化け屋敷の入場者数から総入場者数と売り上げを出力せよという問題。 解法 簡単な問題なのでただ書くだけです。 午前と午後の違いに注意するくらいです。 #include<stdio.h> int main(){ char name[16]; int m,n; while(scanf("%s %d %d",name,&m,&n)!=EOF){ printf("%s %d %d\n",name,n+m,n*300+m*200); } } ---- *0174 Badminton http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0174 バトミントンのサーブ記録から試合の得点を求めよという問題です。 解法 データの条件を試合終了時必ず2点差ついていると読みかえますと、最後まで計算した時得点の多い方に一点足せば最後の一点の計算ができます。 それが分かれば後はサーブ記録から互いに１点ずつ計算するだけです。 #include<stdio.h> bool calc(){ char serve[101]; int score[2],p; for(int i=0;i<3;i++){ scanf("%s",serve); if(serve[0]=='0') return false; p=1; score[0]=score[1]=0; while(serve[p]!='\0'){ score[serve[p]-'A']++; p++; } score[score[0]>score[1]?0:1]++; printf("%d %d\n",score[0],score[1]); } return true; } int main(){ while(calc()){ } } ---- *0175 A King in Hawaii http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0175 １０進数を４進数に変換せよという問題。 解法 m進数を表現する時はｍの余りを取りｍで割ってそれを文字列として保存して逆順に出力すれば何進数への変換であっても普遍的に計算できます。 #include<stdio.h> int main(){ int n,p; char ans[20]; while(1){ scanf("%d",&n); if(n==-1) break; p=0; if(n==0){ ans[0]='0'; p++; } while(n>0){ ans[p]=n%4+'0'; n/=4; p++; } for(int i=p-1;i>=0;i--){ printf("%c",ans[i]); } printf("\n"); } } ---- *0176 What Color? http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0176 カラー表が与えられます。 色データがＲＧＢで与えられるので、カラー表の中でその色に最も近い色返すという問題。 解法 書いてある通りに上から実装します。 問題分の指定ではｓｑｒｔを使っていますが重要なのは色の距離だけなので、距離を２乗のまま扱うと計算が楽になります。 #include<stdio.h> struct color{ int r,g,b; }; double colorLen2(color c1,color c2){ return (c1.r-c2.r)*(c1.r-c2.r)+(c1.g-c2.g)*(c1.g-c2.g)+(c1.b-c2.b)*(c1.b-c2.b); } int main(){ color colors[8]={ {0,0,0},{0,0,255},{0,255,0},{0,255,255} ,{255,0,0}, {255,0,255},{255,255,0},{255,255,255}}; char colorNames[8][8]={"black","blue","lime","aqua", "red","fuchsia","yellow","white"}; color c; char top; int ans,len,tempLen; while(1){ scanf("%c",&top); if(top=='0') break; scanf("%2x%2x%2x%c",&c.r,&c.g,&c.b,&top); ans=0; len=colorLen2(c,colors[0]); for(int i=1;i<8;i++){ tempLen=colorLen2(c,colors[i]); if(len>tempLen){ len=tempLen; ans=i; } } printf("%s\n",colorNames[ans]); } } ---- *0179 Mysterious Worm http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0179 一定のルールの下時間とともに体の各部分の体色を変化させていく虫がいるので、この虫が同じ色に落ち着くまでのターン数を答えよという問題。 解法 シミュレートして、虫の体色変化を幅優先探索で追いかけるだけで解決できます。 この問題を答えた人のデータを見るとコードの実行速度やコードサイズやメモリ使用量が人によって違うので色々な解法があるのかもしれません。 調べてみるとよいかもしれません。 #include<stdio.h> #include<queue> #include<string.h> #include<set> struct Worm{ char body[11]; int turn; bool operator<(const Worm w)const{ for(int i=0;i<10;i++){ if(body[i]!=w.body[i]) return body[i]<w.body[i]; } return false; } }; bool allOK(char body[11]){ char color=body[0]; int p=1; while(body[p]!='\0'){ if(color!=body[p]) return false; p++; } return true; } char changeColor(char t1,char t2){ char ans[3][4]={".bg","b.r","gr."}; int x,y; if(t1=='r')x=0; if(t1=='g')x=1; if(t1=='b')x=2; if(t2=='r')y=0; if(t2=='g')y=1; if(t2=='b')y=2; return ans[y][x]; } void calc(char wormBody[11]){ std::queue<Worm> worms; std::set<Worm> memo; Worm w,nextW; memcpy(w.body,wormBody,11); w.turn=0; worms.push(w); memo.insert(w); int wormSize=strlen(wormBody); char color; while(!worms.empty()){ w=worms.front(); nextW=worms.front(); if(allOK(w.body)){ printf("%d\n",w.turn); return; } nextW.turn++; worms.pop(); for(int i=0;i<wormSize-1;i++){ if(w.body[i]!=w.body[i+1]){ color=changeColor(w.body[i],w.body[i+1]); nextW.body[i]=nextW.body[i+1]=color; if(memo.find(nextW)==memo.end()){ memo.insert(nextW); worms.push(nextW); } nextW.body[i]=w.body[i]; nextW.body[i+1]=w.body[i+1]; } } } printf("NA\n"); } int main(){ char wormBody[11]; while(1){ scanf("%s",wormBody); if(wormBody[0]=='0') break; calc(wormBody); } }
