S2. Cryptogram Cracking Club
레이팅 미적용의견: 0
Cyrene, the captain of the Cryptogram Cracking Club (CCC), came
across a concerningly long cipher. Conveniently, this cipher is composed
of lower-case characters (a-z). Comfortingly, the cipher is
composed of a pattern that repeats infinitely.
Cyrene wishes to locate the \(c\)-th
character of the cipher. To make your job easier, the CCC members have
extracted the repeated pattern and compressed it using the Run-Length
Encoding (RLE) algorithm, which replaces consecutive repeated characters
with a single occurrence of the character followed by a count of how
many times it was repeated. For example, for the pattern
aaaabccdddd, the RLE algorithm outputs
a4b1c2d4.
You are given the output of the RLE algorithm for a certain pattern.
Can you determine the \(c\)-th
character of the long cipher that is formed by repeating this pattern
infinitely?
The first line of input will consist of a string \(S\), representing a pattern produced by the
RLE algorithm. The length of \(S\) will
be at least \(2\) and at most \(2\cdot 10^5\). Additionally, all numbers
appearing in \(S\) are between \(1\) and \(10^{12}\).
The next line of input contains a single integer \(c\), representing the index of the
character you wish to locate, starting from index \(0\).
Output the \(c\)-th character of the
long cipher.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 40점 | \(0\le c \le 2000\) — All numbers appearing in \(S\) are between \(1\) and \(9\) (inclusive) and the length of the repeated pattern is at most \(2000\) characters. |
2 | 20점 | \(0\le c \le 10^6\) — The length of the repeated pattern is at most \(10^6\) characters. |
3 | 20점 | \(0\le c \le 10^{12}\) — The length of the repeated pattern is at most \(10^6\) characters. |
4 | 20점 | \(0\le c \le 10^{12}\) — No additional constraints. |
r2d2
8rThe output of the RLE algorithm r2d2 corresponds to the
pattern rrdd, which creates the infinitely long cipher
rrddrrddrrddrrdd..., where the \(c = 8\)th character is r.
a4b1c2d10
100dThe output of the RLE algorithm a4b1c2d10 corresponds to
the pattern aaaabccdddddddddd. When repeated infinitely,
the \(c = 100\)th character is
d.
평가 및 의견
S2. Cryptogram Cracking Club
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
S2. Cryptogram Cracking Club