みんなのプロコン 2019 C - When I hit my pocket...
備忘録
問題
回答
import sys import os import math import bisect import itertools import collections import heapq import queue import array import time # 時々使う # from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall # from decimal import Decimal # from collections import defaultdict, deque # 再帰の制限設定 sys.setrecursionlimit(10000000) def ii(): return int(sys.stdin.buffer.readline().rstrip()) def il(): return list(map(int, sys.stdin.buffer.readline().split())) def fl(): return list(map(float, sys.stdin.buffer.readline().split())) def iln(n): return [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] def iss(): return sys.stdin.buffer.readline().decode().rstrip() def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split())) def isn(n): return [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] def lcm(x, y): return (x * y) // math.gcd(x, y) MOD = 10 ** 9 + 7 INF = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") K, A, B = il() if A + 1 < B: d, m = divmod(K - (A - 1), 2) print(B + (B - A) * (d - 1) + m) else: print(K+1) if __name__ == '__main__': main()
考え方
ビスケットを増やすために必要な一連の操作が何回行うことができるのかを考えます
- 回答概要
A + 1 >= B
のときは、ビスケットをお金に換える操作を行うたびに合計枚数が減るA + 1 < B
のときは、何回ビスケットとお金の交換を行うことができるのかを考える
A
枚のビスケットを持っている場合、追加で2回の操作(A
枚のビスケットをお金に換えて、お金をB
枚のビスケットにする)を
行うことでビスケットをB
枚にすることが出来ます。
つまり、A + 2
回の操作でB
枚のビスケットを新たに得ることが出来ます。
A + 1 >= B
のとき、A
枚のビスケットをお金に換えて、お金をB
枚のビスケットにするよりも、
素直にビスケットをたたき続けてK
枚のビスケットを得る方が最終的なビスケットの枚数は増えます。
そのため、A + 1 >= B
のときは、K + 1
が回答となります。
次に、A + 1 < B
の場合について考えます。
この時、お金をB
枚のビスケットにするたびにビスケットの最大枚数は増えるため、
そのためA
枚のビスケットをお金に交換し、お金をB
枚のビスケットに交換できる回数を考えます。
まず、はじめはビスケットは1枚のみです。
A
枚のビスケットにするためには、A - 1
回の操作が必要になります。
そのため、A
枚のビスケットを得た時点の、残りの操作回数はK - (A - 1)
回です。
お金を介してB
枚のビスケットにする操作回数は2回必要です。
そのためK - (A - 1) // 2
回、お金を介してB
枚のビスケットを得ることが出来ます。
しかし、お金を介してB
枚のビスケットに交換する方法で、
ビスケットの最大枚数を求めるためには、2つ注意が必要です。
一つは、K - (A - 1) // 2
回の操作以外の余った操作です。
余った操作は単純にビスケットをたたいてビスケットを増やす以外の選択ができないため、
最終的なビスケットの枚数に余りを足す必要があります。
もう一つは、お金を介してB
枚のビスケットを得るとき、1回の操作で増えるビスケットの枚数です。
一番初めの1回目はB
枚のビスケットを得ることができますが、
2回目以降は1度お金を介すため、1度の操作で増えるビスケットの枚数はB - A
枚です。
以上に気を付けて計算を行うことで、最終的なビスケットの最大枚数を求めることが出来ます。