結果

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

ソースコード

diff # 

import sys

def main():
    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 up to 200,000
    upper = min(200000, max_A + 2)
    for X in range(1, upper + 1):
        candidates.add(X)
    
    # Add candidates around max_A
    candidates.add(max_A)
    candidates.add(max_A + 1)
    if max_A > 0:
        candidates.add(max_A - 1)
    
    # Add candidates from max_A divided by q
    for q in range(1, 300):
        if q > max_A:
            break
        X = max_A // q
        candidates.add(X)
        candidates.add(X + 1)
    
    # Add candidates from each A_i divided by q
    for a in A:
        for q in range(1, 300):
            if q > a:
                break
            X = a // q
            candidates.add(X)
            candidates.add(X + 1)
    
    min_f = float('inf')
    best_X = -1

    for X in candidates:
        if X <= 0:
            continue
        prev = None
        count = 0
        for a in A:
            q = a // 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

    print(best_X)
    print(min_f)

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