結果

問題 No.2221 Set X
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 16:22:02
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,727 bytes
コンパイル時間 224 ms
コンパイル使用メモリ 82,072 KB
実行使用メモリ 83,936 KB
最終ジャッジ日時 2025-06-12 16:22:29
合計ジャッジ時間 5,834 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    max_A = A[-1]
    candidates = set()

    for i in range(1, N):
        diff = A[i] - A[i-1]
        if diff == 0:
            continue
        for k in range(1, int(diff**0.5) + 1):
            x1 = diff // k
            x2 = k
            if x1 > 0:
                candidates.add(x1)
            if x2 > 0:
                candidates.add(x2)
            if diff % k != 0:
                x3 = diff // (k) + 1
                if x3 > 0:
                    candidates.add(x3)
                x4 = k + 1
                if x4 > 0:
                    candidates.add(x4)
        candidates.add(diff)
        candidates.add(diff + 1)
        candidates.add(diff - 1)
    
    candidates.add(max_A)
    candidates.add(max_A + 1)
    candidates.add(1)
    candidates.add(2)
    candidates.add(0)
    candidates.add(max_A // 2)
    candidates.add((max_A + 1) // 2)
    candidates.add(max_A // 3)
    candidates.add((max_A + 1) // 3)

    min_f = float('inf')
    best_X = -1
    candidates = sorted(candidates)

    for X in candidates:
        if X <= 0:
            continue
        count = 1
        prev = A[0] // X
        for a in A[1:]:
            curr = a // X
            if curr != prev:
                count += 1
                prev = curr
        f = (X + 1) * count
        if f < min_f or (f == min_f and X < best_X):
            min_f = f
            best_X = X

    if best_X == -1:
        best_X = max_A + 1
        count = 1
        f = (best_X + 1) * 1
        print(best_X)
        print(f)
        return

    print(best_X)
    print(min_f)

if __name__ == '__main__':
    main()
0