実行時間制限: 2 sec / メモリ制限: 976 MB
配点: 300 点
問題文
Mr. Infinity は, 1
から 9
までの数字からなる文字列 S を持っている. この文字列は, 日付が変わるたびに次のように変化する.
- 文字列 S に含まれるそれぞれの
2
が22
,3
が333
,4
が4444
,5
が55555
,6
が666666
,7
が7777777
,8
が88888888
,9
が999999999
に置き換わる.1
は1
のまま残る.
例えば, S が 1324
の場合, 翌日には 1333224444
になり, 翌々日には 133333333322224444444444444444
になる.
あなたは 5000 兆日後に文字列がどのようになっているか知りたい. 5000 兆日後の文字列の左から K 文字目は何か?
制約
- S は 1 文字以上 100 文字以下の文字列.
- K は 1 以上 10^{18} 以下の整数.
- 5000 兆日後の文字列の長さは K 文字以上である.
入力
入力は以下の形式で標準入力から与えられる.
S K
出力
5000 兆日後に Mr. Infinity が持っている文字列の K 文字目の数字を出力しなさい.
入力例 1
1214 4
出力例 1
2
文字列 S は次のように変化していく.
- 現在:
1214
- 1 日後:
12214444
- 2 日後:
1222214444444444444444
- 3 日後:
12222222214444444444444444444444444444444444444444444444444444444444444444
5000 兆日後の文字列の最初 5 文字は 12222
となる. K=4 なので, 4 文字目の 2
を出力すればよい.
入力例 2
3 157
出力例 2
3
文字列ははじめ 3
である. 5000 兆日経ったとき, 文字列は 3
だけで構成される.
入力例 3
299792458 9460730472580800
出力例 3
2
Score: 300 points
Problem Statement
Mr. Infinity has a string S consisting of digits from 1
to 9
. Each time the date changes, this string changes as follows:
- Each occurrence of
2
in S is replaced with22
. Similarly, each3
becomes333
,4
becomes4444
,5
becomes55555
,6
becomes666666
,7
becomes7777777
,8
becomes88888888
and9
becomes999999999
.1
remains as1
.
For example, if S is 1324
, it becomes 1333224444
the next day, and it becomes 133333333322224444444444444444
the day after next.
You are interested in what the string looks like after 5 \times 10^{15} days. What is the K-th character from the left in the string after 5 \times 10^{15} days?
Constraints
- S is a string of length between 1 and 100 (inclusive).
- K is an integer between 1 and 10^{18} (inclusive).
- The length of the string after 5 \times 10^{15} days is at least K.
Input
Input is given from Standard Input in the following format:
S K
Output
Print the K-th character from the left in Mr. Infinity's string after 5 \times 10^{15} days.
Sample Input 1
1214 4
Sample Output 1
2
The string S changes as follows:
- Now:
1214
- After one day:
12214444
- After two days:
1222214444444444444444
- After three days:
12222222214444444444444444444444444444444444444444444444444444444444444444
The first five characters in the string after 5 \times 10^{15} days is 12222
. As K=4, we should print the fourth character, 2
.
Sample Input 2
3 157
Sample Output 2
3
The initial string is 3
. The string after 5 \times 10^{15} days consists only of 3
.
Sample Input 3
299792458 9460730472580800
Sample Output 3
2