2018-06-10

Volume0: 0009

$n$ 以下の素数の個数を求める問題です。

予めエラトステネスの篩を使用して素数のリストを作成しておき、各データセットに対して素数の個数を求めます。

Python

# coding: utf-8

LIMIT = 999999

# 1 から LIMIT までのリスト
# 素数（の候補）を 1 、素数でないもを 0 とする  
# 2 以外の偶数は素数ではない
prime = [0, 1] + [0 if i % 2 == 0 else 1 for i in range(3, LIMIT + 1)]

# 3 から LIMIT の平方根までを走査
for i in range(3, int(LIMIT ** 0.5) + 1):
    # 対象が素数である場合
    if prime[i - 1] == 1:
        # 自身の倍数は素数ではない
        for j in range(i ** 2, LIMIT + 1, i):
            # 素数ではないので 0
            prime[j - 1] = 0

while True:
    try:
        n = int(input())
    except EOFError:
        break
    
    # 1 から n までの素数の個数を合計して出力
    print(sum(prime[:n]))

Ruby

Primeクラスで素数についてあれこれできます。

# coding: utf-8

require 'prime'

while line = gets do
    n = line.to_i
    puts Prime.each(n).count
end

2018-06-09

Volume0: 0008

AOJ Volume0 c++ python

４つの整数の和 | Aizu Online Judge

重複を許す組み合わせの数を求めます。

C++

$d$ を $n - (a + b + c)$ より求めることで、forループが三重で済みます。

#include <iostream>
using namespace std;

int n;

int main()
{
    while (cin >> n) {
        int count = 0;
        for (int a = 0; a <= 9; ++a) {
            for (int b = 0; b <= 9; ++b) {
                for (int c = 0; c <= 9; ++c) {
                    int d = n - a - b - c;
                    if (0 <= d && d <= 9) ++count;
                }
            }
        }
        cout << count << endl;
    }
    return 0;
}

Python

itertools.product()を使用することで、直積を求めることができます。

product(range(10), range(10))は、(x, y) for x in range(10) for y in range(10)と等価です。

また、product(range(10), range(10))は、product(range(10), repeat=2)と等価です。

# coding: utf-8

from itertools import product

RANGE = range(10)

while True:
    try:
        n = int(input())
    except EOFError:
        break
    
    print(sum([1 for (a, b, c) in product(RANGE, repeat=3) if n - a - b - c in RANGE]))

2018-06-03

Volume0: 0007

AOJ Volume0 c++ python

借金地獄 | Aizu Online Judge

以下の操作を $n$ 回繰り返せば良いです。

借金に利子を加える
1000未満を切り上げ

C++

借金の計算は以下の通りです。

借金に金利を加える
1000未満を切り上げするために、999を加える
1000で割って千の位未満の桁を飛ばす
1000を掛けて千の位未満の桁を0にする

#include <iostream>
using namespace std;

int n;
int debt = 100000;
const int DIGITS = 1000;
const float INTEREST_RATE = 1.05;

int main()
{
    cin >> n;

    for (int i = 0; i < n; ++i) {
        // 借金に利子を加え、1000円未満を切り上げ
        debt = ((int)((debt * INTEREST_RATE + DIGITS - 1) / DIGITS)) * DIGITS;
    }

    cout << debt << endl;
    return 0;
}

Python

math.ceil(x)関数は、x以上の最小の整数を返します。

借金を百の位で切り捨てるためには、百の位が小数点第一位となるように調整し、math.ceil()を使用すれば良いです。

# coding: utf-8

from math import ceil

DEBT = 100000
DIGITS = 1000
INTEREST_RATE = 1.05

def calc_debt(n):
    "n週間後の借金を計算する"

    # 借金の百の位が小数点第一位となるよう調整
    d = DEBT // DIGITS

    # 毎週利子を加える
    while n > 0:
        d = ceil(d * INTEREST_RATE)  # 借金の小数点以下を切り捨て
        n  -= 1

    # 調整した借金を元に戻して返却する
    return d * DIGITS

n = int(input())

print(calc_debt(n))

2018-06-02

Volume0: 0006

AOJ Volume0 c++ javascript python ruby

文字列を逆順に出力 | Aizu Online Judge

文字列を逆順にする問題です。

文字列は文字の配列で表現されているので、配列を後ろから操作すれば良いです。

ただし、ほとんどの言語において、関数reverseで文字列を逆順にすることができます。

C++

配列を後ろから操作します。

#include <iostream>
using namespace std;

string s, r;

int main()
{
    cin >> s;

    for (int i = s.size() - 1; i >= 0; i--) {
        r += s[i];
    }

    cout << r << endl;
    return 0;
}

reverseを使用します。

#include <iostream>
#include <algorithm>
using namespace std;

string s;

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

JavaScript

'use strict'

const fs = require('fs')

function main(input) {
  console.log(input.trim().split('').reverse().join(''))
}

main(fs.readFileSync('/dev/stdin', 'utf8'))

Python

# coding: utf-8

print(input()[::-1])

Ruby

# coding: utf-8

puts gets.chomp.reverse

2018-05-27

Volume0: 0005

AOJ Volume0 c++ python ruby

最大公約数と最小公倍数 | Aizu Online Judge

最大公約数と最小公倍数を求める問題です。

整数 $a, b$ に対して、最大公約数 $gcd(a, b)$ と $lcm(a, b)$ は、 $gcd(a, b) \times lcm(a, b) = ab$ という関係があります。

最大公約数は、ユークリッドの互除法を使って求めることができます。

C++

#include <iostream>
using namespace std;

long a, b, gcd, lcm;

// ユークリッドの互除法より最大公約数を求める
long euclideanAlgorithm(long a, long b)
{
    // a > b になるように a と b を入れ替える
    if (a < b) swap(a, b);

    // 剰余が0になった時の除数が a と b の最大公約数
    if (b == 0) return a;

    // 剰余が0になるまで、剰余を求める計算を繰り返す
    return euclideanAlgorithm(b, a % b);
}

int main()
{
    while (cin >> a >> b) {
        gcd = euclideanAlgorithm(a, b);  // 最大公約数
        lcm = a * b / gcd;               // 最小公倍数
        cout << gcd << " " << lcm << endl;
    }

    return 0;
}

Python

math.gcd(a, b)は、aとbの最大公約数を返します。

# coding: utf-8

import math

while True:
    try:
        a, b = [int(i) for i in input().split()]

        gcd = math.gcd(a, b)  # 最大公約数
        lcm = a * b // gcd    # 最小公倍数

        print(f'{gcd} {lcm}')
    except EOFError:
        break

Ruby

Integer#gcdとInteger#lcmを利用し、最大公約数と最小公倍数を求めることができます。

# coding: utf-8

while line = gets
  a, b = line.chomp.split.map(&:to_i)

  gcd = a.gcd(b)  # 最大公約数
  lcm = a.lcm(b)  # 最小公倍数

  puts %Q!#{gcd} #{lcm}!
end

%Q!STRING!は、ダブルクォート文字列と同等です。

2018-05-26

Volume0: 0004

AOJ Volume0 python ruby

連立方程式 | Aizu Online Judge

連立方程式の解を求める問題です

クラーメルの公式を利用します

Python

# coding: utf-8

while True:
    try:
        a, b, c, d, e, f = [int(i) for i in input().split()]

        detA = a * e - b * d
        detA1 = c * e - b * f
        detA2 = a * f - c * d

        # -0.000 を 0.000 にするために 0 を足す
        print('{:.3f} {:.3f}'.format(detA1 / detA + 0, detA2 / detA + 0))
    except EOFError:
        break

Ruby

# coding: utf-8

while line = gets
    a, b, c, d, e, f = line.strip.split.map(&:to_f)
    detA = a * e - b * d
    detA1 = c * e - b * f
    detA2 = a * f - c * d
    # -0.000 を 0.000 にするために 0 を足す
    puts "%.3f %.3f" % [detA1 / detA + 0, detA2 / detA + 0]
end

文字列の%演算は、第1引数にフォーマット、第2引数にフォーマットしたい値を指定します

書式に埋め込む値が複数ある場合は、右辺を配列にします

"%.3f %.3f" % [detA1 / detA + 0, detA2 / detA + 0]

2018-05-20

Volume0: 0003

AOJ Volume0 c++ python ruby

正三角形 | Aizu Online Judge

三平方の定理を利用します

直角三角形の斜辺 $c$ と他の $2$ 辺 $a, b$ との関係は、 $a^{2} + b^{2} = c^{2}$ です

C++

#include <iostream>
using namespace std;

int a, b, c, n;

int main()
{
    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> a >> b >> c;

        // cを斜辺にする
        if (a > c) swap(a, c);
        if (b > c) swap(b, c);

        cout << (a * a + b * b == c * c ? "YES" : "NO") << endl;
    }

    return 0;
}

Python

# coding: utf-8

for i in range(int(input())):
    a, b, c = sorted([int(i) for i in input().split()])
    print('YES' if a ** 2 + b ** 2 == c ** 2 else 'NO')

Ruby

# coding: utf-8

gets.to_i.times do
    a, b, c = gets.chomp.split().map(&:to_i).sort()
    puts a ** 2 + b ** 2 == c ** 2 ? 'YES' : 'NO'
end

pontz_rwのブログ

プログラミング等の備忘録

Volume0: 0009

Python

Ruby

Volume0: 0008

C++

Python

Volume0: 0007

C++

Python

Volume0: 0006

C++

JavaScript

Python

Ruby

Volume0: 0005

C++

Python

Ruby

Volume0: 0004

Python

Ruby

Volume0: 0003

C++

Python

Ruby