AOJ1145 The Genome Database of All Space Life

2015/03/24 (Tue) AOJ 構文解析

日本語問題文あり

「$ length(k,l,r) = $ 文字列の区間 $[l,r)$ を展開したときの $k$ 番目の文字」とおく． あとは頑張る．繰り返すアルファベットが $1$ 文字の場合でも強制的に括弧を付けるようにすると楽になった．

#include <cstring>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cassert>
using namespace std;

char s[5000];

int length(int const k, int const l, int const r){
    int cur = 0, res = 0, p = l;
    while(s[p] && p < r){
        if(isalpha(s[p])){
            while(isalpha(s[p])){
                if(cur == k) throw s[p];
                res++;
                p++;
                cur++;
            }
        } else if(isdigit(s[p])){
            int mul = 0;
            while(isdigit(s[p])){
                mul = mul * 10 + s[p] - '0';
                p++;
            }
            int d = 0, i = p++;
            while(1){
                if(s[i] == '(') d++;
                else if(s[i] == ')') d--;
                if(d == 0) break;
                i++;
            }
            int memo = -1;
            for(int j = 0; j < mul; j++){
                if(memo != -1 && cur + memo < k){
                    res += memo;
                    cur += memo;
                } else {
                    int x = length(k - cur, p, i);
                    res += x;
                    cur += x;
                    memo = x;
                }
            }
            p = i + 1;
        }
    }
    return res;
}

int main(){
    static char t[5000];
    int k;
    while(scanf("%s%d",t,&k), t[0] != '0'){
        int tlen = strlen(t);
        int len = 0;
        for(int i = 0; i < tlen; i++){
            if(i > 0 && isdigit(t[i - 1]) && isalpha(t[i])){
                s[len++] = '(';
                s[len++] = t[i];
                s[len++] = ')';
            } else {
                s[len++] = t[i];
            }
        }
        s[len] = 0;
        try{
            length(k, 0, len);
            putchar('0');putchar('\n');
        } catch (char e) {
            putchar(e);putchar('\n');
        }
    }
}