結果

問題 No.1440 The Quiz Competition
コンテスト
ユーザー lam6er
提出日時 2025-04-09 20:56:28
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,002 bytes
コンパイル時間 307 ms
コンパイル使用メモリ 82,316 KB
実行使用メモリ 71,756 KB
最終ジャッジ日時 2025-04-09 20:58:07
合計ジャッジ時間 2,460 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def compute_sum_p(x, k_minus_1):
    if k_minus_1 == 0:
        return 0
    m = x // k_minus_1
    r = x % k_minus_1
    sum_p = r * ((m+1)*(m+2)//2) + (k_minus_1 - r)*(m*(m+1)//2)
    return sum_p

def solve():
    input = sys.stdin.read().split()
    idx = 0
    T = int(input[idx])
    idx +=1
    for _ in range(T):
        N = int(input[idx])
        A = int(input[idx+1])
        W = int(input[idx+2])
        K = int(input[idx+3])
        idx +=4
        
        if K == 1:
            if N < 1:
                print(":(")
            else:
                print(A)
            continue
        
        low = 0
        high = A
        best = -1
        K_1 = K-1
        while low <= high:
            mid_a = (low + high) // 2
            limit = A - K*mid_a - (K-1)
            if limit < 0:
                high = mid_a -1
                continue
            x_low = 0
            x_high = W
            best_x = -1
            while x_low <= x_high:
                mid_x = (x_low + x_high) //2
                sp = compute_sum_p(mid_x, K_1)
                if sp <= limit:
                    best_x = mid_x
                    x_low = mid_x +1
                else:
                    x_high = mid_x -1
            if best_x == -1:
                high = mid_a -1
                continue
            sum_p = compute_sum_p(best_x, K_1)
            if sum_p > limit:
                high = mid_a -1
                continue
            
            required_x = best_x
            if (N - K) >0:
                if required_x <= W:
                    best = mid_a
                    low = mid_a +1
                else:
                    high = mid_a -1
            else:
                if required_x == W:
                    best = mid_a
                    low = mid_a +1
                else:
                    high = mid_a -1
        
        if best == -1:
            print(":(")
        else:
            print(best)

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