結果

問題 No.2221 Set X
コンテスト
ユーザー lam6er
提出日時 2025-04-16 15:25:38
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,825 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 82,552 KB
実行使用メモリ 88,404 KB
最終ジャッジ日時 2025-04-16 15:27:25
合計ジャッジ時間 4,711 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12 WA * 1 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    max_A = A[-1]
    has_zero = A[0] == 0

    min_f = float('inf')
    best_x = -1

    # Check X up to 1e5 or max_A, whichever is smaller
    upper = min(10**5, max_A)
    for X in range(1, upper + 1):
        prev = -1
        count = 0
        for a in A:
            q = a // X
            if q != prev:
                count += 1
                prev = q
        current_f = (X + 1) * count
        if current_f < min_f or (current_f == min_f and X < best_x):
            min_f = current_f
            best_x = X

    # Check K=1 case
    if has_zero:
        X_candidate = max_A + 1
        current_f = X_candidate + 1
        if current_f < min_f or (current_f == min_f and X_candidate < best_x):
            min_f = current_f
            best_x = X_candidate

    # Check X = max_A
    X_candidate = max_A
    if X_candidate >= 1:
        prev = -1
        count = 0
        for a in A:
            q = a // X_candidate
            if q != prev:
                count += 1
                prev = q
        current_f = (X_candidate + 1) * count
        if current_f < min_f or (current_f == min_f and X_candidate < best_x):
            min_f = current_f
            best_x = X_candidate

    # Check X = max_A - 1
    X_candidate = max_A - 1
    if X_candidate >= 1:
        prev = -1
        count = 0
        for a in A:
            q = a // X_candidate
            if q != prev:
                count += 1
                prev = q
        current_f = (X_candidate + 1) * count
        if current_f < min_f or (current_f == min_f and X_candidate < best_x):
            min_f = current_f
            best_x = X_candidate

    print(best_x)
    print(min_f)

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