Overview
| SHA1 Hash: | bdc8bb3e190e8cb3ac70be38eeaf1a41d7905e01 |
|---|---|
| Date: | 2015-05-13 00:53:07 |
| User: | kinaba |
| Comment: | 657 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/657-U/1A.cpp version [cbc7da6c8638afb4]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class ProblemSets { public: > 23 long long maxSets(long long E, long long EM, long long M, long long MH, > 24 { > 25 LL L=0, R=0x7fffffffffffffffLL; // can make [L,R) > 26 while(R-L>1) { > 27 LL C = L+(R-L)/2; > 28 (can(E,EM,M,MH,H,C) ? L : R) = C; > 29 } > 30 return L; > 31 } > 32 > 33 bool can(long long E, long long EM, long long M, long long MH, long long > 34 LL eNeed = max(0LL, nProbs-E); > 35 LL mNeed = max(0LL, nProbs-M); > 36 LL hNeed = max(0LL, nProbs-H); > 37 if(EM < eNeed) return false; > 38 EM -= eNeed; > 39 if(MH < hNeed) return false; > 40 MH -= hNeed; > 41 return mNeed <= EM+MH; > 42 } > 43 }; > 44 > 45 // BEGIN CUT HERE > 46 #include <ctime> > 47 double start_time; string timer() > 48 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 49 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 50 { os << "{ "; > 51 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 52 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 53 void verify_case(const long long& Expected, const long long& Received) { > 54 bool ok = (Expected == Received); > 55 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 56 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 57 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 58 #define END verify_case(_, ProblemSets().maxSets(E, EM, M, MH, H));} > 59 int main(){ > 60 > 61 CASE(0) > 62 long long E = 2LL; > 63 long long EM = 2LL; > 64 long long M = 1LL; > 65 long long MH = 2LL; > 66 long long H = 2LL; > 67 long long _ = 3LL; > 68 END > 69 CASE(1) > 70 long long E = 100LL; > 71 long long EM = 100LL; > 72 long long M = 100LL; > 73 long long MH = 0LL; > 74 long long H = 0LL; > 75 long long _ = 0LL; > 76 END > 77 CASE(2) > 78 long long E = 657LL; > 79 long long EM = 657LL; > 80 long long M = 657LL; > 81 long long MH = 657LL; > 82 long long H = 657LL; > 83 long long _ = 1095LL; > 84 END > 85 CASE(3) > 86 long long E = 1LL; > 87 long long EM = 2LL; > 88 long long M = 3LL; > 89 long long MH = 4LL; > 90 long long H = 5LL; > 91 long long _ = 3LL; > 92 END > 93 CASE(4) > 94 long long E = 1000000000000000000LL; > 95 long long EM = 1000000000000000000LL; > 96 long long M = 1000000000000000000LL; > 97 long long MH = 1000000000000000000LL; > 98 long long H = 1000000000000000000LL; > 99 long long _ = 1666666666666666666LL; > 100 END > 101 /* > 102 CASE(5) > 103 long long E = LL; > 104 long long EM = LL; > 105 long long M = LL; > 106 long long MH = LL; > 107 long long H = LL; > 108 long long _ = LL; > 109 END > 110 CASE(6) > 111 long long E = LL; > 112 long long EM = LL; > 113 long long M = LL; > 114 long long MH = LL; > 115 long long H = LL; > 116 long long _ = LL; > 117 END > 118 */ > 119 } > 120 // END CUT HERE
Added SRM/657-U/1B-U.cpp version [bdee7ea796a0a8ca]
> 1 #include <iostream> > 2 #include <sstream> > 3 #include <iomanip> > 4 #include <vector> > 5 #include <string> > 6 #include <map> > 7 #include <set> > 8 #include <algorithm> > 9 #include <numeric> > 10 #include <iterator> > 11 #include <functional> > 12 #include <complex> > 13 #include <queue> > 14 #include <stack> > 15 #include <cmath> > 16 #include <cassert> > 17 #include <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 bool is_prime(int p) > 23 { > 24 for(int q=2; q*q<=p; ++q) > 25 if(p%q==0) > 26 return false; > 27 return true; > 28 } > 29 > 30 static const unsigned MODVAL = 1000000007; > 31 struct mint > 32 { > 33 unsigned val; > 34 mint():val(0){} > 35 mint(int x):val(x%MODVAL) {} > 36 mint(unsigned x):val(x%MODVAL) {} > 37 mint(LL x):val(x%MODVAL) {} > 38 }; > 39 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 40 mint operator*(mint x, mint y) { return x*=y; } > 41 mint POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; } > 42 > 43 class PolynomialGCD { public: > 44 int gcd(string s) > 45 { > 46 mint ans = 1; > 47 for(int p=2; p<=s.size()+1; ++p) > 48 if(is_prime(p)) > 49 ans *= POW(p, howManyTimesAlwaysDivisibleByP(s, > 50 return ans.val; > 51 } > 52 > 53 int howManyTimesAlwaysDivisibleByP(const string& s, int p) > 54 { > 55 static const int INF = 0x7fffffff; > 56 int at_least = INF; > 57 for(int k=-p; k<=+p; ++k) { > 58 int cur = 0; > 59 for(int b=((k+p+p-1)/p-1)*p,i=s.size()-1-(b-k); i>=0; b+ > 60 int e = s[i]-'0'; > 61 if(b==0 && e) > 62 goto next; > 63 if(e) > 64 for(int bb=b; bb%p==0; bb/=p) > 65 cur+=e; > 66 } > 67 at_least = min(at_least, cur); > 68 next:; > 69 } > 70 return at_least; > 71 } > 72 }; > 73 > 74 // BEGIN CUT HERE > 75 #include <ctime> > 76 double start_time; string timer() > 77 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 78 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 79 { os << "{ "; > 80 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 81 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 82 void verify_case(const int& Expected, const int& Received) { > 83 bool ok = (Expected == Received); > 84 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 85 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 86 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 87 #define END verify_case(_, PolynomialGCD().gcd(s));} > 88 int main(){ > 89 > 90 CASE(0) > 91 string s = "111"; > 92 int _ = 6; > 93 END > 94 CASE(1) > 95 string s = "00000"; > 96 int _ = 1; > 97 END > 98 CASE(2) > 99 string s = "2014"; > 100 int _ = 16; > 101 END > 102 CASE(3) > 103 string s = "31415926535"; > 104 int _ = 659897170; > 105 END > 106 /* > 107 CASE(4) > 108 string s = ; > 109 int _ = ; > 110 END > 111 CASE(5) > 112 string s = ; > 113 int _ = ; > 114 END > 115 */ > 116 } > 117 // END CUT HERE