「AOJ101～110」の編集履歴（バックアップ）一覧に戻る
AOJ101～110 - (2011/09/06 (火) 10:47:47) のソース
*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);
}
}
