結果

問題 No.2221 Set X
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:10:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,294 bytes
コンパイル時間 452 ms
コンパイル使用メモリ 82,004 KB
実行使用メモリ 77,468 KB
最終ジャッジ日時 2025-04-15 22:12:04
合計ジャッジ時間 6,668 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18 TLE * 1 -- * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

n = int(input())
A = list(map(int, input().split()))
max_A = A[-1] if n > 0 else 0

min_f = float('inf')
best_x = None

# Handle small X values (1 to sqrt(max_A))
K = int(math.isqrt(max_A)) + 1 if max_A > 0 else 1
for X in range(1, K + 1):
    prev = None
    k = 0
    for a in A:
        q = a // X
        if q != prev:
            k += 1
            prev = q
    current_f = (X + 1) * k
    if current_f < min_f or (current_f == min_f and X < (best_x if best_x is not None else float('inf'))):
        min_f = current_f
        best_x = X

# Handle large X values by enumerating possible q values
if max_A > 0:
    for q in range(1, K + 1):
        X_min = (max_A // (q + 1)) + 1
        X_max = max_A // q
        if X_min > X_max:
            continue
        X = X_min
        prev = None
        k = 0
        for a in A:
            q_val = a // X
            if q_val != prev:
                k += 1
                prev = q_val
        current_f = (X + 1) * k
        if current_f < min_f or (current_f == min_f and X < best_x):
            min_f = current_f
            best_x = X

# Handle q=0 case (X > max_A)
X = max_A + 1
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)
0