結果

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

ソースコード

diff # 

import sys

def main():
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    if N == 0:
        print(0)
        return
    
    # Compute the maximum difference between consecutive elements
    d_max = 0
    if N > 1:
        diffs = [A[i+1] - A[i] for i in range(N-1)]
        d_max = max(diffs) if diffs else 0
    
    # Generate candidate X values
    candidates = set()
    
    # Candidates around d_max
    start = max(1, d_max - 2)
    for x in range(start, d_max + 3):
        candidates.add(x)
    
    # Candidates from A_i divided by m (1, 2, 3)
    for a in A:
        for m in range(1, 4):
            if m > a:
                continue
            div = a // m
            candidates.add(div)
            candidates.add(div + 1)
            candidates.add(div - 1)
    
    # Add X=1 and X=A_N + 1
    candidates.add(1)
    if N > 0:
        candidates.add(A[-1] + 1)
    
    # Process each candidate X
    min_product = float('inf')
    min_x = -1
    
    for x in candidates:
        if x <= 0:
            continue
        
        prev = None
        count = 0
        for a in A:
            current = a // x
            if prev is None:
                prev = current
                count = 1
            else:
                if current != prev:
                    count += 1
                    prev = current
        
        product = (x + 1) * count
        if product < min_product or (product == min_product and x < min_x):
            min_product = product
            min_x = x
    
    print(min_x)
    print(min_product)

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