「AOJ1~10」の編集履歴(バックアップ)一覧はこちら
「AOJ1~10」(2011/08/21 (日) 17:22:04) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
----
*0001 List of Top 3 Hills
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0001&lang=jp
山の高さをあらわす整数が10個与えられるので、上位3つの山の高さを表示せよ。
基本機能であるソートを理解しているかどうかが問われる問題です。
基本機能を理解しているならそのまま実装しましょう。
#include<stdio.h>
#include <algorithm>
int main(){
int m[10],i;
for(i=0;i<10;i++){scanf("%d",&m[i]);}
std::sort(m,m+10);
for(int i=9;i>6;i--)printf("%d\n",m[i]);
}
----
*0002 Digit Number
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0002&lang=jp
2つの整数の和の桁数を表示する問題。
基本機能である読み込み関数の使い方やmod演算等を理解しているか問われる問題です。
そのまま実装するだけです。
#include<stdio.h>
int main(){
int a,b,c,d=0;
while(scanf("%d %d",&a,&b)!=EOF){
c=a+b;
d=0;
while(c/10!=0){
c/=10;
d++;
}
printf("%d\n",d+1);
}
}
----
*0003 Is it a Right Triangle?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0003&lang=jp
三角形の3辺が与えられるので、それが直角三角形であるならYesでないならNoと答える問題。
3平方の定理と基本的な計算式を記述する能力が問われます。
#include<stdio.h>
int main(){
int a,b,c,d;
scanf("%d",&d);
for(int i=0;i<d;i++){
scanf("%d %d %d",&a,&b,&c);
a*=a;
b*=b;
c*=c;
if(a==b+c || b==c+a || c==b+a){
printf("YES\n");
}else{
printf("NO\n");
}
}
}
----
*0004 Simultaneous Equation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0004&lang=jp
ax+by=c
dx+ey=f
という定義式があります。
a,b,c,d,e,fの値が与えられるので、x、yを求めてください。
2*2の逆行列を理解しているかが問われる問題です。
高校数学の教科書通りに実装します。
#include<stdio.h>
int main(){
double a,b,c,d,e,f,x,y,k;
while(scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f)!=EOF){
k=a*e-b*d;
x=(e*c-b*f)/k+0.0;
y=(-d*c+a*f)/k+0.0;
printf("%.3lf %.3lf\n",x,y);
}
}
----
*0005 GCD and LCM
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0005&lang=jp
2数a,bが与えられるのでaとbの最小公倍数と最大公約数を求める問題です。
初歩のアルゴリズムの教科書に載っている通りの手順で求めるだけです。
gcdが最大公約数、a*(b/q)が最大公約数となります。
#include<stdio.h>
int gcd(int a, int b)
{
int c;
while (b > 0)
{
c = a % b;
a = b;
b = c;
}
return a;
}
int main(){
int a,b,q;
while(scanf("%d %d",&a,&b)!=EOF){
q=gcd(a,b);
printf("%d %d\n",q,a*(b/q));
}
}
----
*0006 Reverse Sequence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0006&lang=jp
文字列が一行ずつ入力されるので、文字列を一行ずつ逆から表示します。
stdのrevers命令を使えば一行で済みますが、文字列を配列的に扱ってみました。
#include<stdio.h>
#include<string.h>
int main(){
char t[21];
scanf("%s",t);
for(int i=strlen(t)-1;i>=0;i--){
printf("%c",t[i]);
}
printf("\n");
}
----
*0007 Debt Hell
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0007&lang=jp
借金の利息計算です。
利息日ごとに1.05倍して1000円以下は切り上げする処理を書くだけです。
#include<stdio.h>
int main(){
int d=100000,n;
scanf("%d",&n);
for(int i=0;i<n;i++){
d*=1.05;
d+=d%1000==0?0:1000-d%1000;
}
printf("%d\n",d);
}
----
*0008 Sum of 4 Integers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008&lang=jp
50 以下の正の整数 n を入力し、0 ~ 9 の範囲の整数 a, b, c, d の組で
a + b + c + d = n
を満たすものの組み合わせ数を出力するプログラムを作成して下さい。
普通にループを回すだけでも解けますがナップザック法を応用してみました。
#include<stdio.h>
#include<string.h>
int main(){
unsigned int m[5][52],p,q;
memset(m,0,1040);
m[0][0]=1;
for(int k=0;k<51;k++){
for(int i=0;i<40;i++){
p=i/10;
q=i%10;
if(k+p>50) continue;
m[p+1][k+q]+=m[p][k];
}
}
while(scanf("%d",&p)!=EOF){
printf("%d\n",m[4][p]);
}
}
----
*0009 Prime Number
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp
自然数nが与えられるのでn以下の素数が何個あるかを答える問題です。
下から上に数え上げてそれをメモするだけです。
このコード、数え上げに使った配列をそのまま使えばよくMapに入れたのは蛇足なコードでした。
#include<stdio.h>
#include<string.h>
#include<map>
std::map<int,int> s;
int p;
void setSo(){
const m=1000003;
bool t[m];
p=1;
memset(t,m,true);
s[2]=p;
for(int i=3;i<m;i+=2){
if(t[m]==false) continue;
p++;
s[i]=p;
for(int j=i*3;j<m;j+=i*2){
t[j]=false;
}
}
}
int main(){
setSo();
int d;
std::map<int,int>::iterator it;
while(scanf("%d",&d)!=EOF){
it=s.lower_bound(d);
it=it!=s.begin()?it--:it;
printf("%d\n",(*it).second);
}
}
----
*0010 Circumscribed Circle of a Triangle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0010&lang=jp
三角形の頂点座標が与えられるので外心の座標を出力する問題です。
私の場合重心座標で求めまたしたが、求め方は多数ある問題だと思います。
#include<stdio.h>
#include<math.h>
double getDoubleSin(double x1,double y1,double x2,double y2){
double len1,len2,s,c;
len1=sqrt(x1*x1+y1*y1);
len2=sqrt(x2*x2+y2*y2);
s=fabs(x1*y2-y1*x2)/(len1*len2);
c=(x1*x2+y1*y2)/(len1*len2);
//printf("(%lf %lf)",s,c);
return 2*s*c;
}
double getR(double a,double b,double c){
double ans=a*b*c;
ans/=sqrt((a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c));
return ans;
}
int main(){
double xs[3],ys[3];
double g1,g2,g3;
double vx1,vy1,vx2,vy2;
double g[3];
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lf %lf %lf %lf %lf %lf",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2]);
double ansX=0,ansY=0,gSum=0;
double lens[3];
for(int i=0;i<3;i++){
vx1=xs[(i+1)%3]-xs[i];
vy1=ys[(i+1)%3]-ys[i];
vx2=xs[(i+2)%3]-xs[i];
vy2=ys[(i+2)%3]-ys[i];
lens[i]=sqrt(vx1*vx1+vy1*vy1);
g[i]=getDoubleSin(vx1,vy1,vx2,vy2);
//printf("(2s=%lf)\n",g[i]);
ansX+=g[i]*xs[i];
ansY+=g[i]*ys[i];
gSum+=g[i];
}
double R=getR(lens[0],lens[1],lens[2]);
ansX/=gSum;
ansY/=gSum;
printf("%.3lf %.3lf %.3lf\n",ansX,ansY,R);
}
}
----
*0001 List of Top 3 Hills
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0001&lang=jp
山の高さをあらわす整数が10個与えられるので、その中から上位3つの山の高さを表示せよ。
基本機能であるソートを理解しているかどうかが問われる問題です。
基本機能を理解しているならそのまま実装しましょう。
#include<stdio.h>
#include <algorithm>
int main(){
int m[10],i;
for(i=0;i<10;i++){scanf("%d",&m[i]);}
std::sort(m,m+10);
for(int i=9;i>6;i--)printf("%d\n",m[i]);
}
----
*0002 Digit Number
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0002&lang=jp
2つの整数の和の桁数を表示する問題。
基本機能である読み込み関数の使い方やmod演算等を理解しているか問われる問題です。
そのまま実装するだけです。
#include<stdio.h>
int main(){
int a,b,c,d=0;
while(scanf("%d %d",&a,&b)!=EOF){
c=a+b;
d=0;
while(c/10!=0){
c/=10;
d++;
}
printf("%d\n",d+1);
}
}
----
*0003 Is it a Right Triangle?
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0003&lang=jp
三角形の3辺が与えられるので、それが直角三角形であるならYesでないならNoと答える問題。
3平方の定理と基本的な計算式を記述する能力が問われます。
#include<stdio.h>
int main(){
int a,b,c,d;
scanf("%d",&d);
for(int i=0;i<d;i++){
scanf("%d %d %d",&a,&b,&c);
a*=a;
b*=b;
c*=c;
if(a==b+c || b==c+a || c==b+a){
printf("YES\n");
}else{
printf("NO\n");
}
}
}
----
*0004 Simultaneous Equation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0004&lang=jp
ax+by=c
dx+ey=f
という定義式があります。
a,b,c,d,e,fの値が与えられるので、x、yを求めてください。
2*2の逆行列を理解しているかが問われる問題です。
高校数学の教科書通りに実装します。
#include<stdio.h>
int main(){
double a,b,c,d,e,f,x,y,k;
while(scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f)!=EOF){
k=a*e-b*d;
x=(e*c-b*f)/k+0.0;
y=(-d*c+a*f)/k+0.0;
printf("%.3lf %.3lf\n",x,y);
}
}
----
*0005 GCD and LCM
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0005&lang=jp
2数a,bが与えられるのでaとbの最小公倍数と最大公約数を求める問題です。
初歩のアルゴリズムの教科書に載っている通りの手順で求めるだけです。
gcdが最大公約数、a*(b/q)が最大公約数となります。
#include<stdio.h>
int gcd(int a, int b)
{
int c;
while (b > 0)
{
c = a % b;
a = b;
b = c;
}
return a;
}
int main(){
int a,b,q;
while(scanf("%d %d",&a,&b)!=EOF){
q=gcd(a,b);
printf("%d %d\n",q,a*(b/q));
}
}
----
*0006 Reverse Sequence
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0006&lang=jp
文字列が一行ずつ入力されるので、文字列を一行ずつ逆から表示します。
stdのrevers命令を使えば一行で済みますが、文字列を配列的に扱ってみました。
#include<stdio.h>
#include<string.h>
int main(){
char t[21];
scanf("%s",t);
for(int i=strlen(t)-1;i>=0;i--){
printf("%c",t[i]);
}
printf("\n");
}
----
*0007 Debt Hell
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0007&lang=jp
借金の利息計算です。
利息日ごとに1.05倍して1000円以下は切り上げする処理を書くだけです。
#include<stdio.h>
int main(){
int d=100000,n;
scanf("%d",&n);
for(int i=0;i<n;i++){
d*=1.05;
d+=d%1000==0?0:1000-d%1000;
}
printf("%d\n",d);
}
----
*0008 Sum of 4 Integers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008&lang=jp
50 以下の正の整数 n を入力し、0 ~ 9 の範囲の整数 a, b, c, d の組で
a + b + c + d = n
を満たすものの組み合わせ数を出力するプログラムを作成して下さい。
普通にループを回すだけでも解けますがナップザック法を応用してみました。
#include<stdio.h>
#include<string.h>
int main(){
unsigned int m[5][52],p,q;
memset(m,0,1040);
m[0][0]=1;
for(int k=0;k<51;k++){
for(int i=0;i<40;i++){
p=i/10;
q=i%10;
if(k+p>50) continue;
m[p+1][k+q]+=m[p][k];
}
}
while(scanf("%d",&p)!=EOF){
printf("%d\n",m[4][p]);
}
}
----
*0009 Prime Number
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp
自然数nが与えられるのでn以下の素数が何個あるかを答える問題です。
下から上に数え上げてそれをメモするだけです。
このコード、数え上げに使った配列をそのまま使えばよくMapに入れたのは蛇足なコードでした。
#include<stdio.h>
#include<string.h>
#include<map>
std::map<int,int> s;
int p;
void setSo(){
const m=1000003;
bool t[m];
p=1;
memset(t,m,true);
s[2]=p;
for(int i=3;i<m;i+=2){
if(t[m]==false) continue;
p++;
s[i]=p;
for(int j=i*3;j<m;j+=i*2){
t[j]=false;
}
}
}
int main(){
setSo();
int d;
std::map<int,int>::iterator it;
while(scanf("%d",&d)!=EOF){
it=s.lower_bound(d);
it=it!=s.begin()?it--:it;
printf("%d\n",(*it).second);
}
}
----
*0010 Circumscribed Circle of a Triangle
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0010&lang=jp
三角形の頂点座標が与えられるので外心の座標を出力する問題です。
私の場合重心座標で求めまたしたが、求め方は多数ある問題だと思います。
#include<stdio.h>
#include<math.h>
double getDoubleSin(double x1,double y1,double x2,double y2){
double len1,len2,s,c;
len1=sqrt(x1*x1+y1*y1);
len2=sqrt(x2*x2+y2*y2);
s=fabs(x1*y2-y1*x2)/(len1*len2);
c=(x1*x2+y1*y2)/(len1*len2);
//printf("(%lf %lf)",s,c);
return 2*s*c;
}
double getR(double a,double b,double c){
double ans=a*b*c;
ans/=sqrt((a+b+c)*(-a+b+c)*(a-b+c)*(a+b-c));
return ans;
}
int main(){
double xs[3],ys[3];
double g1,g2,g3;
double vx1,vy1,vx2,vy2;
double g[3];
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lf %lf %lf %lf %lf %lf",&xs[0],&ys[0],&xs[1],&ys[1],&xs[2],&ys[2]);
double ansX=0,ansY=0,gSum=0;
double lens[3];
for(int i=0;i<3;i++){
vx1=xs[(i+1)%3]-xs[i];
vy1=ys[(i+1)%3]-ys[i];
vx2=xs[(i+2)%3]-xs[i];
vy2=ys[(i+2)%3]-ys[i];
lens[i]=sqrt(vx1*vx1+vy1*vy1);
g[i]=getDoubleSin(vx1,vy1,vx2,vy2);
//printf("(2s=%lf)\n",g[i]);
ansX+=g[i]*xs[i];
ansY+=g[i]*ys[i];
gSum+=g[i];
}
double R=getR(lens[0],lens[1],lens[2]);
ansX/=gSum;
ansY/=gSum;
printf("%.3lf %.3lf %.3lf\n",ansX,ansY,R);
}
}