夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

AOJの0001〜0009を解いてみた。

題名のとおりです。

もちろん0000も解いたのですがローカルに保存してなかったので(;´Д`)


問題文は日本語もありますが、あえて英語で掲載しています。

では、解答一覧。

0001

 /*
There is a data which provides heights (in meter) of mountains. The data is only for ten mountains.

Write a program which prints heights of the top three mountains in descending order.
 */

#include <iostream>

using namespace std;

void reverse(int *array, int length) {
	int i;
	int j;
	for(i=0;i<length-1;i++){
		for(j=i+1;j<length;j++){
			if(array[i]<array[j]){
				int temp=array[i];
				array[i]=array[j];
				array[j]=temp;
			}
		}
	}
}

int main() {
	int mountain[10];
	for (int i = 0; i < 10; i++) {
		cin >> mountain[i];
	}
	reverse(mountain, 10);
	for (int i = 0; i < 3; i++) {
		cout << mountain[i] << endl;
	}
}

山の高さが10個与えられるからそのうちのトップ3を表示しろという問題。

まぁ降順ソートしておk。

0002

 /*
Write a program which computes the digit number of sum of two integers a and b
 */

#include <iostream>
  
using namespace std;  
  
// 入力  
int a, b;  
  
void solve()  
{  
    int res = 0;  
  
    a += b;  
  
    for (; a; a /= 10)  
        res++;  
  
    cout << res << endl;  
}  
  
int main()  
{  
    while (cin >> a >> b)  
        solve();  
  
    return 0;  
} 

a+bの桁数を求めるもの。
どうしてもエラーがでるので他人のコードを奪取(汗 for文はおそらく合計を10で割っていってaが割れなくなるまでっていうんでしょうけど…どうなってるのか(;´Д`)

0003

 /*
Write a program which judges wheather given length of three side form a right triangle. Print "YES" if the given sides (integers) form a right triangle, "NO" if not so.
 */

#include <iostream>
#include <math.h>

using namespace std;

void solve(int a, int b, int c) {
	bool f = false;
	int max_num = max(a, max(b, c));
	int sub1, sub2;
	if (max_num != a) {
		sub1 = a;
		if (max_num != b) sub2 = b;
		else sub2 = c;
	} else if (max_num != b) {
		sub1 = b;
		sub2 = c;
	} 		
	if (pow(max_num, 2) == pow(sub1, 2) + pow(sub2, 2)) f = true;
	if (f) cout << "YES" << endl;
	else cout << "NO" << endl;
}

int main() {
	int num, a, b, c;
	cin >> num;
	for (int i=0; i<num; i++) {
		cin >> a >> b >> c;
		solve(a,b,c);
	}
	return 0;
}

三辺の数値が与えられるのでそれが直角三角形かを判定する問題。
途中までただの三角形ができるかどうかの問題だと思ってて苦戦しましたw

とりあえず普通に三平方の定理で解きました。

0004

 /*
Write a program which solve a simultaneous equation:

        ax + by = c
        dx + ey = f
The program should print x and y for given a, b, c, d, e and f(-1000 &#8804; a, b, c, d, e, f &#8804; 1000). You can suppose that given equation has a unique solution.
 */

#include <iostream>
#include <cstdio>

using namespace std;

void solve(int a, int b, int c, int d, int e, int f) {
	double x = (f - (double)e*c/b) / (d - (double)e*a/b);
	double y = (c - a*x) / b;
	if (x == 0) x = 0.000;
	if (y == 0) y = 0.000;
	printf("%4.3f %4.3f\n", x, y);
}

int main() {
	int a, b, c, d, e, f;
	while (cin >> a >> b >> c >> d >> e >> f) {
		solve(a,b,c,d,e,f);
	}
	return 0;
}

与えられたa,b,c,d,e,fを使ってできる連立方程式をとけというもの。

浮動小数点の扱いにすこし手こずりましたが、とりあえず手元で連立方程式の一般式を解いて代入しました。

0005

 /*
Write a program which computes the greatest common divisor (GCD) and the least common multiple (LCM) of given a and b (0 < a, b &#8804; 2,000,000,000). You can supporse that LCM(a, b) &#8804; 2,000,000,000.
  */

#include <iostream>
#include <math.h>

using namespace std;

int calc_gcj(int a, int b) {
	int A=0, B=0;
	if (a == max(a,b)) {
		A = a;
		B = b;
	} else {
		A = b;
		B = a;
	}
	if (A == B) return A;
	else return calc_gcj(B,A-B);
	return -1;
}

void solve(int a, int b) {
	int gcj = calc_gcj(a,b);
	int lcm = a/gcj*b;
	cout << gcj << " " << lcm << endl;
}

int main() {
	int a, b;
	while (cin >> a >> b) {
		solve(a,b);
	}
	return 0;
}

与えられた2つの値のデータセットから、最大公約数と最小公倍数を求めるというもの。

ただ、人間がやるような方法をやらせようとしても値の上限値が2,000,000,000ということでランタイムエラーorタイムオーバーしてしまいます。


そこでコンピュータに適した最大公約数の求め方、ユークリッド互除法を使います。詳しくは検索してください。

0006

 /*
Write a program which reverses a given string str.
 */

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main() {
	string str;
	cin >> str;
	reverse(str.begin(), str.end());
	cout << str << endl;
	return 0;
}

文字列を反転して返すもの。

僕ずるいので調べて標準ライブラリ関数使ってしまいました(笑)

0007

 /*
Your friend who lives in undisclosed country is involved in debt. He is borrowing 10-man yen from a loan shark. The loan shark adds 5% interest of the debt and rounds it to the nearest sen above week by week.

Write a program which computes the amount of the debt in n weeks. ( n &#8804; 100) 
 */

#include <iostream>

using namespace std;

int main() {
	int n; cin >> n;
	int ans = 100000;
	int tmp;
	for (int i=0; i<n; i++) {
		ans *= 1.05;
		tmp = ans / 1000 * 1000;
		if (tmp != ans) ans = tmp + 1000;
	}
	cout << ans << endl;
	return 0;
}

闇金に手をだした友達。しかし一銭も返済していない。今返済しなくてはいけない額をもとめるというもの。

ちょっと1000円に騙されました。どうやら1000円未満を切り上げるということらしいです。(←日本語文見た。)
どっちかっていうと読解問題w

0008

 /*
Write a program which reads an integer n (n &#8804; 50) and identifies the number of combinations of a, b, c, and d (0 &#8804; a, b, c, d &#8804; 9) which meet the following equality:

        a + b + c + d = n
For example, for n = 35, we have 4 different combinations of (a, b, c, d): (8, 9, 9, 9), (9, 8, 9, 9), (9, 9, 8, 9), (9, 9, 9, 8).
 */

#include <iostream>

using namespace std;

int calc(int a, int b, int n) {
	int tmp = n-a-b;
	int count = 0;
	for (int c=0; c<10; c++) {
		for (int d=0; d<10; d++) {
			if (tmp == c+d)
				count++;
		}
	}
	return count;
}

void solve(int n) {
	int count = 0;
	for (int a=0; a<10; a++) {
		for (int b=0; b<10; b++) {
			count += calc(a,b,n);
		}
	}
	cout << count << endl;
}

int main() {
	int n;
	while (cin >> n) {
		solve(n);
	}
	return 0;
}

nが与えられるのでa+b+c+d=n(0≦a,b,c,d≦9)となる(a,b,c,d)がいくつ作れるか返す問題。

ものすごい方針から苦戦しましたが、まぁ出来ました。
これなら別にcalcわけなくても良かったですね(汗

0009

現在進行形で思索中

 /*
Write a program which reads an integer n (n &#8804; 999999) and prints the number of prime numbers which are less than or equal to n. A prime number is a natural number which has exactly two distinct natural number divisors: 1 and itself. For example, the first four prime numbers are: 2, 3, 5, 7.
 */

#include <iostream>

using namespace std;

void solve(int n) {
	int prime[n];
	int j=0;
	for (int i=2; i<=n; i++) {
		prime[j] = i;
		j++;
	}
	int p;
	for (int i=0; i<n; i++) {
		p = prime[i];
		if (p == -1) continue;
		for (int k=i+1; k<n; k++) {
			if (prime[k]%p == 0)
				prime[k] = -1;
		}
	}
	int count = 0;
	for (int i=0; i<n; i++)
		if (prime[i] != -1) count++;
	cout << count << endl;
}

int main() {
	int n;
	while (cin >> n) {
		if (n<=1) cout << 0 << endl;
		solve(n);
	}
	return 0;
}

nまでの素数の数を求めよというのですが、愚直な方法でもタイムオーバーです。

どうすればいいんでしょう(;´Д`)


p.s.メインのエディタがGeditに劣化しました(笑)埋め込み端末からVimも呼び出せますけどw

広告を非表示にする