結果

問題 No.2221 Set X
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:16:53
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,353 bytes
コンパイル時間 239 ms
コンパイル使用メモリ 82,524 KB
実行使用メモリ 88,628 KB
最終ジャッジ日時 2025-06-12 21:17:31
合計ジャッジ時間 4,894 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def compute_f(X, A):
    if X == 0:
        return 0
    prev = -1
    count = 0
    for a in A:
        k = a // X
        if k != prev:
            count += 1
            prev = k
    return (X + 1) * count

def find_min_f(A, N):
    max_A = A[-1]
    min_f = float('inf')
    best_X = 0
    # Iterate over possible X values
    for X in range(1, int(max_A ** 0.5) + 2):
        current_f = compute_f(X, A)
        if current_f < min_f or (current_f == min_f and X < best_X):
            min_f = current_f
            best_X = X
    # Also consider X up to max(A)
    for X in range(1, max_A + 1):
        current_f = compute_f(X, A)
        if current_f < min_f or (current_f == min_f and X < best_X):
            min_f = current_f
            best_X = X
    # Also check X larger than max_A
    X = max_A
    current_f = compute_f(X, A)
    if current_f < min_f:
        min_f = current_f
        best_X = X
    X = max_A + 1
    current_f = compute_f(X, A)
    if current_f < min_f:
        min_f = current_f
        best_X = X
    return best_X, min_f

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    if N == 0:
        print(0)
        print(0)
        return
    best_X, min_f = find_min_f(A, N)
    print(best_X)
    print(min_f)

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