結果

問題 No.2221 Set X
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:16:46
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,350 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 81,928 KB
実行使用メモリ 96,540 KB
最終ジャッジ日時 2025-06-12 21:17:32
合計ジャッジ時間 4,931 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    # Generate all possible X candidates
    candidates = set()
    for i in range(N):
        # Include A[i] as candidate
        candidates.add(A[i])
        # Include A[i] // k for k in 1..sqrt(A[i])
        if A[i] == 0:
            continue
        max_k = int(A[i] ** 0.5) + 1
        for k in range(1, max_k + 1):
            x = A[i] // k
            if x > 0:
                candidates.add(x)
            x = (A[i] + k) // k
            if x > 0:
                candidates.add(x)
    # Also include differences between consecutive A's
    for i in range(1, N):
        diff = A[i] - A[i-1]
        if diff > 0:
            candidates.add(diff)
    # Include X=1, even if not present
    candidates.add(1)
    
    min_f = float('inf')
    best_x = -1
    
    for x in sorted(candidates):
        if x <= 0:
            continue
        # Compute C(x)
        prev = -1
        cnt = 0
        for a in A:
            b = a // x
            if b != prev:
                cnt += 1
                prev = b
        f = (x + 1) * cnt
        if f < min_f or (f == min_f and x < best_x):
            min_f = f
            best_x = x
    
    print(best_x)
    print(min_f)
    
if __name__ == "__main__":
    main()
0