ARC088 C - Multiple Gift

AtCoder Python3

備忘録

問題

atcoder.jp

回答

import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, 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()
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]


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

    X, Y = il()
    ret = 0
    while True:
        X *= 2
        ret += 1
        if X > Y: break

    print(ret)


if __name__ == '__main__':
    main()

考え方

条件(Ai+1はAiの倍数であり..)から数列A(A1, A2, A3 ... An)のA2はA1 * 2となるため、
数列Aの最小値となるXを2倍し続け、Yを上回るまでの回数を数えることで、
数列の長さを求めることができる。