結果

問題 No.2221 Set X
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:52:00
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,092 bytes
コンパイル時間 227 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 275,064 KB
最終ジャッジ日時 2025-06-12 19:52:34
合計ジャッジ時間 6,885 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

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]

    candidates = set()
    for a in A:
        if a == 0:
            continue
        k = int(math.sqrt(a))
        if k > 0:
            candidates.add(k)
            candidates.add(k-1)
            candidates.add(k+1)
        k = int(math.sqrt(a)) + 1
        candidates.add(k)
    candidates.add(1)
    candidates.add(max_A)
    candidates.add(max_A + 1)
    candidates.add(0)
    candidates = [x for x in candidates if x >= 1]
    candidates.sort()

    best_X = 1
    min_f = float('inf')
    
    for X in candidates:
        current = set()
        for a in A:
            q = a // X
            current.add(q)
            if len(current) > min_f:
                break  # 优化，提前退出
        D = len(current)
        f = (X + 1) * D
        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