数字膨胀

ID: 19367

传统题

1000ms

256MiB

难度: 8

上传者:

标签>

模拟

字符串

题目描述

给定一个只包含数字 1 到 9 的字符串 $s$ 。一次变换会同时将字符串中的每个数字 $d$ 替换为连续 $d$ 个数字 $d$ 。

例如，字符串 1234 经过一次变换后会变为 1223334444。

请你求出经过 $10^{10}$ 次变换后，所得字符串的第 $k$ 个字符。保证答案存在。

输入一行，包含一个字符串 $s$ 和一个整数 $k$ 。

输出一行一个数字，表示经过 $10^{10}$ 次变换后字符串的第 $k$ 个字符。

1234 4

31415 11

对于样例 1，数字 1 不会扩展，原串中第一个非 1 字符为 2，经过足够多次变换后第 $4$ 个字符为 2。

对于样例 2，原串第一个字符就是 3。经过足够多次变换后，开头会形成很长一段连续的 3，因此第 $11$ 个字符为 3。

子任务	分值	限制
$1$	$30$	$s长度 \le 20$ ， $k \le 20$
$2$	$70$	$s长度 \le 100$ ， $k \le 10^8$

对于所有数据， $s$ 仅包含 1 到 9，并保证经过 $10^{10}$ 次变换后的字符串长度至少为 $k$ 。