「AOJ171~180」の編集履歴(バックアップ)一覧はこちら
AOJ171~180 - (2011/08/26 (金) 18:15:43) の1つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
----
*0171 Dice Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0171
サイコロを8個組み合わせて、2*2*2の大きなさいころを作るという問題。
サイコロの面同士を合わせる時サイの目に描かれている文字が同じアルファベット大文字と小文字でないといけません。
yとYやaと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点差ついていると読みかえますと、最後まで計算した時得点の多い方に一点足せば最後の一点の計算ができます。
それが分かれば後はサーブ記録から互いに1点ずつ計算するだけです。
#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()){
}
}
----
*0176 What Color?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0176
カラー表が与えられます。
色データがRGBで与えられるので、カラー表の中でその色に最も近い色返すという問題。
解法
書いてある通りに上から実装します。
問題分の指定ではsqrtを使っていますが重要なのは色の距離だけなので、距離を2乗のまま扱うと計算が楽になります。
#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]);
}
}
----
*0171 Dice Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0171
サイコロを8個組み合わせて、2*2*2の大きなさいころを作るという問題。
サイコロの面同士を合わせる時サイの目に描かれている文字が同じアルファベット大文字と小文字でないといけません。
yとYやaと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点差ついていると読みかえますと、最後まで計算した時得点の多い方に一点足せば最後の一点の計算ができます。
それが分かれば後はサーブ記録から互いに1点ずつ計算するだけです。
#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
10進数を4進数に変換せよという問題。
解法
m進数を表現する時はmの余りを取り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
カラー表が与えられます。
色データがRGBで与えられるので、カラー表の中でその色に最も近い色返すという問題。
解法
書いてある通りに上から実装します。
問題分の指定ではsqrtを使っていますが重要なのは色の距離だけなので、距離を2乗のまま扱うと計算が楽になります。
#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]);
}
}