「AOJ21~30」の編集履歴(バックアップ)一覧はこちら

AOJ21~30」(2011/08/21 (日) 18:09:01) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*0021 Parallelism http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0021&lang=jp 4点A,B,C,Dの座標が与えられるので ABとCDが平行ならYES、でないならNOと出力する問題です。 外積が0なら平行という性質を使って外積を求めて答えを出します。 #include<stdio.h> int main(){ double xs[4],ys[4]; int n; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2],&xs[3],&ys[3]); printf("%s\n",(xs[1]-xs[0])*(ys[3]-ys[2])==(xs[3]-xs[2])*(ys[1]-ys[0])?"YES":"NO"); } } ---- *0022 Maximum Sum Sequence http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0022&lang=jp n個の整数の並びが与えられます。 その中で連続した項の和が最大になる値を答えとして出力してください。 順番に読みこんで解いていきます。 ある所まで読んで、読み込んだ数が今までの和より大きいならその数を出発点に足しなおすという作業を繰り返すことで最大値が自動的にもとまります。 和の計が最大値を更新したらそれを記録し最後に出力します。 #include <stdio.h> int main() { int n,s,t,a; while(scanf("%d",&n),n!=0){ s=a=-100001; for(int i=0;i<n;i++){ scanf("%d",&t); s=t+s>t?t+s:t; a=a>s?a:s; } printf("%d\n",a); } } ---- *0023 Circles Intersection http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0023&lang=jp 円A、Bの座標とサイズが与えられるので Aの中にBがあれば-2 Bの中にAがあれば2 AとBが交点を持てば1 重なってないなら0と出力してください。 円A、Bの中心の距離と円のサイズから交点を持つか、内部にあるかを判断できます。 #include <stdio.h> #include <math.h> int main() { double xa,ya,xb,yb,ra,rb,r3,x,y; int n,a; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%lf %lf %lf %lf %lf %lf",&xa,&ya,&ra,&xb,&yb,&rb); x=xa-xb; y=ya-yb; r3=sqrt(x*x+y*y); if(r3+rb<ra){ a=2; }else if(r3+ra<rb){ a=-2; }else if(r3<=ra+rb){ a=1; }else{ a=0; } printf("%d\n",a); } } ---- *0024 Physical Experiments http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0024&lang=jp 建物から物を落とします。 物は空気抵抗を無視して重力加速で地面に激突し壊れます。 落下時物が壊れる速度が与えられるので、何階から落とせば物が壊れるか一番低い階を表示してください。 この問題は重力方程式を素直に解くだけです。 1階が0m扱いなので階を求める処理に少し注意が必要です。 #include <stdio.h> int main(void) { double h,t,h1; while(scanf("%lf",&h)>0){ t=h/9.8; h1=4.9*t*t; printf("%d\n",(int)(h1/5.0)+2); } } ---- *0025 Hit and Blow http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0025&lang=jp Hit And Blowという数当てゲームで答えの数字と回答者の提示した数字が与えれます。 何個HitとBlowがあるかを提示してください。 この問題は同じ数字は使わないというところがポイントになり下記コードのような簡潔な2重ループでかたがつきます。 同じ数字を使うなら、使った数字をメモする必要があります。 #include<stdio.h> #include <math.h> int main(){ int a[4],h,b,n; while(scanf("%d %d %d %d",&a[0],&a[1],&a[2],&a[3])!=EOF){ h=b=0; for(int i=0;i<4;i++){ scanf("%d",&n); for(int j=0;j<4;j++){ if(a[j]==n){ if(i==j) h++; else b++; } } } printf("%d %d\n",h,b); } } ---- *0026 Dropping Ink http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0026&lang=jp 布の上にインクを垂らす問題です。 インクが布の上にたらされていくのでその結果をシミュレートしてください。 解法は愚直にシミュレートするだけです。 lはmとsをmはsを含むということを利用して少しだけコードを短縮できます。 非常に短いコードで解決している人もいるので何か賢い方法もあるかもしれません。 #include<stdio.h> int map[14][14]={0}; void s(int x,int y){ map[y][x]++; map[y][x+1]++; map[y+1][x]++; map[y][x-1]++; map[y-1][x]++; } void m(int x,int y){ map[y+1][x+1]++; map[y+1][x-1]++; map[y-1][x-1]++; map[y-1][x+1]++; s(x,y); } void l(int x,int y){ map[y][x+2]++; map[y+2][x]++; map[y][x-2]++; map[y-2][x]++; m(x,y); } int main(){ int x,y,t; while(scanf("%d,%d,%d",&x,&y,&t)!=EOF){ x+=2; y+=2; if(t==3){ l(x,y); }else if(t==2){ m(x,y); }else{ s(x,y); } } t=0; y=0; for(int i=2;i<12;i++){ for(int j=2;j<12;j++){ x=map[i][j]; t+=x>0?0:1; y=y>x?y:x; } } printf("%d\n%d\n",t,y); } ---- *0027 What day is today? http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0027&lang=jp 2004年の日にちが与えられるので、その日が何曜日か答える問題です。 一番賢い方法はツェラーの公式を使う方法です。 Wikiに良い解説があるので検索してみてください。 これなら年をまたいでも初日と日付の間に何日差があるか計算できます。 私の場合は2004年限定であることを使って下記のようなインチキコードでアセプトしました。 #include<stdio.h> int main(){ int ms[]={0,31,60,91,121,152,182,213,244,274,305,335}; char w[7][10]={"Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"}; int m,d; scanf("%d %d",&m,&d); while(m!=0){ printf("%s\n",w[(2+ms[m-1]+d)%7]); scanf("%d %d",&m,&d); } } ---- *0028 Mode Value http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0028&lang=jp 1~100までの整数データを読み込んで、データの最頻値を出力する問題です。 値が100以下であることを利用して配列にカウントしていくだけです。 #include<stdio.h> #include<string.h> int main(){ int s[101]={0}; int a=0,m; while(scanf("%d",&m)!=EOF){ s[m]++; a=a>s[m]?a:s[m]; } for(int i=1;i<101;i++){ if(a==s[i]) printf("%d\n",i); } } ---- *0029 English Sentence http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0029&lang=jp 文章の中から英単語の出現頻度を計算する問題です。 最も出現頻度の高い単語と文字数の多い単語を出力してください。 stdのMapを理解しているなら基本機能だけで片がつく問題です。 #include <iostream> #include<string> #include<map> using namespace std; int main(){ map<std::string,int> memo; string s,ans1,ans2; int max=0; while(cin>>s){ if(ans2.size()<s.size()) ans2=s; if(memo.find(s)==memo.end()){ memo[s]=1; }else{ memo[s]++; } if(max<memo[s]){ ans1=s; max=memo[s]; } } cout<<ans1<<" "<<ans2<<"\n"; } ---- *0030 Sum of Integers 0 から 9 の数字から異なる n 個の数を取り出して合計が s となる組み合わせの数を出力して終了する問題です。 たった10個の数字を足す足さないで組み合わせるだけなので力づくで全探索しましょう。 n個目の数を足す足さないを01で表現すると、1024までの数で片が付きます。 後はBitを使ってメモ化するだけです。 #include<stdio.h> int main(){ int m[12][50]={0}; int c,s,p,j; for(int i=0;i<1024;i++){ j=c=s=0; p=i; while(p>0){ if(p&1==1){ c++; s+=j; } p=p>>1; j++; } m[c][s]+=1; } scanf("%d %d",&c,&s); while(c!=0 || s!=0){ if(c>10 || s>45){ printf("0\n"); }else{ printf("%d\n",m[c][s]); } scanf("%d %d",&c,&s); } }
*0021 Parallelism http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0021&lang=jp 4点A,B,C,Dの座標が与えられるので ABとCDが平行ならYES、でないならNOと出力する問題です。 外積が0なら平行という性質を使って外積を求めて答えを出します。 #include<stdio.h> int main(){ double xs[4],ys[4]; int n; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2],&xs[3],&ys[3]); printf("%s\n",(xs[1]-xs[0])*(ys[3]-ys[2])==(xs[3]-xs[2])*(ys[1]-ys[0])?"YES":"NO"); } } ---- *0022 Maximum Sum Sequence http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0022&lang=jp n個の整数の並びが与えられます。 その中で連続した項の和が最大になる値を答えとして出力してください。 順番に読みこんで解いていきます。 ある所まで読んで、読み込んだ数が今までの和より大きいならその数を出発点に足しなおすという作業を繰り返すことで最大値が自動的にもとまります。 和の計が最大値を更新したらそれを記録し最後に出力します。 #include <stdio.h> int main() { int n,s,t,a; while(scanf("%d",&n),n!=0){ s=a=-100001; for(int i=0;i<n;i++){ scanf("%d",&t); s=t+s>t?t+s:t; a=a>s?a:s; } printf("%d\n",a); } } ---- *0023 Circles Intersection http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0023&lang=jp 円A、Bの座標とサイズが与えられるので Aの中にBがあれば-2 Bの中にAがあれば2 AとBが交点を持てば1 重なってないなら0と出力してください。 円A、Bの中心の距離と円のサイズから交点を持つか、内部にあるかを判断できます。 #include <stdio.h> #include <math.h> int main() { double xa,ya,xb,yb,ra,rb,r3,x,y; int n,a; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%lf %lf %lf %lf %lf %lf",&xa,&ya,&ra,&xb,&yb,&rb); x=xa-xb; y=ya-yb; r3=sqrt(x*x+y*y); if(r3+rb<ra){ a=2; }else if(r3+ra<rb){ a=-2; }else if(r3<=ra+rb){ a=1; }else{ a=0; } printf("%d\n",a); } } ---- *0024 Physical Experiments http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0024&lang=jp 建物から物を落とします。 物は空気抵抗を無視して重力加速で地面に激突し壊れます。 落下時物が壊れる速度が与えられるので、何階から落とせば物が壊れるか一番低い階を表示してください。 この問題は重力方程式を素直に解くだけです。 1階が0m扱いなので階を求める処理に少し注意が必要です。 #include <stdio.h> int main(void) { double h,t,h1; while(scanf("%lf",&h)>0){ t=h/9.8; h1=4.9*t*t; printf("%d\n",(int)(h1/5.0)+2); } } ---- *0025 Hit and Blow http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0025&lang=jp Hit And Blowという数当てゲームで答えの数字と回答者の提示した数字が与えれます。 何個HitとBlowがあるかを提示してください。 この問題は同じ数字は使わないというところがポイントになり下記コードのような簡潔な2重ループでかたがつきます。 同じ数字を使うなら、使った数字をメモする必要があります。 #include<stdio.h> #include <math.h> int main(){ int a[4],h,b,n; while(scanf("%d %d %d %d",&a[0],&a[1],&a[2],&a[3])!=EOF){ h=b=0; for(int i=0;i<4;i++){ scanf("%d",&n); for(int j=0;j<4;j++){ if(a[j]==n){ if(i==j) h++; else b++; } } } printf("%d %d\n",h,b); } } ---- *0026 Dropping Ink http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0026&lang=jp 布の上にインクを垂らす問題です。 インクが布の上にたらされていくのでその結果をシミュレートしてください。 解法は愚直にシミュレートするだけです。 lはmとsをmはsを含むということを利用して少しだけコードを短縮できます。 非常に短いコードで解決している人もいるので何か賢い方法もあるかもしれません。 #include<stdio.h> int map[14][14]={0}; void s(int x,int y){ map[y][x]++; map[y][x+1]++; map[y+1][x]++; map[y][x-1]++; map[y-1][x]++; } void m(int x,int y){ map[y+1][x+1]++; map[y+1][x-1]++; map[y-1][x-1]++; map[y-1][x+1]++; s(x,y); } void l(int x,int y){ map[y][x+2]++; map[y+2][x]++; map[y][x-2]++; map[y-2][x]++; m(x,y); } int main(){ int x,y,t; while(scanf("%d,%d,%d",&x,&y,&t)!=EOF){ x+=2; y+=2; if(t==3){ l(x,y); }else if(t==2){ m(x,y); }else{ s(x,y); } } t=0; y=0; for(int i=2;i<12;i++){ for(int j=2;j<12;j++){ x=map[i][j]; t+=x>0?0:1; y=y>x?y:x; } } printf("%d\n%d\n",t,y); } ---- *0027 What day is today? http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0027&lang=jp 2004年の日にちが与えられるので、その日が何曜日か答える問題です。 一番賢い方法はツェラーの公式を使う方法です。 Wikiに良い解説があるので検索してみてください。 これなら年をまたいでも初日と日付の間に何日差があるか計算できます。 私の場合は2004年限定であることを使って下記のようなインチキコードでアセプトしました。 #include<stdio.h> int main(){ int ms[]={0,31,60,91,121,152,182,213,244,274,305,335}; char w[7][10]={"Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"}; int m,d; scanf("%d %d",&m,&d); while(m!=0){ printf("%s\n",w[(2+ms[m-1]+d)%7]); scanf("%d %d",&m,&d); } } ---- *0028 Mode Value http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0028&lang=jp 1~100までの整数データを読み込んで、データの最頻値を出力する問題です。 値が100以下であることを利用して配列にカウントしていくだけです。 #include<stdio.h> #include<string.h> int main(){ int s[101]={0}; int a=0,m; while(scanf("%d",&m)!=EOF){ s[m]++; a=a>s[m]?a:s[m]; } for(int i=1;i<101;i++){ if(a==s[i]) printf("%d\n",i); } } ---- *0029 English Sentence http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0029&lang=jp 文章の中から英単語の出現頻度を計算する問題です。 最も出現頻度の高い単語と文字数の多い単語を出力してください。 stdのMapを理解しているなら基本機能だけで片がつく問題です。 #include <iostream> #include<string> #include<map> using namespace std; int main(){ map<std::string,int> memo; string s,ans1,ans2; int max=0; while(cin>>s){ if(ans2.size()<s.size()) ans2=s; if(memo.find(s)==memo.end()){ memo[s]=1; }else{ memo[s]++; } if(max<memo[s]){ ans1=s; max=memo[s]; } } cout<<ans1<<" "<<ans2<<"\n"; } ---- *0030 Sum of Integers http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0030&lang=jp 0 から 9 の数字から異なる n 個の数を取り出して合計が s となる組み合わせの数を出力して終了する問題です。 たった10個の数字を足す足さないで組み合わせるだけなので力づくで全探索しましょう。 n個目の数を足す足さないを01で表現すると、1024までの数で片が付きます。 後はBitを使ってメモ化するだけです。 #include<stdio.h> int main(){ int m[12][50]={0}; int c,s,p,j; for(int i=0;i<1024;i++){ j=c=s=0; p=i; while(p>0){ if(p&1==1){ c++; s+=j; } p=p>>1; j++; } m[c][s]+=1; } scanf("%d %d",&c,&s); while(c!=0 || s!=0){ if(c>10 || s>45){ printf("0\n"); }else{ printf("%d\n",m[c][s]); } scanf("%d %d",&c,&s); } }

表示オプション

横に並べて表示:
変化行の前後のみ表示: