Algoogle

Algorithm for Programming Contest

AOJ 1145 The Genome Database of All Space Life

Category: AOJ Tag: parsing

The Genome Database of All Space Life

問題概要


繰り返される部分が圧縮されている文字列が与えられる.
その文字列を復元した時のi番目の文字を答えよ.
ただし存在しない場合は’0’と答えること.

解法


再帰で構文解析していく.
数字があって, その繰り返しの中に答えがある場合, 繰り返しの頭から何番目にあるのか求めて改めてその繰り返しの仲を調べる.

コード


(1145.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,a) repi(i,0,a)
string s;
int n, cur;

int number(){
    int ret = 0;
    while(isdigit(s[cur]))
        ret = ret*10+s[cur++]-'0';
    return ret;
}

int seq(int sum){
    if(cur == (int)s.size()) return 0;
    if(s[cur] == '('){ cur++; return seq(sum);}
    if(s[cur] == ')'){ cur++; return 0;}
    if(isalpha(s[cur])) {
        if(sum == n) throw s[cur];
        cur++;
        return 1+seq(sum+1);
    }
    int m = number(), l;
    int head = cur;
    if(isalpha(s[cur])) { l = 1; cur++;}
    else l = seq(sum);
    if(l*m+sum > n) {
        cur = head;
        n = (n-sum)%l;
        seq(0);
    }
    return l*m+seq(sum+l*m);
}

char solve(){
    cur = 0;
    try{ seq(0);}
    catch(char e){ return e;}
    return '0';
}

int main(){
    while(cin >> s >> n, s!="0") cout << solve() << endl;
    return 0;
}

Comments