結果

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

ソースコード

diff # 

import math

n = int(input())
A = list(map(int, input().split()))
A.sort()

max_A = A[-1]
sqrt_max = int(math.isqrt(max_A)) + 2

max_diff = 0
for i in range(1, n):
    max_diff = max(max_diff, A[i] - A[i-1])

candidates = []

# Case 1: X up to sqrt(max_A)
for X in range(1, sqrt_max + 1):
    prev = None
    count = 0
    for a in A:
        q = a // X
        if q != prev:
            count += 1
            prev = q
    f = (X + 1) * count
    candidates.append((X, f))

# Case 2: q up to sqrt_max
for q in range(0, sqrt_max + 1):
    current_max = 0
    for a in A:
        if a == 0:
            temp = 0
        else:
            temp = a // (q + 1)
        if temp > current_max:
            current_max = temp
    X_candidate = current_max + 1
    if X_candidate <= sqrt_max:
        continue
    # Compute count for X_candidate
    prev = None
    count = 0
    for a in A:
        q_val = a // X_candidate
        if q_val != prev:
            count += 1
            prev = q_val
    f = (X_candidate + 1) * count
    candidates.append((X_candidate, f))

# Case 3: X = max_diff + 1
X_case3 = max_diff + 1
prev = None
count = 0
for a in A:
    q_val = a // X_case3
    if q_val != prev:
        count += 1
        prev = q_val
f_case3 = (X_case3 + 1) * count
candidates.append((X_case3, f_case3))

# Case 4: X = max_A + 1
X_case4 = max_A + 1
f_case4 = (X_case4 + 1) * 1
candidates.append((X_case4, f_case4))

# Find the minimal f and the smallest X
min_f = float('inf')
best_X = float('inf')
for x, f in candidates:
    if f < min_f or (f == min_f and x < best_X):
        min_f = f
        best_X = x

print(best_X)
print(min_f)
0