Artifact 65a8b90d6a216ada1c472b8c1ff88ffbacd9beab
#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