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

## 目次
  - [A - Three Threes](#a---three-threes)
  - [B - Pentagon](#b---pentagon)
  - [C - Repunit Trio](#c---repunit-trio)

## A - Three Threes
### 問題
1 以上 9 以下の整数 N が入力として与えられます。
数字 N を N 個繋げて得られる文字列を出力してください。

>**制約**
>1. N は 1 以上 9 以下の整数

詳細はこちらです。

https://atcoder.jp/contests/abc333/tasks/abc333_a

### 解説
入力した N 回分、`do文`で繰り返し出力します。


### プログラム例
```Fortran
program abc333a
    !N：整数N
    implicit none
    integer N, i

    !入力
    read (*, *) N

    !出力
    do i = 1, N
        write (*, '(i0)', advance='no') N
    end do
end program abc333a
```



## B - Pentagon
### 問題
辺ABCDEから構成される正五角形Pがあります。
正五角形P の点 $S_1$ と点 $S_2$ を結ぶ線分と、点 $T_1$ と点 $T_2$ を結ぶ線分の長さが等しいか判定してください。

>**制約**
>1. $S_1,S_2,T_1,T_2$ は A, B, C, D, E のいずれかの文字
>2. $S_1≠S_2$
>3. $T_1≠T_2$

詳細はこちらです。

https://atcoder.jp/contests/abc333/tasks/abc333_b

### 解説
線分の内、$AB , BC, CD, DE, EA$は短く、残りの線分は長いです。
入力した線分が短いか長いかを場合分けし、長さが等しいか判定します。


### プログラム例
```Fortran
program abc333b
    !S1S2    ：S1と点S2を結ぶ線分
    !T1T2    ：T1と点T2を結ぶ線分
    !nagasa_a：線分S1S2の長さ(1:短い,0：長い)
    !nagasa_b：線分T1T2の長さ(1:短い,0：長い)
    implicit none
    character(2) S1S2, T1T2
    integer nagasa_a, nagasa_b

    !入力
    read (*, *) S1S2
    read (*, *) T1T2

    !線分の長さチェック
    call check_nagasa(S1S2, nagasa_a)
    call check_nagasa(T1T2, nagasa_b)

    !結果の出力
    if (nagasa_a == nagasa_b) then
        write (*, '(a)') 'Yes'
    else
        write (*, '(a)') 'No'
    end if
contains
    subroutine check_nagasa(line, nagasa)
        !line  ：線分
        !nagasa：線分の長さ(1:短い,0：長い)
        character(2) line
        integer nagasa

        !線分の長さ判定
        nagasa = 0
        select case (line)
        case ("AB")
            nagasa = 1
        case ("BC")
            nagasa = 1
        case ("CD")
            nagasa = 1
        case ("DE")
            nagasa = 1
        case ("EA")
            nagasa = 1
        case ("AE")
            nagasa = 1
        case ("ED")
            nagasa = 1
        case ("DC")
            nagasa = 1
        case ("CB")
            nagasa = 1
        case ("BA")
            nagasa = 1
        end select
    end subroutine check_nagasa
end program abc333b
```



## C - Repunit Trio
### 問題
十進法ですべての桁の数字が 1 である整数をレピュニットと呼びます。

レピュニットを小さい順に並べると $1,11,111,…$ です。
3 つのレピュニットの和として表せる整数のうち N 番目に小さいものを求めてください。


>**制約**
>1. N は 1 以上 333 以下の整数

詳細はこちらです。

https://atcoder.jp/contests/abc333/tasks/abc333_c


### 解説
3つのレピュニットA,B,Cは$1,11,111,1111…$と規則的に増えていきます。
`do文`の３重ループを作り、レピュニットA,B,Cの和を全探索で計算します。
([全探索の範囲は12桁まで調べれば十分なようです。](https://atcoder.jp/contests/abc333/editorial/7979))

全探索を用いてレピュニットの和を求める場合、並び順は昇順ではないため**マージソート**を使って並び替えを行います。
また、レピュニット和は同じ数値になる場合があるため、同じ数値は取り除く必要があります。


### プログラム例
```Fortran
program abc333c
    !rep(cnt)           ：3つのレピュニットの和
    !rep_i, rep_j, rep_k：3つのレピュニットの値
    !N                  ：知りたいレピュニットの和の位置
    implicit none
    integer(16) N, rep_N
    integer(16) rep(1728)
    integer(16) rep_i, rep_j, rep_k
    integer(16) i, j, k, cnt

    !入力
    read (*, *) N

    !3つのレピュニットの和を列挙
    rep_i = 0; rep_j = 0; rep_k = 0
    rep = 0; cnt = 1
    do i = 0, 11
        rep_j = 0
        rep_i = rep_i + 10**i
        do j = 0, 11
            rep_j = rep_j + 10**j
            rep_k = 0
            do k = 0, 11
                rep_k = rep_k + 10**k
                rep(cnt) = rep_i + rep_j + rep_k
                cnt = cnt + 1
            end do
        end do
    end do

    !小さい順に並びかえ、被りの除去
    rep_N = 1728
    call margesort(rep, rep_N)
    call check(rep, rep_N)
    write (*, *) rep(N)
contains
    subroutine margesort(x, n)
        integer(16) N
        integer(16) x(N), tmp(N)
        integer(16) start, end
        start = 1; end = N
        call loop_margesort(x, tmp, N, start, end)
    end subroutine
    recursive subroutine loop_margesort(x, tmp, N, left, right)
        integer(16) left, right, mid
        integer(16) N
        integer(16) x(N), tmp(N)
        integer(16) i, j, k

        !これ以上2分かつできないならretrun
        if (left >= right) return

        !分割できるだけ分割する
        mid = (left + right)/2
        call loop_margesort(x, tmp, N, left, mid)
        call loop_margesort(x, tmp, N, mid + 1, right)

        !並び替えの下準備としてtmpに配列をコピー
        j = 0
        tmp(left:mid) = x(left:mid)
        do i = mid + 1, right
            tmp(i) = x(right - j)
            j = j + 1
        end do

        !大小比較して小さい順に入れていく
        i = left
        j = right
        !write (*, '(3x,*(f13.101x),a)', advance='no') x(left:right)
        !write (*, '(a)', advance='no') '>>'
        do k = left, right
            if (tmp(i) < tmp(j)) then
                x(k) = tmp(i)
                i = i + 1
            else if (tmp(i) == tmp(j)) then
                x(k) = tmp(i)
                i = i + 1
            else
                x(k) = tmp(j)
                j = j - 1
            end if
        end do
        !write (*, '(3x,*(f13.10,1x))') x(left:right)
    end subroutine loop_margesort
    subroutine check(arr, N)
        integer(16) N, cnt
        integer(16) arr(N), arr2(N)
        arr2 = 0; cnt = 1
        arr2(1) = arr(1)
        do i = 1, N
            if (arr2(cnt) /= arr(i)) then
                cnt = cnt + 1
                arr2(cnt) = arr(i)
            end if
        end do
        arr = arr2
    end subroutine check
end program abc333c


```