ABC146 C - Buy an Integer

備忘録

問題

atcoder.jp

回答

import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def fcal(A, B, N):
    return (A * N) + (B * len(str(N)))


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, X = il()
    s = 10 ** 9

    if fcal(A, B, s) <= X:
        print(s)
        exit()

    ret = [0]
    while True:
        if s in ret: break
        if s == 0:
            ret.append(0)
            break
        if fcal(A, B, s) <= X:
            ret.append(s)
            s += s // 2
        else:
            s = (max(ret) + s) // 2

    print(max(ret))


if __name__ == '__main__':
    main()

考え方

整数Nの範囲が1 ~ 10 ** 9まであり、全ての整数が購入可能か否かを判定すると、TLEになる。
そのため、整数Nの最大値10 ** 9が購入できる場合には、10 ** 9を回答とし、
整数Nの最大値10 ** 9が購入できない場合には

• 整数Nが購入できる場合
  • N + (N // 2) を次の判定対象とする
• 整数Nが購入できない場合
  • (過去に購入可能だった最大値 + N) // 2を次の判定対象とする

を繰り返し行う。
判定対象が同じ過去に判定した数値と同値になった場合、または0になった場合に処理を終了し、
その時点での最大値を回答とする。

探索範囲の最大値と最低値を考え、その中央値で購入可能か否かを判定し、
その結果によって次の中央値を求める。
繰り返し行うことで、条件を満たす最大値を得ることが出来る。