結果

問題 No.2221 Set X
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:10:02
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,720 bytes
コンパイル時間 251 ms
コンパイル使用メモリ 81,668 KB
実行使用メモリ 71,988 KB
最終ジャッジ日時 2025-04-15 22:11:30
合計ジャッジ時間 4,856 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

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

if n == 1:
    print(1)
    print(2)
    exit()

diffs = []
for i in range(n-1):
    diffs.append(A[i+1] - A[i])

def get_factors(x):
    if x == 0:
        return set()
    factors = set()
    for i in range(1, int(math.isqrt(x)) + 1):
        if x % i == 0:
            factors.add(i)
            factors.add(x // i)
    return factors

candidates = set()

for d in diffs:
    factors = get_factors(d)
    candidates.update(factors)

for num in A:
    if num == 0:
        continue
    factors = get_factors(num)
    candidates.update(factors)

candidates.add(1)
candidates.add(A[-1])
candidates.add(A[-1] + 1)

sqrt_max = int(math.isqrt(A[-1])) + 2 if A[-1] > 0 else 1
for x in range(max(1, sqrt_max - 5), sqrt_max + 5):
    candidates.add(x)

min_f = float('inf')
best_x = None

for x in candidates:
    if x <= 0:
        continue
    prev = None
    k = 0
    for a in A:
        q = a // x
        if prev is None:
            prev = q
            k = 1
        else:
            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):
        min_f = current_f
        best_x = x

x = A[-1] + 1
current_f = (x + 1) * 1
if current_f < min_f or (current_f == min_f and x < best_x):
    min_f = current_f
    best_x = x

x = A[-1]
prev = None
k = 0
for a in A:
    q = a // x
    if prev is None:
        prev = q
        k = 1
    else:
        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):
    min_f = current_f
    best_x = x

print(best_x)
print(min_f)
0