AtCoder ABC 106 C - To Infinity (茶色, 300 点)

十分多い回数重ねるとなにかが収束する系はよく見るん

問題へのリンク

問題概要 (ABC 106 C)

1 から 9 までの数字からなる文字列 S がある。以下の操作を 5000 兆回行う:

• 文字列 S に含まれるそれぞれの 2 が 22, 3 が 333, 4 が 4444, 5 が 55555, 6 が 666666, 7 が 7777777, 8 が 88888888, 9 が 999999999 に置き換わる. 1 は 1 のまま残る.

5000 兆回目の文字列の左から K 文字目は何か？

解法

1 だけはそのまま残るが、それ以外は途方もなく多い個数になる。よって、

• 先頭の 1 が K 個以上だったら 1
• そうでなかったら、「先頭から見て最初の 1 以外の数」

が答え

#include <iostream>
#include <string>
using namespace std;

int main() {
    string S; int K; cin >> S >> K;
    int ichinum = 0;
    for (int i = 0; i < S.size(); ++i) {
        if (S[i] == '1') ++ichinum;
        else break;
    }
    if (ichinum >= K) cout << 1 << endl;
    else cout << S[ichinum] << endl;
}