AOJ101～110

101 Aizu PR

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0101&lang=jp
文章に記述ミスがあり、Hoshinaと書くところをHoshinoと書いてしまいました。
文章が与えられるのでミスを全て訂正した文章を出力してくださいという問題。
解法
string型に関する基本機能を理解しているか問われるだけの問題です。

#include<iostream>
#include<string>
int main(){
std::string s;
int n;
char c;
unsigned int pos;
std::cin>>n;
std::getline(std::cin,s);
for(int i=0;i<n;i++){
	std::getline(std::cin,s);
	pos=0;
	while(1){
		pos=s.find("Hoshino",pos);
		if(pos==std::string::npos) break;
		s.replace(pos,7,"Hoshina");
	}
	std::cout<<s<<"\n";
}
}

0102　Matrix-like Computation

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0102&lang=jp
数字の表が与えられるので縦計横計総計を付け加えて表示し直してくださいという問題。
解法
普通に計算して表示するだけです。

#include<stdio.h>
void setMap(int n){
int tate[11]={0},yoko=0,p,sum=0;
for(int i=0;i<n*n;i++){
	scanf("%d",&p);
	yoko+=p;
	tate[i%n]+=p;
	sum+=p;
	printf("%5d",p);
	if(i%n==n-1){
		printf("%5d\n",yoko);
		yoko=0;
	}
}
for(int i=0;i<n;i++){
	printf("%5d",tate[i]);
}
printf("%5d\n",sum);
}
int main(){
int n;
while(1){
	scanf("%d",&n);
	if(n==0)break;
	setMap(n);
}
}

0103 Baseball Simulation

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0103
野球ゲームのゲーム記録から得点を再現するという問題。
ルールも簡素化されています。

解法
書いてある通りに実装するだけです。
実はこの問題、ランナーは一塁にいる、１２塁にいる123塁にいるというパタンしか取らないのでランナーの人数は変数一つで片が付くようです。
他の方のコードを参考にしてみてください。

#include<iostream>
#include<string>
void sym(){
std::string eve;
int out=0,score=0,b[3]={0};
while(out<3){
	std::cin>>eve;
	if(eve=="HIT"){
		score+=b[2];
		b[2]=b[1];
		b[1]=b[0];
		b[0]=1;
	}else if(eve=="HOMERUN"){
		score+=b[2]+b[1]+b[0]+1;
		b[2]=b[1]=b[0]=0;
	}else if(eve=="OUT"){
		out++;
	}
}
std::cout<<score<<"\n";
}
int main(){
int n,tern=0;
std::cin>>n;
while(tern<n){
	sym();
	tern++;
}
}

0104　Magical Tiles

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0104&lang=jp
ドラクエ4の滑る床と同じシステムで移動します。
滑る床のマップが与えられるのでスタート地点から初めてどの地点に到達するか、もしくは永久ループするか出力せよという問題。
解法
外に出ないのでエラー処理がいりません。
書いてある通りに実装し、一度通った部分を記録しておくだけです。
一度通った部分に到達すればＬｏｏpしますし、床に到達すればそこがゴールです。

#include<stdio.h>
void setMap(int h){
char map[101][101],t;
for(int i=0;i<h;i++){
	scanf("%s",map[i]);
}
int x=0,y=0;
while(map[y][x]!='.' && map[y][x]!=0){
	t=map[y][x];
	map[y][x]=0;
	if(t=='>'){
		x++;
	}else if(t=='v'){
		y++;
	}else if(t=='<'){
		x--;
	}else if(t=='^'){
		y--;
	}
}
if(map[y][x]==0){
	printf("LOOP\n");
}else{
	printf("%d %d\n",x,y);
}
}
int main(){
int w,h;
while(1){
	scanf("%d %d",&h,&w);
	if(w==0 && h==0) break;
	setMap(h);
}
}

下記は上記コードをショートコーディングにしようとしたコードです。

#include<stdio.h>
void setMap(int h){
char map[101][101],t;
for(int i=0;i<h;i++){
	scanf("%s",map[i]);
}
int x=0,y=0,t=map[0][0];
while(t!='.' && t!=0){
	t=map[y][x];
	map[y][x]=0;
	x+=(t=='>')-(t=='<');
	y+=(t=='v')-(t=='^');
	t=map[y][x];
}
if(t==0){
	printf("LOOP\n");
}else{
	printf("%d %d\n",x,y);
}
}
int main(){
int w,h;
while(1){
	scanf("%d %d",&h,&w);
	if(w==0 && h==0) break;
	setMap(h);
}
}

0105　Book Index

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0105&lang=jp
ある本でどの単語がどのページに出ているかの対応表が与えれます。
単語ごとに整理してインデックスを出力してくださいという問題。

解法
c++のコンテナやjavaのコンテナを基本レベルで使えるかどうかを問うだけの問題です。
コードを短くしたり短縮テクニックを使ったりせず読みやすいコード重視で書いてみた。

#include<string>
#include<map>
#include<set>
int main(){
std::map<std::string,std::set<int> > index;
std::set<int> dSet;
char word[31];
int page;
while(scanf("%s %d",word,&page)!=EOF){
       if(index.find(word)==index.end()){
           index[word]=dSet; 
       }
       index[word].insert(page);
   }
   std::map<std::string,std::set<int> >::iterator it=index.begin();
   std::set<int>::iterator itPage;
   int f;
   while(it!=index.end()){
       printf("%s\n",(*it).first.c_str ());
       itPage=(*it).second.begin();
       f=0;
       while(itPage!=(*it).second.end()){
           printf("%s%d",f==0?"":" ",(*itPage));
           f=f==0?1:f;
           itPage++;
       }
       printf("\n");
       it++;
   }
}

0106　Discounts of Buckwheat

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0106&lang=jp
Ａ店Ｂ店Ｃ店3つの店をめぐってそば粉を買います。
そばは店ごとに量と値段が違いまとめ買いすると割引をしてくれます。
必要なそば粉の量が与えられるので、割引も利用して3店をめぐってもっとも安い購入をしたときの金額を出力せよという問題。

解法
典型的なナップザック法の問題です。
そば粉を200ｇ、300ｇ、500ｇ、まとめ買いをした1000ｇ、1200ｇ、1500ｇ単位でナップザック法で入れていけば答えがもとまります。
解法はhttp://d.hatena.ne.jp/kyuridenamida/20100810/1281440693を参考にしました。

#include<stdio.h>
#include <algorithm>
int main(){
int max=1<<30;
int memo[51];
int ws[6]={2,3,5,10,12,15};
int ps[6]={380,550,850,1520,1870,2244};
for(int i=0;i<51;i++) memo[i]=max;
memo[0]=0;
for(int i=0;i<51;i++){
	for(int j=0;j<6;j++){
		if(i+ws[j]>50) break;
		memo[i+ws[j]]=std::min(memo[i+ws[j]],memo[i]+ps[j]);
	}
}
int n;
while(1){
	scanf("%d",&n);
	if(n==0) break;
	printf("%d\n",memo[n/100]);
}
}

0107 Carry a Cheese

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0107&lang=jp
直方体のチーズが半径ｒの円形の穴に入るか調べ、入るならＯＫ入らないならＮＡと出力せよという問題。
解法
直方体のどれかの辺が穴と垂直になるように入れるということに気づけば簡単な問題です。
t=a*a+b*b+c*c-t*t;はちょっと嬉しいコードなので読んでみてください。

#include <stdio.h>
#include <algorithm>
int main(){
int a,b,c;
int t,n,r;
scanf("%d %d %d",&a,&b,&c);
while(a!=0 || b!=0 || c!=0){
	t=std::max(std::max(a,b),c);
	t=a*a+b*b+c*c-t*t;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&r);
		if(t<r*r*4){
			printf("OK\n");
		}else{
			printf("NA\n");
		}
	}
	scanf("%d %d %d",&a,&b,&c);
}
}

0108 Operation of Frequency of Appearance

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0108&lang=jp
与えられた数列に出現頻度操作を加えつづけ、何回の操作で不動点に到達するかを答える問題。
詳しくは問題に書いてあります。
解法
数列が短いためすぐに収束することが予想されます。
書いてある通りの操作をシミュレートするだけです。
計算量的にいって何の工夫もいりません。

#include<stdio.h>
#include<map>
void calc(int m[13],int n){
std::map<int,int> memo;
int ans,count=0;
bool goal=false;
while(goal==false){
	memo.clear();
	goal=true;
	for(int i=0;i<n;i++){
		if(memo.find(m[i])==memo.end()){
			memo[m[i]]=1;
		}else{
			memo[m[i]]++;
		}
	}
	for(int i=0;i<n;i++){
		if(m[i]!=memo[m[i]]){
			goal=false;
		}
		m[i]=memo[m[i]];
	}
	count++;
}
printf("%d\n%d",count-1,m[0]);
for(int i=1;i<n;i++){
	printf(" %d",m[i]);
}
printf("\n");
}
int main(){
int n,m[13];
while(1){
	scanf("%d",&n);
	if(n==0) break;
	for(int i=0;i<n;i++) scanf("%d",&m[i]);
	calc(m,n);
}
}

0109 Smart Calculator

数式が与えられるのでその数式を解釈して計算結果を表示せよという問題。

解法
数式を評価する命令を使えば一発ですがアルゴリズムの勉強ということで地道に解いてみました。
式を逆ポーランド記法に並べ直して解きます。
再帰下降構文解析というもう一段賢い解法もあるそうで、そちらだとプログラムが驚くほどすっきりと短くなるそうです。
調べてみるとよいでしょう。

#include<stdio.h>
#include<stack>
#include<queue>
#include<string.h>
#include<map>
std::map<char,int> symbolRank;
struct symbol{
union data{
	int num;
	char kigou;
}d;
int type;
};
void set(char *text){
int p=0;
std::queue<symbol> siki;
std::stack<char> kigous;
std::stack<int> calc;
char t,t2;
int num,mod=1,nextTypeNum=1,nextTypeSymbol=0,typeNum=1,typeSymbol=0,u;
symbol s;
symbolRank['(']=0;
symbolRank['+']=1;
symbolRank['-']=1;
symbolRank['*']=2;
symbolRank['/']=2;
	while(text[p]!='='){
	t=text[p];
	if(t=='('){
		kigous.push(t);
		p++;
		mod=nextTypeNum;//次は数字
	}else if(t==')'){
		while(kigous.top()!='('){
			s.d.kigou=kigous.top();
			kigous.pop();
			s.type=typeSymbol;
			siki.push(s);
		}
		kigous.pop();
		mod=nextTypeSymbol;//次は記号
		p++;
	}else if(mod==nextTypeSymbol){
		if(kigous.empty()==true){
			kigous.push(t);
		}else{
			while(1){
				if(kigous.empty()==true){
					kigous.push(t);
					break;
				}
				t2=kigous.top();
				if(symbolRank[t2]>=symbolRank[t]){
					kigous.pop();
					s.d.kigou=t2;
					s.type=typeSymbol;
					siki.push(s);
				}else{
					kigous.push(t);
					break;
				}
			}
		}
		mod=nextTypeNum;
		p++;
	}else if(mod==nextTypeNum){
		mod=nextTypeSymbol;
		if(t=='-'){
			u=-1;
			p++;
			t=text[p];
		}else{
			u=1;
		}
		num=0;
		while('0'<=t && t<='9'){
			num*=10;
			num+=(t-'0');
			p++;
			t=text[p];
		}
		if(num==0 && u==-1){
			s.d.num=-1;
			s.type=typeNum;
			siki.push(s);
			if(kigous.empty()==true){
				kigous.push('*');
			}else{
				if(symbolRank['*']<=symbolRank[kigous.top()]){
					s.d.kigou=kigous.top();
					kigous.pop();
					kigous.push('*');
					s.type=typeSymbol;
					siki.push(s);
				}else{
					kigous.push('*');
				}
			}
			
		}else{
			s.d.num=num*u;
			s.type=typeNum;
			siki.push(s);
			mod=nextTypeSymbol;
		}
	}
}
s.type=typeSymbol;
while(kigous.empty()==false){
	s.d.kigou=kigous.top();
	kigous.pop();
	siki.push(s);
}
/*
   while(siki.empty()==false){
       s=siki.front();  
       if(s.type==typeSymbol){
           printf("%c ",s.d.kigou);
       }else{
           printf("%d ",s.d.num);
       }
       siki.pop();
   }
   */
   while(siki.empty()==false){
   	s=siki.front();
   	siki.pop();
   	if(s.type==typeNum){
   		calc.push(s.d.num);
   	}else{
   		int t3,s3,ans;
   		char t4;
   		t3=calc.top();
   		calc.pop();
   		s3=calc.top();
   		calc.pop();
   		t4=s.d.kigou;
   		if(t4=='+'){
   			ans=s3+t3;
   		}else if(t4=='-'){
   			ans=s3-t3;
   		}else if(t4=='*'){
   			ans=s3*t3;
   		}else if(t4=='/'){
   			ans=s3/t3;
   		}
   		calc.push(ans);
   	}
   }
   printf("%d\n",calc.top());
}
int main(){
//int ttt=(int)77/(int)8/(int)4*((int)4/(int)3*(int)2)*(int)74/(int)5;
//printf("%d\n",ttt);

char text[101];
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
	scanf("%s",text);
	set(text);
}
}

0110 Alphametic

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0110
a+b=cという形の覆面算を解けという問題。
解法
式の中に現れる文字がＸと数字しかなく問題は簡単です。
Ｘに0～9の9通りを入れて一つずつ試してみるだけです。

#include<stdio.h>
#include<string.h>
void setNum(char *t,char *nt,int num){
   int len=strlen(t);
   memset(nt,0,127);
   for(int i=0;i<len;i++){
       nt[127-len+i]=t[i]=='X'?num:t[i]-'0';
   }
}
void calc(char text[127]){
char a[127],b[127],c[127],t;
char na[127],nb[127],nc[127],s=0;
bool hit;

sscanf(text,"%[^+]%c%[^=]%c%s",a,&t,b,&t,c);

if((a[0]=='X' && a[1]!='\0') || (b[0]=='X' && b[1]!='\0') ||( c[0]=='X' && c[1]!='\0')) s=1;
for(int i=s;i<10;i++){
       setNum(a,na,i);
       setNum(b,nb,i);
       setNum(c,nc,i);
    int up=0,sum;
	hit=true;
	for(int j=126;j>=0;j--){
		sum=na[j]+nb[j]+up;
		if(nc[j]!=sum%10){
			hit=false;
			break;
		}
		up=sum/10;
	}
	if(hit==true){
		printf("%d\n",i);
		return;
	}
}
printf("NA\n");
}
int main(){
char text[127];
while(scanf("%s",text)!=EOF){
	calc(text);
}
}

タグ：

+ タグ編集

「AOJ101～110」をウィキ内検索

最終更新：2011年09月06日 10:47

c21coterie @ ウィキ

更新履歴

メニュー

リンク

他のサービス

101 Aizu PR

0102　Matrix-like Computation

0103 Baseball Simulation

0104　Magical Tiles

0105　Book Index

0106　Discounts of Buckwheat

0107 Carry a Cheese

0108 Operation of Frequency of Appearance

0109 Smart Calculator

0110 Alphametic

c21coterie @ ウィキ

AOJ101～110

更新履歴

メニュー

リンク

他のサービス

101 Aizu PR

0102 Matrix-like Computation

0103 Baseball Simulation

0104 Magical Tiles

0105 Book Index

0106 Discounts of Buckwheat

0107 Carry a Cheese

0108 Operation of Frequency of Appearance

0109 Smart Calculator

0110 Alphametic

0102　Matrix-like Computation

0104　Magical Tiles

0105　Book Index

0106　Discounts of Buckwheat