Artifact a7fda6c5ea37e4b7086088b85238e8dece9c39ce

• File SRM/434-U/1C-U.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 <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
using namespace std;
typedef long long LL;

class IncreasingLists {
public:
	string ans;
	typedef pair<int,pair<string,string> > key;
	map<key,bool> memo;

	vector<string> cm;

	string makeIncreasingList(string mask) 
	{
		string buf(mask);
		comma(mask, 0, 1, 0, buf);

		for(int i=0; i<cm.size(); ++i)
		{
			// try_fill
		}

		return rec(mask, 0, "", "", buf) ? ans : "impossible";
	}

	void comma( const string& mask, int i, int prev, int cur, string& buf )
	{
		if( i==mask.size() || mask[i]==',' )
			if( prev > cur )
				return;
		if( i==mask.size() ) {
			cm.push_back(buf);
			return;
		}
		if( mask[i]==',' ) {
			buf[i] = ',';
			comma( mask, i+1, cur, 0, buf );
		}
		else if( mask[i]=='?' ) {
			if( prev<=cur ) {
				buf[i]=',';
				comma( mask, i+1, cur, 0, buf );
			}
			buf[i]='?';
			comma( mask, i+1, prev, cur+1, buf );
		}
		else {
			buf[i] = mask[i];
			comma( mask, i+1, prev, cur+1, buf );
		}
	}

	bool rec(const string& mask, int i, const string& prev, const string& cur, string& buf)
	{
		key k(i, make_pair(prev,cur));
		if( memo.count(k) )
			return false;
		if( i==mask.size() || mask[i]==',' )
		{
			if( prev.size() > cur.size()
			 || prev.size() == cur.size() && prev>=cur )
				return false;
		}

		if( i==mask.size() ) {
			ans = buf;
			return true;
		}

		if( mask[i]==',' )
			return rec(mask, i+1, cur, "", buf);

		if( '0' <= mask[i] && mask[i] <='9' )
			return rec(mask, i+1, prev, cur+mask[i], buf);

		// try ,
		if( !(prev.size()>cur.size() || prev.size()==cur.size() && prev>=cur) ) {
			buf[i] = ',';
			if( rec(mask, i+1, cur, "", buf) )
				return true;
		}
		// try 0
		for(int d=0; d<9; ++d)
			if(cur.size()>0 || d>0) {
				buf[i] = char(d+'0');
				if( rec(mask, i+1, prev, cur+char(d+'0'), buf) )
					return true;
			}
		return memo[k] = false;
	}
};

// 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 mask = "??"; 
	string RetVal = "10"; 
	return verify_case(RetVal, IncreasingLists().makeIncreasingList(mask)); }
int Test_(Case_<1>) {
	string mask = "???"; 
	string RetVal = "1,2"; 
	return verify_case(RetVal, IncreasingLists().makeIncreasingList(mask)); }
int Test_(Case_<2>) {
	string mask = "?????????,9"; 
	string RetVal = "1,2,3,4,5,9"; 
	return verify_case(RetVal, IncreasingLists().makeIncreasingList(mask)); }
int Test_(Case_<3>) {
	string mask = "??????????,9"; 
	string RetVal = "impossible"; 
	return verify_case(RetVal, IncreasingLists().makeIncreasingList(mask)); }
int Test_(Case_<4>) {
	string mask = "?,10,?????????????????,16,??"; 
	string RetVal = "impossible"; 
	return verify_case(RetVal, IncreasingLists().makeIncreasingList(mask)); }
int Test_(Case_<5>) {
	string mask = "?2?5??7?,??"; 
	string RetVal = "12,50,70,71"; 
	return verify_case(RetVal, IncreasingLists().makeIncreasingList(mask)); }
int Test_(Case_<6>) {
	string mask = "???????????????????????????????,???"; 
	string RetVal = "1,10,11,100,101,102,103,104,105,106"; 
	return verify_case(RetVal, IncreasingLists().makeIncreasingList(mask)); }
int Test_(Case_<7>) {
	string mask   = "??????????????????????????????????????????????????";
	string RetVal = "1,10,100,1000,10000,100000,1000000,100000000000000"; 
	return verify_case(RetVal, IncreasingLists().makeIncreasingList(mask)); }

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