結果

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

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    n = int(data[0])
    a = list(map(int, data[1:n+1]))
    max_a = a[-1] if n > 0 else 0

    candidates = set()

    # Add X from 1 to sqrt(max_a)
    sqrt_max = int(math.isqrt(max_a)) + 1 if max_a > 0 else 1
    for x in range(1, sqrt_max + 1):
        candidates.add(x)

    # Add candidates from each A_i
    for ai in a:
        if ai == 0:
            continue
        sqrt_ai = int(math.isqrt(ai)) + 1
        for k in range(1, sqrt_ai + 1):
            x1 = ai // k
            candidates.add(x1)
            candidates.add(x1 + 1)
            if k > 1:
                x3 = ai // (k - 1)
                candidates.add(x3)

    # Convert to sorted list and filter valid X (X >= 1)
    candidates = [x for x in sorted(candidates) if x > 0]

    min_f = float('inf')
    best_x = None

    # Evaluate each candidate X
    for x in candidates:
        prev = None
        count = 0
        for ai in a:
            q = ai // x
            if prev != q:
                count += 1
                prev = q
        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 larger than all candidates (where all elements are 0)
    if candidates:
        max_candidate = max(candidates)
    else:
        max_candidate = 0
    x_large = max_candidate + 1
    # All elements are 0 when X > max_a
    if max_a == 0:
        count_large = 1
    else:
        count_large = 1 if x_large > max_a else 0
    if count_large == 1:
        f_large = (x_large + 1) * 1
        if f_large < min_f or (f_large == min_f and x_large < best_x):
            min_f = f_large
            best_x = x_large

    print(best_x)
    print(min_f)

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