ABC106 C - To Infinity

備忘録

問題

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 main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = list(map(int, iss()))
    K = ii()

    for k in range(K):
        if S[k] != 1:
            print(S[k])
            exit()
    else:
        print(1)


if __name__ == '__main__':
    main()

考え方

実際に5000兆日後、生成される文字列Sをシミュレートするのは不可能なので、
文字列が変化する条件からK文字目が何になるのか推測した。

1は1のまま変化することはなく、残り続ける。
そのため、文字列SのK文字目まで1の場合には、回答はかならず1。

1以外の数字Nは5000兆日後、N^5000兆となり、果てしなく大きくなる（K番目を上回る）。

以上のことから、文字列Sのうち、K文字目までが全て1の場合1が回答となり、
K文字目までに1以外の数字Nが存在している場合、数字Nが回答となる。