【ABC203 C】「Friends and Travel costs」を解く【Python3】

コンテスト一覧へ

 

K円を持った状態で村0にいる太郎君が、友達N人を頼って、最大どの番号の村までたどり着けるのか求める問題です。

提出
n, k = map(int, input().split())
ab=[list(map(int,input().split())) for _ in range(n)]

ab.sort()
now = 0

for a,b in ab:
    if k < a-now:
        print(now+k)
        exit()
    else:
        k -= a-now
        k += b
        now = a

s = 10**100
if k < s-now:
    print(now+k)
else:
    print(s)

入力はすべて整数です。

abをaの要素でソートし、[a, b]を順番に、村aまでたどり着けるのかどうか判定します。

今持っている「お金k」が、村aから「現在地now」を引いた値よりも小さい場合、村aにはたどり着けないので、現在地nowからお金k分だけ進んだ場所が答えになります。

そうでない場合は、「お金k」から「村aから現在地nowを引いた値(進んだ分の金額)」を引き、貰ったお金bを足します。

今度は、村aの位置が現在地nowになるので、それを代入します。

すべての[a, b]を確認することができたら、後は「村10100」にたどり着けるのかチェックします。

たどり着けない場合は、「now+k」が答えになり

たどり着ける場合は、「10100」が答えになります。

【ABC203】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。