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; }