af429d4fc8 2012-06-23 kinaba: #include <iostream> af429d4fc8 2012-06-23 kinaba: #include <sstream> af429d4fc8 2012-06-23 kinaba: #include <iomanip> af429d4fc8 2012-06-23 kinaba: #include <vector> af429d4fc8 2012-06-23 kinaba: #include <string> af429d4fc8 2012-06-23 kinaba: #include <map> af429d4fc8 2012-06-23 kinaba: #include <set> af429d4fc8 2012-06-23 kinaba: #include <algorithm> af429d4fc8 2012-06-23 kinaba: #include <numeric> af429d4fc8 2012-06-23 kinaba: #include <iterator> af429d4fc8 2012-06-23 kinaba: #include <functional> af429d4fc8 2012-06-23 kinaba: #include <complex> af429d4fc8 2012-06-23 kinaba: #include <queue> af429d4fc8 2012-06-23 kinaba: #include <stack> af429d4fc8 2012-06-23 kinaba: #include <cmath> af429d4fc8 2012-06-23 kinaba: #include <cassert> af429d4fc8 2012-06-23 kinaba: using namespace std; af429d4fc8 2012-06-23 kinaba: typedef long long LL; af429d4fc8 2012-06-23 kinaba: typedef long double LD; af429d4fc8 2012-06-23 kinaba: typedef complex<LD> CMP; af429d4fc8 2012-06-23 kinaba: af429d4fc8 2012-06-23 kinaba: class FavouriteDigits { public: af429d4fc8 2012-06-23 kinaba: long long findNext(long long N, int digit1, int count1, int digit2, int count2) af429d4fc8 2012-06-23 kinaba: { af429d4fc8 2012-06-23 kinaba: LL d = 1; af429d4fc8 2012-06-23 kinaba: for(int _=0; _<15; ++_) d *= 10; af429d4fc8 2012-06-23 kinaba: af429d4fc8 2012-06-23 kinaba: LL answer = 0; af429d4fc8 2012-06-23 kinaba: af429d4fc8 2012-06-23 kinaba: bool zeros = true; af429d4fc8 2012-06-23 kinaba: for(int rest=15; d>=1; d/=10, --rest) { af429d4fc8 2012-06-23 kinaba: for(int v=0; v<=9; ++v) { af429d4fc8 2012-06-23 kinaba: int c1 = max(0, count1 - (v==digit1 && (v!=0 || !zeros) ? 1 : 0)); af429d4fc8 2012-06-23 kinaba: int c2 = max(0, count2 - (v==digit2 && (v!=0 || !zeros) ? 1 : 0)); af429d4fc8 2012-06-23 kinaba: bool zz = zeros && (v==0); af429d4fc8 2012-06-23 kinaba: if( rest >= c1 + c2 ) { af429d4fc8 2012-06-23 kinaba: LL cur = answer + v*d + largest(rest, digit1, c1, digit2, c2); af429d4fc8 2012-06-23 kinaba: if( cur >= N ) { af429d4fc8 2012-06-23 kinaba: answer += v*d; af429d4fc8 2012-06-23 kinaba: count1 = c1; af429d4fc8 2012-06-23 kinaba: count2 = c2; af429d4fc8 2012-06-23 kinaba: zeros = zz; af429d4fc8 2012-06-23 kinaba: break; af429d4fc8 2012-06-23 kinaba: } af429d4fc8 2012-06-23 kinaba: } af429d4fc8 2012-06-23 kinaba: } af429d4fc8 2012-06-23 kinaba: } af429d4fc8 2012-06-23 kinaba: af429d4fc8 2012-06-23 kinaba: return answer; af429d4fc8 2012-06-23 kinaba: } af429d4fc8 2012-06-23 kinaba: af429d4fc8 2012-06-23 kinaba: LL largest(int rest, int d1, int c1, int d2, int c2) af429d4fc8 2012-06-23 kinaba: { af429d4fc8 2012-06-23 kinaba: if(rest==0) af429d4fc8 2012-06-23 kinaba: return 0; af429d4fc8 2012-06-23 kinaba: if(d1>d2) swap(d1,d2), swap(c1,c2); af429d4fc8 2012-06-23 kinaba: string s; af429d4fc8 2012-06-23 kinaba: for(int i=0; i<rest-c1-c2; ++i) af429d4fc8 2012-06-23 kinaba: s += '9'; af429d4fc8 2012-06-23 kinaba: for(int i=0; i<c2; ++i) af429d4fc8 2012-06-23 kinaba: s += char('0'+d2); af429d4fc8 2012-06-23 kinaba: for(int i=0; i<c1; ++i) af429d4fc8 2012-06-23 kinaba: s += char('0'+d1); af429d4fc8 2012-06-23 kinaba: stringstream sin(s); af429d4fc8 2012-06-23 kinaba: LL n; af429d4fc8 2012-06-23 kinaba: sin >> n; af429d4fc8 2012-06-23 kinaba: return n; af429d4fc8 2012-06-23 kinaba: } af429d4fc8 2012-06-23 kinaba: }; af429d4fc8 2012-06-23 kinaba: af429d4fc8 2012-06-23 kinaba: // BEGIN CUT HERE af429d4fc8 2012-06-23 kinaba: #include <ctime> af429d4fc8 2012-06-23 kinaba: double start_time; string timer() af429d4fc8 2012-06-23 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } af429d4fc8 2012-06-23 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) af429d4fc8 2012-06-23 kinaba: { os << "{ "; af429d4fc8 2012-06-23 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) af429d4fc8 2012-06-23 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } af429d4fc8 2012-06-23 kinaba: void verify_case(const long long& Expected, const long long& Received) { af429d4fc8 2012-06-23 kinaba: bool ok = (Expected == Received); af429d4fc8 2012-06-23 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; af429d4fc8 2012-06-23 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } af429d4fc8 2012-06-23 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); af429d4fc8 2012-06-23 kinaba: #define END verify_case(_, FavouriteDigits().findNext(N, digit1, count1, digit2, count2));} af429d4fc8 2012-06-23 kinaba: int main(){ af429d4fc8 2012-06-23 kinaba: af429d4fc8 2012-06-23 kinaba: CASE(0) af429d4fc8 2012-06-23 kinaba: long long N = 47LL; af429d4fc8 2012-06-23 kinaba: int digit1 = 1; af429d4fc8 2012-06-23 kinaba: int count1 = 0; af429d4fc8 2012-06-23 kinaba: int digit2 = 2; af429d4fc8 2012-06-23 kinaba: int count2 = 0; af429d4fc8 2012-06-23 kinaba: long long _ = 47LL; af429d4fc8 2012-06-23 kinaba: END af429d4fc8 2012-06-23 kinaba: CASE(1) af429d4fc8 2012-06-23 kinaba: long long N = 47LL; af429d4fc8 2012-06-23 kinaba: int digit1 = 5; af429d4fc8 2012-06-23 kinaba: int count1 = 0; af429d4fc8 2012-06-23 kinaba: int digit2 = 9; af429d4fc8 2012-06-23 kinaba: int count2 = 1; af429d4fc8 2012-06-23 kinaba: long long _ = 49LL; af429d4fc8 2012-06-23 kinaba: END af429d4fc8 2012-06-23 kinaba: CASE(2) af429d4fc8 2012-06-23 kinaba: long long N = 47LL; af429d4fc8 2012-06-23 kinaba: int digit1 = 5; af429d4fc8 2012-06-23 kinaba: int count1 = 0; af429d4fc8 2012-06-23 kinaba: int digit2 = 3; af429d4fc8 2012-06-23 kinaba: int count2 = 1; af429d4fc8 2012-06-23 kinaba: long long _ = 53LL; af429d4fc8 2012-06-23 kinaba: END af429d4fc8 2012-06-23 kinaba: CASE(3) af429d4fc8 2012-06-23 kinaba: long long N = 47LL; af429d4fc8 2012-06-23 kinaba: int digit1 = 2; af429d4fc8 2012-06-23 kinaba: int count1 = 1; af429d4fc8 2012-06-23 kinaba: int digit2 = 0; af429d4fc8 2012-06-23 kinaba: int count2 = 2; af429d4fc8 2012-06-23 kinaba: long long _ = 200LL; af429d4fc8 2012-06-23 kinaba: END af429d4fc8 2012-06-23 kinaba: CASE(4) af429d4fc8 2012-06-23 kinaba: long long N = 123456789012345LL; af429d4fc8 2012-06-23 kinaba: int digit1 = 1; af429d4fc8 2012-06-23 kinaba: int count1 = 2; af429d4fc8 2012-06-23 kinaba: int digit2 = 2; af429d4fc8 2012-06-23 kinaba: int count2 = 4; af429d4fc8 2012-06-23 kinaba: long long _ = 123456789012422LL; af429d4fc8 2012-06-23 kinaba: END af429d4fc8 2012-06-23 kinaba: CASE(5) af429d4fc8 2012-06-23 kinaba: long long N = 92LL; af429d4fc8 2012-06-23 kinaba: int digit1 = 1; af429d4fc8 2012-06-23 kinaba: int count1 = 1; af429d4fc8 2012-06-23 kinaba: int digit2 = 0; af429d4fc8 2012-06-23 kinaba: int count2 = 0; af429d4fc8 2012-06-23 kinaba: long long _ = 100LL; af429d4fc8 2012-06-23 kinaba: END af429d4fc8 2012-06-23 kinaba: /* af429d4fc8 2012-06-23 kinaba: CASE(6) af429d4fc8 2012-06-23 kinaba: long long N = LL; af429d4fc8 2012-06-23 kinaba: int digit1 = ; af429d4fc8 2012-06-23 kinaba: int count1 = ; af429d4fc8 2012-06-23 kinaba: int digit2 = ; af429d4fc8 2012-06-23 kinaba: int count2 = ; af429d4fc8 2012-06-23 kinaba: long long _ = LL; af429d4fc8 2012-06-23 kinaba: END af429d4fc8 2012-06-23 kinaba: */ af429d4fc8 2012-06-23 kinaba: CASE(7) af429d4fc8 2012-06-23 kinaba: long long N = 1000000000000000LL - 1; af429d4fc8 2012-06-23 kinaba: int digit1 = 5; af429d4fc8 2012-06-23 kinaba: int count1 = 5; af429d4fc8 2012-06-23 kinaba: int digit2 = 5; af429d4fc8 2012-06-23 kinaba: int count2 = 5; af429d4fc8 2012-06-23 kinaba: long long _ = -1LL; af429d4fc8 2012-06-23 kinaba: END af429d4fc8 2012-06-23 kinaba: af429d4fc8 2012-06-23 kinaba: } af429d4fc8 2012-06-23 kinaba: // END CUT HERE