PKU 3010 The Genome Database of All Space Life

http://poj.org/problem?id=3010
圧縮された文字列を展開してn番目の文字を答えろというような問題。

1文字だけの繰り返しの処理にドハマリして結構時間かかりました。

string in;
int p;

void next(int& p){
  ++p;
  while(p<SZ(in) && in[p]!=')'){
    if(in[p]=='(')next(p);
    else ++p;
  }
  ++p;
}

ll get(int po,int re){
  ll le=0;
  if(in[po]!='(')return 1;
  ++po;
  while(po<SZ(in) && in[po]!=')'){
    if(isdigit(in[po])){
      ll t=0;
      while(isdigit(in[po]))t=t*10+in[po++]-'0';
      ll cle=get(po,re);
      if(cle==-1)return -1;
      le+=cle*t;
      if(in[po]=='(')next(po);
      else ++po;
    }else{
      ++le;
      ++po;
    }
    if(le>re)return -1;
  }
  return le;
}

char rec(int po,int re){
  while(po<SZ(in)){
    //cout<<po<<' '<<re<<endl;
    if(isdigit(in[po])){
      ll t=0;
      while(isdigit(in[po]))t=t*10+in[po++]-'0';
      ll len=get(po,re);
      //cout<<len<<endl;
      int de=0;
      if(in[po]=='(')++de;
      if(len==-1)return rec(po+de,re);
      else if(re<t*len)return rec(po+de,re%len);
      re-=t*len;
      //cout<<re<<endl;
      if(de)next(po);
      else ++po;
    }else{
      if(re==0)return in[po];
      ++po;
      --re;
    }
  }
  ++po;
  return '0';
}



main(){
  while(cin>>in>>p,in!="0")
    cout<<rec(0,p)<<endl;
}