結果

問題 No.2221 Set X
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:44:25
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,754 bytes
コンパイル時間 358 ms
コンパイル使用メモリ 81,808 KB
実行使用メモリ 91,256 KB
最終ジャッジ日時 2025-04-16 15:47:14
合計ジャッジ時間 4,865 ms
ジャッジサーバーID
（参考情報） 		judge2 / 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]
    candidates = set()

    # Collect candidates from each A_i divided by k
    for a in A:
        if a == 0:
            continue
        sqrt_a = int(math.isqrt(a))
        for k in range(1, sqrt_a + 1):
            x1 = a // k
            candidates.add(x1)
            candidates.add(x1 + 1)
        # Also handle the case where k > sqrt(a)
        for m in range(1, sqrt_a + 1):
            if m == 0:
                continue
            x2 = m
            if x2 <= sqrt_a:
                continue
            candidates.add(a // x2)
            candidates.add(a // x2 + 1)

    # 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 = max_A + 1
    candidates.add(max_A + 1)

    # Convert to sorted list
    candidates = sorted(candidates)

    min_f = float('inf')
    best_x = -1

    for x in candidates:
        if x <= 0:
            continue
        prev = -1
        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 < best_x):
            min_f = current_f
            best_x = x

    # Check X = max_A + 1 if not already considered
    x = max_A + 1
    if x not in candidates:
        current_f = x + 1
        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