読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 1145 : The Genome Database of All Space Life

問題リンク:The Genome Database of All Space Life | Aizu Online Judge

問題概要:
圧縮されたゲノム配列とint型の変数i(0 <= i <= 1000000)が与えられる
ゲノム配列を復元し、ゲノム配列の0-indexedでi番目の値を答えよ
ゲノム配列を復元した際にi番目の値が存在しない場合は0と出力せよ

使用した言語:C++

解法:
答えを求めるために必要なのはゲノム配列の0番からi番までなので圧縮されたゲノム配列の左側から復元していき、サイズがiを越えた時点で復元作業を打ち切り答えを出力する
結局作業が打ち切られずにすべて復元したがサイズがiを越えていない場合は0と出力する


コード:

#include<iostream>
#include<sstream>
#include<cmath>
using namespace std;

class Parsing
{
private:
  string parse;
  int pos;
  int size;
  int x;
public:

  Parsing(string parse,int x):parse(parse),pos(0),x(x),size(0){}

  int StringToInt(string v)
  {
    int ret = 0;
    for(int i=0;i<v.size();i++)
      ret += (v[i]-'0')*(int)pow(10.0,v.size()-i-1);
    return ret;
  }

  string getCnt()
  {
    string v;
    while('0' <= parse[pos] && parse[pos] <= '9') 
      v += parse[pos++];
    return v;  
  }

  int getCntInt(){return StringToInt(getCnt());}

  string decode()
  {
    int power = getCntInt();
    if(parse[pos] == '(')
      pos++;
    else 
      {
	string mes,ret;
	while('A' <= parse[pos] && parse[pos] <= 'Z')	
	  mes += parse[pos++];
	
	for(int i=0;i<power;i++)
	  {
	    ret += mes;
	    if(ret.size() >= x)
	      break;
	  }
	return ret;	  
      }
    string message;
    while(('0' <= parse[pos] && parse[pos] <= '9') || ('A' <= parse[pos] && parse[pos] <= 'Z') )
      {
	if('0' <= parse[pos] && parse[pos] <= '9')
	  message += decode();
	else if('A' <= parse[pos] && parse[pos] <= 'Z')
	  message += parse[pos++];
      }  
    
    if(parse[pos] == ')')
      pos++;
    
    string ret;
    for(int i=0;i<power;i++)
      {
	ret += message,size += message.size();
	if(ret.size() >= x)
	  break;
      }
    return ret;
  }
  
  string exp()
  {
    string ret;
    for(;pos<parse.size();)
      {
	if('0' <= parse[pos] && parse[pos] <= '9')
	  ret += decode();
	else
	  ret += parse[pos++],size++;
	if(ret.size() >= x)
	  break;
      }
    return ret;
  }

  int getSize(){return size;}

};

int main()
{
  string Genome;  
  int pos;
  while(cin >> Genome >> pos, Genome != "0" || pos != 0)
    {
      Parsing par = Parsing(Genome,pos+1);
      string message = par.exp();
      if(message.size() <= pos)
	cout << 0 << endl;
	else
	  cout << message[pos] << endl;
    }
  return 0;
}