Artifact 65a8b90d6a216ada1c472b8c1ff88ffbacd9beab

• File SRM/438-U/1B.cpp
  • 2011-02-23 09:21:16 - part of checkin [4fd800b3a8] on branch trunk - Copied from private svn repository. (user: kinaba) [annotate]

#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;

string g_input;
string g_program;
LL g_num_d;
LL g_non_d;

class EndlessStringMachine {
public:
	string getFragment(string input, string program, int s_, int min_, int max_) 
	{
		LL s = s_;
		LL min = min_ - 1;
		LL max = max_;

		int nd = 0, id = -1;
		for(int i=0; i!=program.size(); ++i)
			if( program[i]=='$' )
				++nd, id=i;

		if( nd == 0 )
		{
			string result;
			for(LL i=min; i<max; ++i)
				result += (i < program.size() ? program[i] : '-');
			return result;
		}
		else if( nd == 1 )
		{
			// output = program[..id]^s input program[id+1..]^s
			string L = program.substr(0, id);
			string C = input;
			string R = program.substr(id+1);
			string result;
			for(LL i=min; i<max; ++i)
				if( i < L.size()*s )
					result += L[i%L.size()];
				else if( i < L.size()*s + C.size() ) 
					result += C[i - L.size()*s];
				else if( i < L.size()*s + C.size() + R.size()*s )
					result += R[(i-L.size()*s-C.size()) % R.size()];
				else
					result += '-';
			return result;
		}
		else
		{
			g_input = input;
			g_program = program;
			g_num_d = nd;
			g_non_d = program.size() - nd;

			string result;
			for(int i=min; i<max; ++i)
				result += theChar(i, s);
			return result;
		}
	}

	char theChar( LL i, LL s )
	{
		if( s == 0 )
		{
			return ( i < g_input.size() ? g_input[i] : '-' );
		}

		LL cur = 0;
		for(LL ip=0; ip<g_program.size(); ++ip)
		{
			if( g_program[ip]=='$' ) {
				LL len = theLen(s-1);
				if( cur<=i && i<cur+len )
				{
					i -= cur;
					LL theLevel = 0, lvLen = g_input.size();
					while( lvLen <= i )
						theLevel ++, lvLen = lvLen*g_num_d + g_non_d;
					return theChar(i, theLevel);
				}
				else
					cur += len;
			} else {
				if( cur == i )
					return g_program[ip];
				else
					cur += 1;
			}
		}
		return '-';
	}

	LL theLen(LL s)
	{
		if( s == 0 )
			return g_input.size();
		if( s > 32 )
			return 2000000000LL;
		LL pr = theLen(s-1);
		LL nx = pr*g_num_d + g_non_d;
		return min(2000000000LL, nx);
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }

template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
int verify_case(const string &Expected, const string &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;}

template<int N> struct Case_ { Case_(){start_time=clock();} };
char Test_(...);
int Test_(Case_<0>) {
	string input = "a"; 
	string program = "$meric$"; 
	int s = 6; 
	int min = 1; 
	int max = 35; 
	string RetVal = "americamericamericamericamericameri"; 
	return verify_case(RetVal, EndlessStringMachine().getFragment(input, program, s, min, max)); }
int Test_(Case_<1>) {
	string input = "top"; 
	string program = "$coder"; 
	int s = 1; 
	int min = 1; 
	int max = 20; 
	string RetVal = "topcoder------------"; 
	return verify_case(RetVal, EndlessStringMachine().getFragment(input, program, s, min, max)); }
int Test_(Case_<2>) {
	string input = "abc"; 
	string program = "$x$y$z$"; 
	int s = 10; 
	int min = 30; 
	int max = 50; 
	string RetVal = "bcyabcxabcyabczabczab"; 
	return verify_case(RetVal, EndlessStringMachine().getFragment(input, program, s, min, max)); }
int Test_(Case_<3>) {
	string input = "xy"; 
	string program = "$a$bb"; 
	int s = 12; 
	int min = 5000; 
	int max = 5099; 
	string RetVal = "xybbbbaxyaxybbaxyaxybbbbbbbbaxyaxybbaxyaxybbbbaxyaxybbaxyaxybbbbbbaxyaxybbaxyaxybbbbaxyaxybbaxyaxybb"; 
	return verify_case(RetVal, EndlessStringMachine().getFragment(input, program, s, min, max)); }
int Test_(Case_<4>) {
	string input = "x"; 
	string program = "$y$"; 
	int s = 999999999; 
	int min = 5000; 
	int max = 5001; 
	string RetVal = "xx";
	return verify_case(RetVal, EndlessStringMachine().getFragment(input, program, s, min, max)); }

template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<>      void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE