ADDED SRM/529-U/1A.cpp Index: SRM/529-U/1A.cpp ================================================================== --- SRM/529-U/1A.cpp +++ SRM/529-U/1A.cpp @@ -0,0 +1,139 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#ifdef __GNUC__ +#include +#define unordered_map __gnu_cxx::hash_map +#else +#include +#endif +using namespace std; +typedef long long LL; +typedef complex CMP; + +static string ones[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}; +static string tens[] = {"", "X", "XX", "XXX", "XL", "L"}; + +class KingSort { public: + vector getSortedList(vector kings) + { + vector< pair > kk; + for(int i=0; i parse(const string& s) + { + stringstream ss(s); + string name, ord; + ss >> name >> ord; + return make_pair(name, roman(ord)); + } + + int roman(const string& s) + { + for(int i=0; i<=s.size(); ++i) + { + int ti = find(&tens[0], &tens[6], s.substr(0, i)) - &tens[0]; + int oi = find(&ones[0], &ones[10], s.substr(i)) - &ones[0]; + if( oi == 10 || ti == 6 ) + continue; + return oi + ti*10; + } + return -99999; + } + + string encode(const pair& p) + { + stringstream ss; + ss << p.first << " " << tens[p.second/10] << ones[p.second%10]; + return ss.str(); + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const vector & Expected, const vector & Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, KingSort().getSortedList(kings));} +int main(){ + +CASE(0) + string kings_[] = {"Louis IX", "Louis VIII"}; + vector kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); + string __[] = {"Louis VIII", "Louis IX" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(1) + string kings_[] = {"Louis IX", "Philippe II"}; + vector kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); + string __[] = {"Louis IX", "Philippe II" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(2) + string kings_[] = {"Richard III", "Richard I", "Richard II"}; + vector kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); + string __[] = {"Richard I", "Richard II", "Richard III" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(3) + string kings_[] = {"John X", "John I", "John L", "John V"}; + vector kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); + string __[] = {"John I", "John V", "John X", "John L" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(4) + string kings_[] = {"Philippe VI", "Jean II", "Charles V", "Charles VI", "Charles VII", "Louis XI"}; + vector kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); + string __[] = {"Charles V", "Charles VI", "Charles VII", "Jean II", "Louis XI", "Philippe VI" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(5) + string kings_[] = {"Philippe II", "Philip II"}; + vector kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); + string __[] = {"Philip II", "Philippe II" }; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +/* +CASE(6) + string kings_[] = ; + vector kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); + string __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +CASE(7) + string kings_[] = ; + vector kings(kings_, kings_+sizeof(kings_)/sizeof(*kings_)); + string __[] = ; + vector _(__, __+sizeof(__)/sizeof(*__)); +END +*/ +} +// END CUT HERE ADDED SRM/529-U/1B-U.cpp Index: SRM/529-U/1B-U.cpp ================================================================== --- SRM/529-U/1B-U.cpp +++ SRM/529-U/1B-U.cpp @@ -0,0 +1,89 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#ifdef __GNUC__ +#include +#define unordered_map __gnu_cxx::hash_map +#else +#include +#endif +using namespace std; +typedef long long LL; +typedef complex CMP; + +static const int MODVAL = 1000000009; + +class MinskyMystery { public: + int computeAnswer(long long N) + { + return N<2 ? -1 : theCode(N); + } + + LL theCode(LL N) + { + LL counter = 1; + for(LL a=2 ;; ++a) { + {counter += N*4 + (N+a-1)/a + 1;} + if( N%a == 0 ) + return counter - N; + } + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const int& Expected, const int& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, MinskyMystery().computeAnswer(N));} +int main(){ + +CASE(0) + long long N = 2LL; + int _ = 9; +END +CASE(1) + long long N = 3LL; + int _ = 27; +END +CASE(2) + long long N = 4LL; + int _ = 16; +END +CASE(3) + long long N = 2401LL; + int _ = 59058; +END +CASE(4) + long long N = 24LL; + int _ = 86; +END +CASE(5) + long long N = 1; + int _ = -1; +END + +} +// END CUT HERE ADDED SRM/529-U/1C-U.cpp Index: SRM/529-U/1C-U.cpp ================================================================== --- SRM/529-U/1C-U.cpp +++ SRM/529-U/1C-U.cpp @@ -0,0 +1,138 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#ifdef __GNUC__ +#include +#define unordered_map __gnu_cxx::hash_map +#else +#include +#endif +using namespace std; +typedef long long LL; +typedef complex CMP; + +class BigAndSmallAirports { public: + long long solve(int Nlo, int Nhi, int Blo, int Bhi, int Slo, int Shi) + { + LL cnt = 0; + for(int B=Blo; B<=Bhi; ++B) + for(int S=Slo; S<=Shi; ++S) + if( S < B ) + cnt += fast(Nhi, B, S) - fast(Nlo-1, B, S); + return cnt; + } + + LL fast(LL N, LL B, LL S) + { + LL cnt = 0; + for(LL k=0; k<=N; ++k) { + LL Nmin = ((1+B+S)*k - k*k + S-1) / S; + if( Nmin < 0 ) { + cnt += (N-k+1)*(N-k+2)/2; + break; + } + Nmin = max(Nmin, k); + if( N >= Nmin ) + cnt += (N-Nmin+1); + } + return cnt; + } +}; + +// BEGIN CUT HERE +#include +double start_time; string timer() + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } +template ostream& operator<<(ostream& os, const vector& v) + { os << "{ "; + for(typename vector::const_iterator it=v.begin(); it!=v.end(); ++it) + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } +void verify_case(const long long& Expected, const long long& Received) { + bool ok = (Expected == Received); + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); +#define END verify_case(_, BigAndSmallAirports().solve(Nlo, Nhi, Blo, Bhi, Slo, Shi));} +int main(){ + +CASE(0) + int Nlo = 20; + int Nhi = 20; + int Blo = 3; + int Bhi = 3; + int Slo = 2; + int Shi = 2; + long long _ = 21LL; +END +CASE(1) + int Nlo = 1; + int Nhi = 1; + int Blo = 10; + int Bhi = 10; + int Slo = 2; + int Shi = 2; + long long _ = 1LL; +END +CASE(2) + int Nlo = 10; + int Nhi = 10; + int Blo = 8; + int Bhi = 8; + int Slo = 3; + int Shi = 3; + long long _ = 6LL; +END +CASE(3) + int Nlo = 10; + int Nhi = 100; + int Blo = 13; + int Bhi = 15; + int Slo = 18; + int Shi = 22; + long long _ = 0LL; +END +CASE(4) + int Nlo = 30; + int Nhi = 32; + int Blo = 8; + int Bhi = 10; + int Slo = 6; + int Shi = 8; + long long _ = 768LL; +END +CASE(5) + int Nlo = 1; + int Nhi = 10000000; + int Blo = 1; + int Bhi = 200; + int Slo = 1; + int Shi = 200; + long long _ = -1LL; +END +/* +CASE(6) + int Nlo = ; + int Nhi = ; + int Blo = ; + int Bhi = ; + int Slo = ; + int Shi = ; + long long _ = LL; +END +*/ +} +// END CUT HERE