AOJ 0008 Sum of 4 Integers
問題概要
nが与えられる。
a + b + c + d = n
を満たすa, b, c, d(a, b, c, dそれぞれの値は、0から9までの範囲の整数に限る)の組み合わせの総数を求めよ。
制約
- 1 ≤ n ≤ 50
解法
全探索。
a, b, c, dについて、それぞれが0から9のいずれであるかをループで決めるので、
4重ループを書き、その中で条件を満たすかどうかをチェックし、満たすのであれば、カウントに1を加算する。
コード
#include <iostream> using namespace std; int main() { int N; while (cin >> N) { int cnt = 0; for (int i = 0; i <= 9; i++) { for (int j = 0; j <= 9; j++) { for (int k = 0; k <= 9; k++) { for (int l = 0; l <= 9; l++) { if (i + j + k + l == N) { cnt++; } } } } } cout << cnt << endl; } return 0; }
AOJ 0007 Debt Hell
問題概要
最初お金が10万円ある。1週間ごとに5%の利子を加え、さらに1000円未満を切り上げる。
n週間後のお金を求めよ。
制約
- 0 ≤ n ≤ 100
解法
シミュレーションする。
5%を加えるは、今持っているお金をmとすると、
m × 1.05である。
1000円未満の切り上げ方法は様々であるが、例えば、
1000 - m % 1000
とすれば良い(ここでa%bとは、aをbで割った余りを表す)。
コード
#include <iostream> using namespace std; int main() { int n, debt = 100000; cin >> n; for (int i = 0; i < n; i++) { debt *= 1.05; if (debt % 1000 != 0) { debt += 1000 - debt % 1000; } } cout << debt << endl; return 0; }
AOJ 0005 GCD and LCM
問題概要
正の整数a, bが与えられるので、これらの最大公約数と最小公倍数を出力せよ。
制約
- 0 ≤ a, b ≤ 2 × 109
- aとbの最小公倍数は、2 × 109を超えない。
- データセットの数は50を超えない。
解法
まず、最大公約数を求める。
ただし、N = min(a, b)とし、
2からNまですべての整数について割り切れるかどうかを判定すると、O(N)かかり、間に合わない。
(AOJは爆速なので間に合うかもしれないが、オーダー的には間に合わないので以下の方法を推奨する)
最大公約数を求めるために、ユークリッドの互除法というアルゴリズムを用いる。
ユークリッドの互除法の原理は、以下が成り立つことである。
a > bのときaとbの最大公約数をGCD(a, b)とし、aをbで割ったときの余りをc(≥ 0)とすると、
GCD(a, b) = GCD(b, c)
となる(証明などは省略、「ユークリッドの互除法」でググると出てくる)。
この方法により、O(log N)で最大公約数を求めることができる。
次に、最小公倍数を求める。
上で求めた最大公約数をGCD(a, b)とすると、以下が成り立つ。
最小公倍数 =
先にa × bをすると、オーバーフローする可能性があるので注意が必要である。
コード
#include <iostream> using namespace std; int gcd(int a, int b) { if (a % b == 0) return b; return gcd(b, a % b); } int main() { int a, b; while (cin >> a >> b) { cout << gcd(a, b) << " " << a / gcd(a, b) * b << endl; } return 0; }
AOJ 0004 Simultaneous Equation
問題概要
a, b, c, d, eが与えられたとき、
連立方程式
ax + by = c
dx + ey = f
を解き、x, yの値を求めよ。
なお、解は一意に定まる。
出力の際には、小数点第4位を四捨五入せよ。
制約
- -1000 ≤ a, b, c, d, e ≤ 1000
コード
#include <iostream> using namespace std; int main() { double a, b, c, d, e, f; while (cin >> a >> b >> c >> d >> e >> f) { double x = (c * e - b * f) / (a * e - b * d); double y = (a * f - c * d) / (a * e - b * d); x *= 1000; x = x + (x > 0 ? 0.5 : -0.5); x = (int)x; y *= 1000; y = y + (y > 0 ? 0.5 : -0.5); y = (int)y; printf("%.3f %.3f\n", x / 1000, y / 1000); } return 0; }
AOJ 0006 Reverse Sequence
問題概要
文字列strが与えられるので、その文字列を逆順に表示せよ。
制約
- 1 ≤ 文字列のサイズ ≤ 20
- 文字列中の文字は、半角英数字のみ
解法
まず、文字列を入力する。
文字列の入力について、C言語、C++では以下のように書く。
/* 注意点として、文字列の最大サイズより1大きいサイズにすること。 理由は、文字列の終端には、ヌル文字という文字列の終わりを表す特殊な文字が挿入されるためである。 */ char str[21]; scanf("%s", str);
string str; cin >> str;
文字列を入力したら、文字列のサイズを求める。
文字列のサイズの求め方は、C言語、C++では以下のように書く。
strlen(str);
str.size(); // str.length()でもOK
後は、文字列のサイズ-1から0になるまでループで1文字ずつ出力していく。
コード
#include <iostream> using namespace std; int main() { string str; cin >> str; for (int i = str.size()-1; i >= 0; i--) { cout << str[i]; } cout << endl; return 0; }
