Edit

【pythonでABC203を解説】C - Friends and Travel costs

問題概要

問題ページ

C - Friends and Travel costs
C - Friends and Travel costs

問題ページへ移動する

問題文

\(10^{100}+1\) 個の村があり、それぞれ村 \(0\), 村 \(1\), \(\ldots\), 村 \(10^{100}\) と番号がついています。
\(0\) 以上 \(10^{100}-1\) 以下の全ての整数 \(i\) について、村 \(i\) で \(1\) 円を払う事で村 \((i+1)\) に移動することができます。
それ以外の移動方法はありません。

太郎君は初め \(K\) 円を持った状態で村 \(0\) におり、その後、可能な限り大きな番号の村まで進もうとします。
太郎君には \(N\) 人の友達がいます。\(i\) 人目の友達は村 \(A_i\) にいて、太郎君が村 \(A_i\) に着いたときに \(B_i\) 円を太郎君に渡します。
太郎君が最終的にたどり着く村の番号を求めてください。

制約

  • \(1 \leq N \leq 2\times 10^5\)
  • \(1 \leq K \leq 10^9\)
  • \(1 \leq A_i \leq 10^{18}\)
  • \(1 \leq B_i \leq 10^9\)
  • 入力は全て整数である。

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, k = list(map(int, input().rstrip('\n').split()))
    ab = sorted([list(map(int, input().rstrip('\n').split())) for _ in range(n)])
    lst = 0
    for a, b in ab:
        if k - (a - lst) >= 0:
            k -= (a - lst)
            k += b
            lst = a
        else:
            print(lst + k)
            exit()
    print(lst + k)


if __name__ == '__main__':
    solve()

-Edit