「AOJ121～130」の編集履歴（バックアップ）一覧に戻る
AOJ121～130 - (2011/08/23 (火) 18:17:22) のソース
----
*0121 Seven Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0121
7パズルの盤面が与えられます。
盤面を完成させるには最短で何手必要かを答える問題。
解法
最初に7パズルの全ての組み合わせを求めて何手で到達できるかを計算して求めます。
コードでは高速化のため7パズルの並びを右上から精査して並べたものを数字列とみなして管理します。
数字の並びに0の位置を末尾に付け加えて管理します。
#include<stdio.h>
#include<queue>
#include<map>
int mod[]={100000000,10000000,1000000,100000,10000,1000,100,10};
int dxs[]={1,4,-1,-4};
int main(){
int num,next,p,np,dell,turn;
std::queue<int> qu;
std::map<int,int> memo;
qu.push(12345670);
memo[1234567]=0;
while(qu.empty()==false){
num=qu.front();
turn=memo[num/10];
qu.pop();
for(int i=0;i<4;i++){
p=num%10;
np=p+dxs[i];
if(np<0 || 7<np || (np==3 && p==4)||(np==4 && p==3))continue;
dell=((num/mod[np])%10);
next=(num-dell*mod[np]+dell*mod[p])-num%10+np;
if(memo.find(next/10)==memo.end()){
qu.push(next);
memo[next/10]=turn+1;
}
}
}
int n;
while(scanf("%d",&n)!=EOF){
for(int i=1;i<8;i++){
scanf("%d",&p);
n=n*10+p;
}
if(memo.find(n)!=memo.end()){
printf("%d\n",memo[n]);
}
}
}
----
*0122 Summer of Phyonkichi
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122
カエルのぴょん吉が、暑い夏の盛りを生き残れるかを答える問題。
ぴょん吉はジャンプしてスプリンクラーからスプリンクラーの散水へと移動します。
もしスプリンクラーの散水範囲に入れない場合暑さで死んでしまいます。
スプリンクラーの散水順序とぴょん吉の位置が与えられるので生き残れるかを答えるという問題です。
解法
1手ずつジャンプしてスプリンクラーの範囲に入れるか深さ優先探索で調べていくだけです。
非常に簡単な問題なので気楽に挑戦してください。
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
int dxs[]={2,2,1,0,-1,-2,-2,-2,-1,0,1,2};
int dys[]={0,1,2,2,2,1,0,-1,-2,-2,-2,-1};
int px[]={-1,0,1,-1,0,1,-1,0,1};
int py[]={-1,-1,-1,0,0,0,1,1,1};
void setMap(int x,int y){
int nx,ny,ox=x,oy=y,jx,jy,count,n,xx,yy;
scanf("%d",&n);
int map[10][10],nMap[10][10];
memset(map,0,400);
memset(nMap,0,400);
map[y][x]=1;
for(int i=0;i<n;i++){
scanf("%d %d",&nx,&ny);
count=0;
for(int j=0;j<9;j++){
jx=ox+px[j];
jy=oy+py[j];
if(jx<0 || 9<jx || jy<0 || 9<jy || map[jy][jx]==0) continue;
for(int k=0;k<12;k++){
xx=jx+dxs[k];
yy=jy+dys[k];
if(xx<0 || 9<xx || yy<0 || 9<yy) continue;
if(abs(xx-nx)<2 && abs(yy-ny)<2){
nMap[yy][xx]=1;
count++;
}
}
}
memcpy(map,nMap,400);
memset(nMap,0,400);
ox=nx;
oy=ny;
}
if(count>0){
printf("OK\n");
}else{
printf("NA\n");
}
}
int main(){
int x,y;
while(1){
scanf("%d %d",&x,&y);
if(x==0 && y==0) break;
setMap(x,y);
}
}
----
*0123 Speed Skating Badge Test
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0123
アイススケートのタイムが与えられます。
タイムから選手のランク付けをする問題です。
解法
データをマトリクスに書いて、後はループで判定するだけです。
#include <stdio.h>
int main(void)
{
char kekka[8][4]={"AAA","AA","A","B","C","D","E","NA"};
double times500[7]={35.5, 37.5, 40, 43, 50, 55 ,70},
times1000[7]={71, 77, 83, 89, 105, 116,148},
t1,t2;
int r1,r2;
while(scanf("%lf %lf",&t1,&t2)>0){
r1=r2=7;
for(int i=6;i>=0;i--){
if(t1<times500[i]){
r1=i;
}
if(t2<times1000[i]){
r2=i;
}
}
printf("%s\n",r1>r2?kekka[r1]:kekka[r2]);
}
}
----
*0124 League Match Score Sheet
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0124
スポーツの勝敗データからチームをランク付けして出力する問題。
解法
構造体を定義してソート基準を指定するだけです。
実装が楽なのでoperator<を定義しましたが、ソート用クラスを使るのが正しい方法だと思います。
#include<stdio.h>
#include <algorithm>
struct team{
char name[21];
int score,no;
bool operator<(const team t)const{
if(score!=t.score) return score>t.score;
return no<t.no;
}
};
void setData(int n){
team t[11];
int v,d,l;
for(int i=0;i<n;i++){
scanf("%s %d %d %d",t[i].name,&v,&l,&d);
t[i].no=i;
t[i].score=v*3+d;
}
std::sort(t,t+n);
for(int i=0;i<n;i++){
printf("%s,%d\n",t[i].name,t[i].score);
}
}
int main(){
int n,first=0;
while(1){
scanf("%d",&n);
if(n==0)break;
if(first==0){
first=1;
}else{
printf("\n");
}
setData(n);
}
}
----
*0125 Day Count
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0125
２つの日付が与えられるので、その日数の差分を計算する問題です。
解法
フェアフィールドの公式をそのまま使います。
公式を使えない場合日付マトリックスを使うことになるかＪavaのカレンダークラスを使うとよいでしょう。
#include<stdio.h>
#include<stdlib.h>
int f(int y,int m,int d){
if(m<3){
m+=12;
y--;
}
return 365*y+y/4-y/100+y/400+(306*(m+1))/10+d-428;
}
int main(){
int y,m,d,yy,mm,dd;
while(1){
scanf("%d %d %d %d %d %d",&y,&m,&d,&yy,&mm,&dd);
if(y<0 || m<0 || d<0 || yy<0 || mm<0 || dd<0) break;
printf("%d\n",abs(f(y,m,d)-f(yy,mm,dd)));
}
}
----
*0126 Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0126
数独を解いた結果が表として与えられます。
表からルール違反（数字が重複している)の部分を縦列、横列、3*3マスで調べてその部分を表示するという問題。
解法
丁寧に調べるだけです。
コードでは縦横３*３マスのチェック手順をマトリックス化しています。
優秀な人ならＢｉｔ演算などでもっと簡単に解くと思います。
#include<stdio.h>
#include<string.h>
int sp[9]={0,3,6,27,30,33,54,57,60};
int cp[9]={0,1,2,9,10,11,18,19,20};
void setMap(){
char map[9][9],ans[9][9];
memset(ans,' ',81);
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
scanf(" %c",&map[i][j]);
}
}
int px1,py1,px2,py2;
for(int i=0;i<9;i++){
for(int j=0;j<8;j++){
for(int k=j+1;k<9;k++){
//縦チェック
if(map[j][i]==map[k][i]){
ans[j][i]=ans[k][i]='*';
}
//3*3チェック
px1=sp[i]%9+cp[j]%9;
py1=sp[i]/9+cp[j]/9;
px2=sp[i]%9+cp[k]%9;
py2=sp[i]/9+cp[k]/9;
//printf("<%d %d %d %d>",px1,py1,px2,py2);
if(map[py1][px1]==map[py2][px2]){
ans[py1][px1]=ans[py2][px2]='*';
}
//横チェック
if(map[i][j]==map[i][k]){
ans[i][j]=ans[i][k]='*';
}
}
}
}
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
printf("%c%c",ans[i][j],map[i][j]);
}
printf("\n");
}
}
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
setMap();
printf("%s",n-1==i?"":"\n");
}
}
----
*0127 Pocket Pager Input
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0127
ポケットベルの数字列を文字列に戻すという問題。
解法
memoの表と対応しながら出力していくだけです。
#include<stdio.h>
#include<string.h>
char memo[6][6]={"abcde","fghij","klmno","pqrst","uvwxy","z.?! "};
int main(){
char mes[201],ans[101];
int p,len,t1,t2;
while(scanf("%s",mes)!=EOF){
len=strlen(mes);
p=0;
if(len%2==0){
while(p<len){
t1=mes[p];
t2=mes[p+1];
if(t1<'1' || '6'<t1 || t2<'1' || '5'<t2){
break;
}else{
ans[p/2]=memo[t1-'1'][t2-'1'];
p+=2;
}
}
}
ans[len/2]='\0';
printf("%s\n",p>=len?ans:"NA");
}
}
----
*0128 Abacus
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0128
与えられた数字をそろばんの盤面に直して表示するという問題です。
解法
change関数でそろばんの各桁を削り出して配列に入れます。
後は縦横を入れ替えて表示します。
#include<stdio.h>
#include<string.h>
void change(int num,char* re){
strcpy(re,"**=*****");
re[-(num/5-1)]=' ';
re[num%5+3]=' ';
}
int main(){
char re[9];
char ans[5][9];
int n,c=0;
while(scanf("%d",&n)!=EOF){
printf("%s",c==0?"":"\n");
c++;
for(int i=4;i>=0;i--){
change(n%10,re);
strcpy(ans[i],re);
n/=10;
}
for(int i=0;i<8;i++){
for(int j=0;j<5;j++)printf("%c",ans[j][i]);
printf("\n");
}
}
}
----
*0129 Hide-and-Seek Supporting System
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0129
かくれんぼで鬼の位置と自分の位置、壁の位置が与えられるので、鬼と自分の間に壁があればSafe、壁がなければDanger
と表示する問題。
解法
壁の数が多く大変に思えますが一つ一つの壁を個別に処理するという観点でみれば簡単な問題です。
色々な解き方があると思います。
好みで解けばよいと思います。
サンプルコードがふくらんだので、コードを短くできないかと手短な判別式を書いてみました。
正射影の概念をつかった解法で未テストです。
http://www14.atwiki.jp/c21coterie/?cmd=upload&act=open&page=AOJ121%EF%BD%9E130&file=0129Hide-and-SeekSupportingSystem4.txt
#include<stdio.h>
#include <math.h>
bool inSeeCheck(int taroX,int taroY,int oniX,int oniY,int wallXs[101],int wallYs[101],int wallRs[101],int n);
void setData(int n);
int main()
{
int n;
scanf("%d",&n);
while(n!=0){
setData(n);
scanf("%d",&n);
}
}
void setData(int n){
int wallXs[101],wallYs[101],wallRs[101];
int taroX,taroY,oniX,oniY;
for(int i=0;i<n;i++){
scanf("%d %d %d",&wallXs[i],&wallYs[i],&wallRs[i]);
}
int m;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d %d %d %d",&taroX,&taroY,&oniX,&oniY);
if(inSeeCheck(taroX,taroY,oniX,oniY,wallXs,wallYs,wallRs,n)==false){
printf("Safe\n");
}else{
printf("Danger\n");
}
}
}
bool inSeeCheck(int taroX,int taroY,int oniX,int oniY,int wallXs[101],int wallYs[101],int wallRs[101],int n){
//同じ円筒内にいるかいないかのチェック
int len1,len2,lenR;
int a=oniY-taroY;
int b=oniX-taroX;
int c=-a*taroX+b*taroY;
int len;
int q,p;
for(int i=0;i<n;i++){
len1=(taroX-wallXs[i])*(taroX-wallXs[i])+(taroY-wallYs[i])*(taroY-wallYs[i]);
len2=(oniX-wallXs[i])*(oniX-wallXs[i])+(oniY-wallYs[i])*(oniY-wallYs[i]);
lenR=wallRs[i]*wallRs[i];
if((len1>lenR && lenR>len2) || (len2>lenR && lenR>len1)){
//両者が違う円の中にいた
//printf("%d %d",len1,len2);
return false;
}else if(len1>lenR && len2>lenR){
//両者が円の外にいてその円で視線がさえぎられるかどうか
len=a*wallXs[i]-b*wallYs[i]+c;
len=(len*len);
//printf("<%d>",len);
if(len<=lenR*(a*a+b*b)){
//printf("A");
q=b*taroX+a*taroY-(a*wallYs[i]+b*wallXs[i]);
p=b*oniX+a*oniY-(a*wallYs[i]+b*wallXs[i]);
if(p*q<0){
//printf("B");
return false;
}
}
}
}
return true;
}
----
*0130 Train
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0130
電車の車掌さんが番号のついた電車を左右に移動した記録があります。
この記録から電車の並びを再現するという問題。
解法
26両以上ないので60個の配列の真ん中から初めて、左右に移動するたびに左右の車両の番号を記録していくだけです。
#include<stdio.h>
#include<string.h>
void calc(){
char train[60],p=30,t,u;
memset(train,'\0',60);
scanf("%c",&train[p]);
while(1){
scanf("%c",&t);
if(t=='\n')break;
scanf("%c%c",&t,&u);
p+=t=='>'?1:-1;
train[p]=u;
}
for(int i=0;i<60;i++){
if(train[i]!='\0') printf("%c",train[i]);
}
printf("\n");
}
int main(){
int n;
char t;
scanf("%d%c",&n,&t);
for(int i=0;i<n;i++){
calc();
}
}
