1055 - 끝이없음

step 1

max - min은 대략 100만큼 차이 납니다. 그럼 "i번째 문자가 무엇인가"라는 문제를 i가 min, min+1, ..., max일 때까지 해서 총 100번 물어보면 됩니다. 앞으로의 설명에서는 i번째 문자를 구하는 데에 집중하겠습니다.

step 2

$ 기호가 1개일 때와 2개일 때로 나눌 수 있습니다. $가 1개일 때 먼저 처리하겠습니다. S를 $ 기준으로 앞과 뒤로 나눌 수 있습니다. $ 앞을 (1), $ 뒤를 (2)라고 하면

 

(1) (1) (1).... (1) (1) (입력) (2) (2) (2)... (2) (2)

 

로 만들어 집니다. (1)과 (2)는 (실행시킨 횟수)만큼 반복됩니다. (1)과 (2)의 길이를 구해두면 쉽게 풀 수 있습니다.

step 3

N번 실행시켰을 때 문자열의 길이가 있고 그때 $에 해당하는 문자열의 길이 L이 있을 것입니다. 앞에서부터 문자열을 보면서 $면 L만큼, 아니면 1만큼 카운트를 증가시킵니다. 그럼 i번째 문자가 어디에 해당하는지 알 수 있습니다. 만약 그 문자가 알파벳이면 바로 출력하면 됩니다. 아래는 문제의 첫 번째 예시에서 N을 2, i를 32로 했을 때입니다.

만약 $라면 N 을 1 감소시켰을 때의 문자열에서 내가 찾으려고 한 문자가 몇 번째에 있는지 계산을 합니다. $ 이전에 문자가 몇 개가 있는지 계산하면 쉽게 알 수 있습니다.

이런 식으로 계속 진행하면 답을 구할 수 있습니다.

$기호가 2개 이상이면 프로그램을 실행시킬 때 마다 적어도 2배씩 늘어난다는 뜻입니다. 그럼 프로그램을 30번만 실행시켜도 max범위를 넘어가므로 그 이상을 볼 필요가 없습니다. N의 범위가 1000000000이지만 사실은 최대 30만큼 보면 되기 때문에 해결할 수 있습니다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
char b1[100], b2[100];
int main() {
    long long int i, l1,l2,n,x,y,k,t,cnt=0,j;
    scanf(" %s %s", b1, b2);
    l1 = strlen(b1);
    l2 = strlen(b2);
    scanf("%lld", &n);
    scanf("%lld%lld", &x, &y);
    for (i = 0;i < l2;i++) {
        if (b2[i] == '$') cnt++;
    }
    if (cnt == 1) {
        long long int s = 0, e = 0;
        for (i = 0;i < l2;i++) {
            if (b2[i] == '$') {
                s = i;
                e = l2 - s - 1;
            }
        }
        for (i = x;i <= y;i++) {
            if (i > s * n + e * n + l1) {
                printf("-");
                continue;
            }
            long long int t = i;
            if (t <= s * n) {
                t--;
                t %= s;
                printf("%c", b2[t]);
            }
            else if (t <= s * n + l1) {
                t--;
                t -= s * n;
                printf("%c", b1[t]);
            }
            else {
                t -= s * n + l1;
                t--;
                t %= e;
                printf("%c", b2[s + 1 + t]);
            }
        }
        return 0;
    }
    for (i = x;i <= y;i++) {
        long long int size = l1,countt=0;
        t = i;
        for (j = 1;j <= n;j++) {
            size = size * cnt + (l2 - cnt);
            countt++;
            if (size > i) break;
        }
        if (n == countt && size < i) { printf("-"); continue; }
        for (j = 1;j <= countt;j++) {
            size = (size - (l2 - cnt)) / cnt;
            long long int p = 0;
            for (k = 0;k < l2;k++) {
                if (b2[k] == '$') p += size; else p++;
                if (p >= t) {
                    if (b2[k] != '$') {
                        printf("%c", b2[k]);
                        j = n + 10;
                    }
                    else {
                        t = t-(p - size);
                    }
                    break;
                }
            }
        }
        if (j == countt + 1) printf("%c", b1[t - 1]);
    }
    return 0;
}