結果

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

ソースコード

diff # 

import sys
import math

def main():
    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
    
    candidates = set()
    max_A = A[-1]
    
    for a in A:
        if a == 0:
            continue
        sqrt_a = int(math.isqrt(a))
        for q in range(1, sqrt_a + 1):
            candidates.add(q)
            candidates.add(a // q)
            candidates.add(a // q + 1)
        for x in [sqrt_a, sqrt_a + 1]:
            candidates.add(x)
            candidates.add(a // x)
            candidates.add(a // x + 1)
    
    for i in range(n-1):
        d = A[i+1] - A[i]
        candidates.add(d)
        candidates.add(d+1)
        candidates.add(d-1)
    
    candidates.add(1)
    candidates.add(max_A)
    candidates.add(max_A + 1)
    candidates.add(max_A - 1)
    
    D = 0
    for i in range(n-1):
        D = max(D, A[i+1] - A[i])
    candidates.add(D)
    candidates.add(D + 1)
    candidates.add(D - 1)
    
    for a in A:
        if a > 0:
            candidates.add(a)
            candidates.add(a + 1)
            candidates.add(a - 1)
    
    candidates = {x for x in candidates if x > 0}
    candidates.add(1)
    candidates.add(2)
    candidates.add(3)
    
    min_f = float('inf')
    best_x = None
    
    for x in sorted(candidates):
        if x == 0:
            continue
        s = set()
        for a in A:
            s.add(a // x)
        k = len(s)
        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)

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