문제
풀이 해설
점화식
$i$번째 실행의 총 문자열 길이를 $A_i$, 처음 입력 문자열의 길이를 $l$, 두번째 입력 문자열에서 $의 개수를 $n$, $ 를 제외한 문자열의 길이를 $m$이라 한다면
$$A_i = n * A_{i-1} + m $$
0번 실행 시 $ A_0 = l $라 가정한다면,
$$A_i = m \times \cfrac{n^i - 1}{n-1} + n^i \times l $$
따라서 $i$번 실행시 총 문자열의 길이를 계산해 낼 수 있기 때문에, modular를 잘 활용한다면, 특정 자리수의 문자열이 무엇인지 구할 수 있게 되고, 문제를 풀어낼 수 있게 된다.
다만, 문제 조건에서 처음 문자열의 길이가 최대 50, 두번째 문자열의 길이가 2~50, 실행 횟수가 1 ~ 1,000,000,000이기 때문에, 최악의 경우를 생각한다면, 50개 자리 문자열 입력, 그리고 실행 횟수가 $10^{9}$일 경우에, 문자열의 길이는 대충 $50^{10^{9}}$ 정도의 경이로운 숫자가 나올 수 있다.
이는 문자열을 직접 구하는 것은 물론이고, 문자열의 길이조차 직접 계산하는데 한참이 걸린다. 시간 제한이 2초이기 때문에 여기까지만 본다면 불가능한 문제일 수 도 있다. 하지만, 마지막 문제 조건인 최소값 $m$의 크기가 1,000,000,000이기 때문에 문자열의 길이가 $m$의 최대값만 넘기지 않으면 되기 떄문에, 이를 이용해서 문제를 풀 수 있게 된다.
구분
문자열에 $가 2개이상 포함될 경우에는 실행마다 지수적으로 문자가 증가하게 된다. $를 2개 이상 포함하는 경우에서, 최소한의 문자열 입력을 생각한다면, 한 문자 입력과 $$가 입력된 경우를 생각해 볼 수 있다.
이 때, $2^{30} \approx 10^{9}$이기 때문에, $가 2번 이상 넘어가는 경우에는 30번 이상 실행되는 경우에 대해서는 생각해줄 필요가 없다.
-
$가 하나 포함된 경우 -
$가 2개 이상 포함된 경우
로 구분하여서 풀었다
테스트 케이스
문제에서 제공되는 테스트 케이스가 그리 충분하지는 않다. 다만, 엣지 케이스가 그렇게 많이 존재하지는 않는 것 같고 만약 안될 경우에는
- 출력 범위가 실행 후 총 문자열 길이를 넘어서는지(아예 -로만 출력되는 경우 등)
- 2번째 문자열 입력에 이
$로 끝나는지 - 2번째 문자열 입력이
$로만 구성되어있는지
정도만 생각하면 될 것 같다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
def solve(a, S, r, m, M):
a = a
S = S.split('$')[1:]
r, m, M = int(r), int(m), int(M)
len_a = len(a)
len_S = list(map(len, S))
total_len_S = sum(len_S)
initial = a + a.join(S)
ans = ''
if len(S) == 1:
total_len = len_a + total_len_S * r
ans = ''
for k in range(m, M+1):
if k <= len_a:
ans += a[k - 1]
elif k <= total_len:
ans += S[0][(k - len_a) % total_len_S - 1]
else:
ans += '-'
else:
cycle = []
cycle.append(total_len_S + len_a * len(S))
limit = M
if r <= 30:
total_len = total_len_S * (len(len_S) ** r - 1)/(len(len_S) - 1) + (len(len_S) ** r) * len_a
limit = min(M, total_len)
while cycle[-1] < limit:
cycle.append(total_len_S + cycle[-1] * len(S))
for k in range(m, M+1):
temp = k
if k > cycle[-1]:
ans += '-'
continue
init_final = True
for i in range(len(cycle)-1, -1, -1):
j = 0
while j < len(S):
if cycle[i] >= temp: # 첫번째 실행에 포함된 문자열
init_final = True
break
temp -= cycle[i]
if len_S[j] >= temp:
init_final = False
break
temp -= len_S[j]
j += 1
if not init_final:
break
if init_final:
ans += initial[temp-1]
else:
ans += S[j][temp-1]
return ans
a = input()
S = input()
r = input()
m, M = input().split()
print(solve(a, S, r, m, M))