結果

問題 No.2221 Set X
ユーザー lam6er
提出日時 2025-03-31 17:29:59
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,068 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 82,344 KB
実行使用メモリ 68,456 KB
最終ジャッジ日時 2025-03-31 17:30:43
合計ジャッジ時間 6,119 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    A = list(map(int, input[1:n+1]))
    A = sorted(A)

    candidates = set()

    # Collect candidates from each A[i] // k
    for a in A:
        if a == 0:
            continue
        max_k = int(math.sqrt(a)) + 1
        for k in range(1, max_k + 1):
            x1 = a // k
            candidates.add(x1)
            candidates.add(x1 + 1)
            candidates.add(x1 - 1)

    # Collect divisors of differences
    for i in range(n-1):
        d = A[i+1] - A[i]
        if d == 0:
            continue
        max_dk = int(math.sqrt(d)) + 1
        for k in range(1, max_dk + 1):
            if d % k == 0:
                candidates.add(k)
                candidates.add(d // k)
                candidates.add(k + 1)
                candidates.add(d // k + 1)
                candidates.add(k - 1)
                if (d // k) > 1:
                    candidates.add(d // k - 1)

    # Add critical candidates
    if len(A) > 0:
        candidates.add(A[-1] + 1)
    candidates.add(1)
    candidates.add(2)

    # Filter and sort candidates
    X_candidates = [x for x in candidates if x > 0]
    X_candidates = list(set(X_candidates))
    X_candidates.sort()

    min_f = float('inf')
    best_x = None

    for x in X_candidates:
        prev = -1
        count = 0
        for a in A:
            fl = a // x
            if fl != prev:
                count += 1
                prev = fl
        current_f = (x + 1) * count
        if current_f < min_f or (current_f == min_f and x < best_x):
            min_f = current_f
            best_x = x

    # Check X = A_N + 1 in case it's not included
    if len(A) > 0:
        x = A[-1] + 1
        count = 1  # since all are 0
        current_f = (x + 1) * count
        if current_f < min_f or (current_f == min_f and x < best_x):
            min_f = current_f
            best_x = x

    # Also check X=1 which might have been included
    print(best_x)
    print(min_f)

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