結果

問題 No.2221 Set X
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:14:13
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,732 bytes
コンパイル時間 288 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 97,844 KB
最終ジャッジ日時 2025-04-15 22:15:44
合計ジャッジ時間 4,985 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    A = list(map(int, input[1:n+1]))
    A = [a for a in A if a >= 0]  # Remove negative values if any (though problem states 0 <= A1 < ...)
    if not A:
        print(1)
        print(2)
        return
    max_A = A[-1]
    candidates = set()

    # Generate candidates from each A_i
    for a in A:
        if a == 0:
            continue
        sqrt_a = int(math.isqrt(a))
        for k in range(1, sqrt_a + 1):
            x = a // k
            candidates.add(x)
            candidates.add(x + 1)
            candidates.add(x - 1)
        # Also handle the case where k is up to a//1 (but covered by sqrt)
        # Add edge cases
        candidates.add(a)
        candidates.add(a + 1)
        candidates.add(a - 1)
    
    # Add max_A + 1 and 1 to 1e5 as threshold
    candidates.add(max_A + 1)
    for x in range(1, min(10**5, max_A + 2)):
        candidates.add(x)
    
    # Remove invalid candidates (X must be positive)
    candidates = {x for x in candidates if x > 0}
    candidates.add(1)  # Ensure X=1 is considered
    candidates.add(max_A)
    candidates.add(max_A + 1)
    
    # Now compute for each candidate X
    min_f = float('inf')
    best_x = None
    A_sorted = sorted(A)
    for x in sorted(candidates):
        prev = None
        count = 0
        for a in A_sorted:
            d = a // x
            if d != prev:
                count += 1
                prev = d
        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
    print(best_x)
    print(min_f)

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