Overview
| SHA1 Hash: | 445abb9772f82060a9f28e3a96fbf0846d525282 |
|---|---|
| Date: | 2015-05-31 10:39:28 |
| User: | kinaba |
| Comment: | 659 |
| 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/659-U/1A.cpp version [6cad379ca924cee7]
> 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 ApplesAndOrangesEasy { public: > 23 int maximumApples(int N, int K, vector <int> info) > 24 { > 25 vector<bool> ate_apple(N, false); > 26 for(auto i: info) > 27 ate_apple[i-1] = true; > 28 for(int i=0; i<N; ++i) > 29 if(!ate_apple[i]) { > 30 ate_apple[i] = true; > 31 if(!ok(N,K,ate_apple)) > 32 ate_apple[i] = false; > 33 } > 34 return count(ate_apple.begin(), ate_apple.end(), true); > 35 } > 36 > 37 bool ok(int N, int K, const vector<bool>& A) > 38 { > 39 int cnt = 0; > 40 for(int i=0; i<N; ++i) { > 41 if(A[i]) cnt++; > 42 if(i-K>=0 && A[i-K]) cnt--; > 43 if(cnt>K/2) > 44 return false; > 45 } > 46 return true; > 47 } > 48 }; > 49 > 50 // BEGIN CUT HERE > 51 #include <ctime> > 52 double start_time; string timer() > 53 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 54 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 55 { os << "{ "; > 56 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 57 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 58 void verify_case(const int& Expected, const int& Received) { > 59 bool ok = (Expected == Received); > 60 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 61 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 62 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 63 #define END verify_case(_, ApplesAndOrangesEasy().maximumApples(N, K, info) > 64 int main(){ > 65 > 66 CASE(0) > 67 int N = 3; > 68 int K = 2; > 69 vector <int> info; > 70 int _ = 2; > 71 END > 72 CASE(1) > 73 int N = 10; > 74 int K = 3; > 75 int info_[] = {3, 8}; > 76 vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_)); > 77 int _ = 2; > 78 END > 79 CASE(2) > 80 int N = 9; > 81 int K = 4; > 82 int info_[] = {1, 4}; > 83 vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_)); > 84 int _ = 5; > 85 END > 86 CASE(3) > 87 int N = 9; > 88 int K = 4; > 89 int info_[] = {2, 4}; > 90 vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_)); > 91 int _ = 4; > 92 END > 93 CASE(4) > 94 int N = 23; > 95 int K = 7; > 96 int info_[] = {3, 2, 9, 1, 15, 23, 20, 19}; > 97 vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_)); > 98 int _ = 10; > 99 END > 100 /* > 101 CASE(5) > 102 int N = ; > 103 int K = ; > 104 int info_[] = ; > 105 vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_)); > 106 int _ = ; > 107 END > 108 CASE(6) > 109 int N = ; > 110 int K = ; > 111 int info_[] = ; > 112 vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_)); > 113 int _ = ; > 114 END > 115 */ > 116 } > 117 // END CUT HERE
Added SRM/659-U/1B.cpp version [31849cb71c63089e]
> 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 static const unsigned MODVAL = 1000000007; > 23 struct mint > 24 { > 25 unsigned val; > 26 mint():val(0){} > 27 mint(int x):val(x%MODVAL) {} > 28 mint(unsigned x):val(x%MODVAL) {} > 29 mint(LL x):val(x%MODVAL) {} > 30 }; > 31 mint& operator+=(mint& x, mint y) { return x = x.val+y.val; } > 32 mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; } > 33 mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; } > 34 mint operator+(mint x, mint y) { return x+=y; } > 35 mint operator-(mint x, mint y) { return x-=y; } > 36 mint operator*(mint x, mint y) { return x*=y; } > 37 > 38 class CampLunch { public: > 39 int count(int N, int M, vector <string> a) > 40 { > 41 memo.assign(N<<M, -1); > 42 memo2.assign(N*M<<M, -1); > 43 return rec(N, M, a, 0, 0); > 44 } > 45 > 46 vector<int> memo; > 47 int rec(int N, int M, const vector<string>& A, int d, int yesterday_free > 48 if(d == N) > 49 return 1; > 50 > 51 const int key = (d<<M) | yesterday_free; > 52 if(memo[key] >= 0) > 53 return memo[key]; > 54 > 55 return memo[key] = rec2(N, M, A, d, 0, yesterday_free, 0); > 56 } > 57 > 58 vector<int> memo2; > 59 int rec2(int N, int M, const vector<string>& A, > 60 int d, int i, int yesterday_free, int today_free) { > 61 if(i == M) > 62 return rec(N,M,A,d+1,today_free); > 63 > 64 const int key = ((d*M+i)<<M) | yesterday_free | today_free; > 65 if(memo2[key] >= 0) > 66 return memo2[key]; > 67 > 68 mint total = 0; > 69 > 70 // Plan 2. > 71 int p = A[d][i] - 'A'; > 72 if(yesterday_free & (1<<p)) > 73 total += rec2(N,M,A,d,i+1,yesterday_free&~(1<<p),today_f > 74 // Plan 1. > 75 if(i+1<M) { > 76 int p2 = A[d][i+1]-'A'; > 77 total += rec2(N,M,A,d,i+2,yesterday_free&~(1<<p)&~(1<<p2 > 78 } > 79 // No Plan. > 80 total += rec2(N,M,A,d,i+1,yesterday_free&~(1<<p),today_free|(1<< > 81 return memo2[key] = total.val; > 82 } > 83 }; > 84 > 85 // BEGIN CUT HERE > 86 #include <ctime> > 87 double start_time; string timer() > 88 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 89 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 90 { os << "{ "; > 91 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 92 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 93 void verify_case(const int& Expected, const int& Received) { > 94 bool ok = (Expected == Received); > 95 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 96 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 97 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 98 #define END verify_case(_, CampLunch().count(N, M, a));} > 99 int main(){ > 100 > 101 CASE(0) > 102 int N = 2; > 103 int M = 2; > 104 string a_[] = {"AB","AB"}; > 105 vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 106 int _ = 7; > 107 END > 108 CASE(1) > 109 int N = 2; > 110 int M = 3; > 111 string a_[] = {"ABC","ABC"}; > 112 vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 113 int _ = 22; > 114 END > 115 CASE(2) > 116 int N = 2; > 117 int M = 3; > 118 string a_[] = {"ABC","BAC"}; > 119 vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 120 int _ = 21; > 121 END > 122 CASE(3) > 123 int N = 1; > 124 int M = 1; > 125 string a_[] = {"A"}; > 126 vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 127 int _ = 1; > 128 END > 129 CASE(4) > 130 int N = 1; > 131 int M = 10; > 132 string a_[] = {"ABDEFHIGJC"}; > 133 vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 134 int _ = 89; > 135 END > 136 CASE(5) > 137 int N = 16; > 138 int M = 16; > 139 string a_[] = {"ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP", > 140 vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 141 int _ = 950052677; > 142 END > 143 /* > 144 CASE(6) > 145 int N = ; > 146 int M = ; > 147 string a_[] = ; > 148 vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 149 int _ = ; > 150 END > 151 CASE(7) > 152 int N = ; > 153 int M = ; > 154 string a_[] = ; > 155 vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_)); > 156 int _ = ; > 157 END > 158 */ > 159 } > 160 // END CUT HERE