「AOJ121～130」の編集履歴（バックアップ）一覧はこちら
AOJ121～130 - (2011/08/18 (木) 15:47:14) の１つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
----
*0121 Seven Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0121
実行速度と分かりやすさのバランスをとって結局こういうコードになった。
このコードなら中学生でもわかるかも。
#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]);
}
}
}
----
*0121
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122
データの読み込みでポカミスをして2連続不正解という大馬鹿をしてしまう。
こんな簡単な問題でポカミスのせいで間違うなんてもったいない。
サンプルデータもポカミスに気付けないように出来ているのがあざとい。
簡単な問題と思って侮りすぎた。
#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
この問題200byte以下で書けるらしい、、、、どうやってるんだろ？
#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
何の工夫もなく実装するだけ。
#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
9^3通りより少し少ないチェック領域力づくで求める。
縦横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");
}
}
----
*0121 Seven Puzzle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0121
実行速度と分かりやすさのバランスをとって結局こういうコードになった。
このコードなら中学生でもわかるかも。
#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]);
}
}
}
----
*0121
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122
データの読み込みでポカミスをして2連続不正解という大馬鹿をしてしまう。
こんな簡単な問題でポカミスのせいで間違うなんてもったいない。
サンプルデータもポカミスに気付けないように出来ているのがあざとい。
簡単な問題と思って侮りすぎた。
#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
この問題200byte以下で書けるらしい、、、、どうやってるんだろ？
#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
何の工夫もなく実装するだけ。
#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
9^3通りより少し少ないチェック領域力づくで求める。
縦横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");
}
}
