結果

問題 No.2221 Set X
ユーザー gew1fw
提出日時 2025-06-12 21:06:07
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,394 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,452 KB
実行使用メモリ 75,264 KB
最終ジャッジ日時 2025-06-12 21:08:14
合計ジャッジ時間 6,973 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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]))
    if N == 1:
        print(1)
        print(2)
        return
    
    # Compute D_max
    D_max = 0
    for i in range(1, N):
        D_max = max(D_max, A[i] - A[i-1])
    
    K = 30000  # Adjust this based on time constraints
    min_f = float('inf')
    min_x = -1
    
    # Check X up to K
    for X in range(1, K + 1):
        prev = None
        count = 0
        for a in A:
            q = a // X
            if prev is None:
                prev = q
                count = 1
            else:
                if q != prev:
                    count += 1
                    prev = q
        f = (X + 1) * count
        if f < min_f or (f == min_f and X < min_x):
            min_f = f
            min_x = X
    
    # Check X_candidate = D_max + 1
    X_candidate = D_max + 1
    if X_candidate > K:
        q_min = A[0] // X_candidate
        q_max = A[-1] // X_candidate
        count = q_max - q_min + 1
        f = (X_candidate + 1) * count
        if f < min_f or (f == min_f and X_candidate < min_x):
            min_f = f
            min_x = X_candidate
    
    # Check candidates from q
    A_N = A[-1]
    A_1 = A[0]
    for q in range(0, K + 1):
        # Compute X_candidate = ceil(A_N / (q+1))
        X_candidate = (A_N + q) // (q + 1)
        if X_candidate <= K:
            continue
        if X_candidate <= D_max:
            continue
        if X_candidate <= A_1:
            continue
        q_max = A_N // X_candidate
        q_min = A_1 // X_candidate
        count = q_max - q_min + 1
        f = (X_candidate + 1) * count
        if f < min_f or (f == min_f and X_candidate < min_x):
            min_f = f
            min_x = X_candidate
        # Check X_candidate - 1
        X_candidate2 = X_candidate - 1
        if X_candidate2 <= K:
            continue
        if X_candidate2 <= D_max:
            continue
        if X_candidate2 <= A_1:
            continue
        q_max2 = A_N // X_candidate2
        q_min2 = A_1 // X_candidate2
        count2 = q_max2 - q_min2 + 1
        f2 = (X_candidate2 + 1) * count2
        if f2 < min_f or (f2 == min_f and X_candidate2 < min_x):
            min_f = f2
            min_x = X_candidate2
    
    print(min_x)
    print(min_f)

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