【ABC330】FortranでA,B,C問題

目次

• A - Counting Passes
• B - Minimize Abs 1
• C - Minimize Abs 2

A - Counting Passes

問題

N 人が試験を受けました。それぞれの点数は $A_i$ 点です。
試験では L 点以上を取った人が合格になります。
N 人中何人が合格したかを求めます。

制約

1. 入力は全て整数
2. $1 ≤ N ≤ 100$
3. $1 ≤ L ≤ 1000$
4. $0 ≤ A_i ≤ 1000$

詳細はこちらです。

解説

N人全員の点数を調べ、合格した人の合計を求めます。

プログラム例

program abc330a
    !N   :受験者数
    !A(N):N人分の試験の点数
    !L   :合格点
    !cnt :合格者数
    implicit none
    integer i, N, L, cnt
    integer, allocatable::A(:)

    !入力
    read (*, *) N, L
    allocate (A(N))
    read (*, *) A(1:N)

    !カウント
    cnt = 0
    do i = 1, N
        if (A(i) >= L) cnt = cnt + 1
    end do

    !結果の出力
    write (*, *) cnt
end program abc330a

B - Minimize Abs 1

問題

N 個の整数 $A_1 ,A_2,…,A_N$ と整数L,Rが与えられます。
$i =1,2...N$　の時以下の条件を満たす整数$X_i$を求めます。

条件

1. $L≤ X_i ≤ R$
2. L 以上、R以下であるどの整数Yでも$|X_i - A_i| ≤ |Y_i - A_i| $を満たす。
3. A_1 ,A_2 ,…,A_N がすべて等しいということはない

制約

1. $L ≤ N ≤ ２*10^5$
2. $1 ≤ L ≤ R ≤ 10^9$
3. $1 ≤ A_i ≤ 10^9$
4. 入力は全て整数

詳細はこちらです。

解説

条件を満たす整数$X_i$のパターンは、$A(i),L,R$ の３パターンに分けられます。
条件の切り分けを行い、回答を出力します。

プログラム例

program abc330b
    !N   :整数列Aの長さ
    !L,R :整数L、R
    !A(N):整数列
    implicit none
    integer(16) N, L, R, i
    integer(16), allocatable :: A(:)

    !入力
    read (*, *) N, L, R
    allocate (A(N))
    read (*, *) A

    !場合分けして出力
    do i = 1, N
        if (A(i) >= L .and. A(i) < R) then !L以上R未満
            write (*, '(i0,1x)', advance='no') A(i)
        elseif (A(i) < L) then !L未満
            write (*, '(i0,1x)', advance='no') L
        elseif (A(i) >= R) then !R以上
            write (*, '(i0,1x)', advance='no') R
        end if
    end do
end program abc330b

C - Minimize Abs 2

問題

正整数 D が与えられます。
非負整数 x,y に対する $∣x^2+y^2−D∣$ の最小値を求めます

1. $1≤D≤2×10^{12}$
2. 入力は全て整数

詳細はこちらです。

解説

全探索を行い最小値を見つけます。
探索範囲はyを十分大きい数($2×10^6$)から１ずつ小さく、xは０から１ずつ大きくしていき行います。

プログラム例

program abc330c
    !D    ：正整数D
    !x    ：非負整数x
    !y    ：非負整数y
    implicit none
    integer(8) x, y, ans, D

    !入力
    read (*, *) D

    !最小値の検索
    ans = D
    y = 2*10**6
    do x = 0, 2*10**6
        do
            if (y > 0 .and. x*x + y*y > D) then
                y = y - 1
            else
                exit
            end if
        end do
        ans = min(ans, abs(x*x + y*y - D))
        ans = min(ans, abs(x*x + (y + 1)*(y + 1) - D))
    end do

    !出力
    write (*, *) ans
end program abc330c

感想

• 繁忙期で忙しく、参加する暇がありませんでした...
• 年度を跨いでも忙しさは改善されなかったので、今後はフロー図省略して更新します。