109f2a9050 2012-09-08 kinaba: #include <iostream> 109f2a9050 2012-09-08 kinaba: #include <sstream> 109f2a9050 2012-09-08 kinaba: #include <iomanip> 109f2a9050 2012-09-08 kinaba: #include <vector> 109f2a9050 2012-09-08 kinaba: #include <string> 109f2a9050 2012-09-08 kinaba: #include <map> 109f2a9050 2012-09-08 kinaba: #include <set> 109f2a9050 2012-09-08 kinaba: #include <algorithm> 109f2a9050 2012-09-08 kinaba: #include <numeric> 109f2a9050 2012-09-08 kinaba: #include <iterator> 109f2a9050 2012-09-08 kinaba: #include <functional> 109f2a9050 2012-09-08 kinaba: #include <complex> 109f2a9050 2012-09-08 kinaba: #include <queue> 109f2a9050 2012-09-08 kinaba: #include <stack> 109f2a9050 2012-09-08 kinaba: #include <cmath> 109f2a9050 2012-09-08 kinaba: #include <cassert> 109f2a9050 2012-09-08 kinaba: using namespace std; 109f2a9050 2012-09-08 kinaba: typedef long long LL; 109f2a9050 2012-09-08 kinaba: typedef long double LD; 109f2a9050 2012-09-08 kinaba: typedef complex<LD> CMP; 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: class CuttingBitString { public: 109f2a9050 2012-09-08 kinaba: static const int INF = 999; 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: int getmin(string S) 109f2a9050 2012-09-08 kinaba: { 109f2a9050 2012-09-08 kinaba: LL v = 1; 109f2a9050 2012-09-08 kinaba: set<string> good; 109f2a9050 2012-09-08 kinaba: for(LL v=1; v<(1LL<<60); v*=5) { 109f2a9050 2012-09-08 kinaba: cerr << bin(v) << endl; 109f2a9050 2012-09-08 kinaba: good.insert(bin(v)); 109f2a9050 2012-09-08 kinaba: } 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: int s = best(S, good, 0, S.size()); 109f2a9050 2012-09-08 kinaba: return s>=INF ? -1 : s; 109f2a9050 2012-09-08 kinaba: } 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: map<pair<int,int>, int> memo; 109f2a9050 2012-09-08 kinaba: int best(const string& S, const set<string>& good, int s, int e) 109f2a9050 2012-09-08 kinaba: { 109f2a9050 2012-09-08 kinaba: pair<int,int> key(s,e); 109f2a9050 2012-09-08 kinaba: if(memo.count(key)) 109f2a9050 2012-09-08 kinaba: return memo[key]; 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: if( good.count(S.substr(s, e-s)) ) 109f2a9050 2012-09-08 kinaba: return memo[key] = 1; 109f2a9050 2012-09-08 kinaba: int score = INF; 109f2a9050 2012-09-08 kinaba: for(int m=s+1; m+1<=e; ++m) 109f2a9050 2012-09-08 kinaba: { 109f2a9050 2012-09-08 kinaba: int x = best(S, good, s, m); 109f2a9050 2012-09-08 kinaba: int y = best(S, good, m, e); 109f2a9050 2012-09-08 kinaba: score = min(score, x+y); 109f2a9050 2012-09-08 kinaba: } 109f2a9050 2012-09-08 kinaba: return memo[key] = score; 109f2a9050 2012-09-08 kinaba: } 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: string bin(LL v) 109f2a9050 2012-09-08 kinaba: { 109f2a9050 2012-09-08 kinaba: string s; 109f2a9050 2012-09-08 kinaba: for(; v; v>>=1) 109f2a9050 2012-09-08 kinaba: s += (v&1 ? '1' : '0'); 109f2a9050 2012-09-08 kinaba: reverse(s.begin(), s.end()); 109f2a9050 2012-09-08 kinaba: return s; 109f2a9050 2012-09-08 kinaba: } 109f2a9050 2012-09-08 kinaba: }; 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: // BEGIN CUT HERE 109f2a9050 2012-09-08 kinaba: #include <ctime> 109f2a9050 2012-09-08 kinaba: double start_time; string timer() 109f2a9050 2012-09-08 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 109f2a9050 2012-09-08 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 109f2a9050 2012-09-08 kinaba: { os << "{ "; 109f2a9050 2012-09-08 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 109f2a9050 2012-09-08 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 109f2a9050 2012-09-08 kinaba: void verify_case(const int& Expected, const int& Received) { 109f2a9050 2012-09-08 kinaba: bool ok = (Expected == Received); 109f2a9050 2012-09-08 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 109f2a9050 2012-09-08 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 109f2a9050 2012-09-08 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 109f2a9050 2012-09-08 kinaba: #define END verify_case(_, CuttingBitString().getmin(S));} 109f2a9050 2012-09-08 kinaba: int main(){ 109f2a9050 2012-09-08 kinaba: 109f2a9050 2012-09-08 kinaba: CASE(3) 109f2a9050 2012-09-08 kinaba: string S = "110011011"; 109f2a9050 2012-09-08 kinaba: int _ = 3; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: CASE(0) 109f2a9050 2012-09-08 kinaba: string S = "101101101"; 109f2a9050 2012-09-08 kinaba: int _ = 3; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: CASE(1) 109f2a9050 2012-09-08 kinaba: string S = "1111101"; 109f2a9050 2012-09-08 kinaba: int _ = 1; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: CASE(2) 109f2a9050 2012-09-08 kinaba: string S = "00000"; 109f2a9050 2012-09-08 kinaba: int _ = -1; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: CASE(4) 109f2a9050 2012-09-08 kinaba: string S = "1000101011"; 109f2a9050 2012-09-08 kinaba: int _ = -1; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: CASE(5) 109f2a9050 2012-09-08 kinaba: string S = "111011100110101100101110111"; 109f2a9050 2012-09-08 kinaba: int _ = 5; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: CASE(6) 109f2a9050 2012-09-08 kinaba: string S = "11111111111111111111111111111111111111111111111111"; 109f2a9050 2012-09-08 kinaba: int _ = -999; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: CASE(7) 109f2a9050 2012-09-08 kinaba: string S = "1101100011010111001001101011011100010111011110101"; 109f2a9050 2012-09-08 kinaba: int _ = 1; 109f2a9050 2012-09-08 kinaba: END 109f2a9050 2012-09-08 kinaba: } 109f2a9050 2012-09-08 kinaba: // END CUT HERE