結果

問題 No.2221 Set X
ユーザー gew1fw
提出日時 2025-06-12 18:01:49
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,339 bytes
コンパイル時間 331 ms
コンパイル使用メモリ 81,916 KB
実行使用メモリ 69,724 KB
最終ジャッジ日時 2025-06-12 18:01:55
合計ジャッジ時間 4,934 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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.sort()
    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
    for x in range(1, sqrt_max + 1):
        candidates.add(x)

    # Add X = A_i // k and X+1 for k up to sqrt(A_i)
    for a in A:
        if a == 0:
            continue
        k_max = int(math.isqrt(a)) + 1
        for k in range(1, k_max + 1):
            x1 = a // k
            x2 = x1 + 1
            candidates.add(x1)
            candidates.add(x2)

    # Also add max_A and max_A + 1 to handle cases where X is very large
    candidates.add(max_A)
    candidates.add(max_A + 1)

    # Convert to list and filter X >= 1
    candidates = [x for x in candidates if x >= 1]

    min_f = float('inf')
    min_x = float('inf')

    for x in sorted(candidates):
        prev = None
        count = 0
        for a in A:
            q = a // x
            if q != prev:
                count += 1
                prev = q
        current_f = (x + 1) * count
        if current_f < min_f or (current_f == min_f and x < min_x):
            min_f = current_f
            min_x = x

    print(min_x)
    print(min_f)

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