Overview
| SHA1 Hash: | b4af6486f6096924dc5a62dc5df77f856359f1cb |
|---|---|
| Date: | 2011-05-19 07:42:09 |
| User: | kinaba |
| Comment: | rename 505-u |
| 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
Name change from from SRM/505-u/1Au.cpp to SRM/505-U/1Au.cpp.
Name change from from SRM/505-u/1B.cpp to SRM/505-U/1B.cpp.
Deleted SRM/505-u/1Au.cpp version [9979db28a5ab5334]
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 <cstring> < 18 using namespace std; < 19 typedef long long LL; < 20 typedef complex<double> CMP; < 21 < 22 class RectangleArea { public: < 23 int minimumQueries(vector <string> known) < 24 { < 25 const int H = known.size(); < 26 const int W = known[0].size(); < 27 for(int y=0; y<H; ++y) < 28 for(int x=0; x<W; ++x) < 29 for(int Y=0; Y<H; ++Y) < 30 for(int X=0; X<W; ++X) < 31 if( make_pair(y,x) < make_pair(Y,X) && y!=Y && x!=X ) < 32 if( known[y][x]=='Y' && known[Y][X]=='Y' ) < 33 { < 34 if( known[y][X]=='Y' ) < 35 known[Y][x] = 'Y'; < 36 if( known[Y][x]=='Y' ) < 37 known[y][X] = 'Y'; < 38 } < 39 < 40 int tt = 0; < 41 for(int i=0; i<W; ++i) < 42 if( known[0][i]=='N' ) < 43 ++tt; < 44 int yy = 0; < 45 for(int i=0; i<H; ++i) < 46 if( known[i][0]=='N' ) < 47 ++yy; < 48 if( tt == 0 ) < 49 return yy; < 50 if( yy == 0 ) < 51 return tt; < 52 return -1; < 53 } < 54 }; < 55 < 56 // BEGIN CUT HERE < 57 #include <ctime> < 58 double start_time; string timer() < 59 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 60 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 61 { os << "{ "; < 62 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 63 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 64 void verify_case(const int& Expected, const int& Received) { < 65 bool ok = (Expected == Received); < 66 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 67 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 68 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 69 #define END verify_case(_, RectangleArea().minimumQueries(known));} < 70 int main(){ < 71 < 72 CASE(0) < 73 string known_[] = {"NN", < 74 "NN"}; < 75 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); < 76 int _ = 3; < 77 END < 78 CASE(1) < 79 string known_[] = {"YNY", < 80 "NYN", < 81 "YNY"}; < 82 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); < 83 int _ = 1; < 84 END < 85 CASE(2) < 86 string known_[] = {"YY", < 87 "YY", < 88 "YY", < 89 "YY"}; < 90 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); < 91 int _ = 0; < 92 END < 93 CASE(3) < 94 string known_[] = {"NNNNNNNNNN"}; < 95 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); < 96 int _ = 10; < 97 END < 98 CASE(4) < 99 string known_[] = {"NNYYYNN", < 100 "NNNNNYN", < 101 "YYNNNNY", < 102 "NNNYNNN", < 103 "YYNNNNY"}; < 104 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); < 105 int _ = 2; < 106 END < 107 CASE(5) < 108 string known_[] = { < 109 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 110 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 111 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 112 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 113 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 114 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 115 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 116 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 117 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 118 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 119 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 120 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 121 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 122 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 123 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 124 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 125 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 126 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 127 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 128 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 129 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 130 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 131 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 132 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 133 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 134 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 135 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 136 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 137 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 138 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 139 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 140 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 141 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 142 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 143 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 144 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 145 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 146 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 147 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 148 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 149 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 150 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 151 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 152 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 153 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 154 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 155 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 156 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 157 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 158 "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", < 159 }; < 160 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); < 161 int _ = -1; < 162 END < 163 CASE(6) < 164 string known_[] = {"N"}; < 165 vector <string> known(known_, known_+sizeof(known_)/sizeof(*known_)); < 166 int _ = 1; < 167 END < 168 < 169 } < 170 // END CUT HERE <
Deleted SRM/505-u/1B.cpp version [dc8b7855f7fb41f0]
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 <cstring> < 18 using namespace std; < 19 typedef long long LL; < 20 typedef complex<double> CMP; < 21 < 22 class SetMultiples { public: < 23 long long smallestSubset(long long A, long long B, long long C, long lon < 24 { < 25 vector< pair<LL,LL> > noneed( 1, make_pair(1,100000) ); < 26 < 27 LL cnt = 0; < 28 for(LL p=1; p<=100000; ++p) < 29 { < 30 if( A<=p&&p<=B || C<=p&&p<=D ) < 31 if( need(p, A, B, C, D) ) < 32 ++cnt; < 33 if( p > 1 ) { < 34 add(noneed, p, A, B); < 35 add(noneed, p, C, D); < 36 } < 37 } < 38 sort(noneed.begin(), noneed.end(), &my_order); < 39 LL a = count_need(noneed, A, B); < 40 LL b = count_need(noneed, C, D); < 41 return cnt + a + b; < 42 } < 43 < 44 static bool need(LL p, LL A, LL B, LL C, LL D) < 45 { < 46 return !covered(p,A,B) && !covered(p,C,D); < 47 } < 48 < 49 static bool covered(LL p, LL A, LL B) < 50 { < 51 LL lo = A%p==0 ? A/p : A/p+1; < 52 LL hi = B/p; < 53 return ( lo<=hi && 2<=hi ); < 54 } < 55 < 56 static void add(vector< pair<LL,LL> >& noneed, LL p, LL A, LL B) < 57 { < 58 LL lo = A%p==0 ? A/p : A/p+1; < 59 LL hi = B/p; < 60 if( lo <= hi ) < 61 noneed.push_back( make_pair(lo,hi) ); < 62 } < 63 < 64 static bool my_order( const pair<LL,LL>& lhs, const pair<LL,LL>& rhs ) < 65 { < 66 if( lhs.second != rhs.second ) < 67 return lhs.second > rhs.second; < 68 return lhs.first < rhs.first; < 69 } < 70 < 71 static LL count_need(const vector< pair<LL,LL> >& noneed, LL A, LL B) < 72 { < 73 LL cnt = 0; < 74 LL highest_need = B; < 75 for(int i=0; i<noneed.size(); ++i) < 76 { < 77 LL lo = noneed[i].first; < 78 LL hi = noneed[i].second; < 79 if( hi < highest_need ) < 80 cnt += max(0LL, highest_need - max(hi,A-1)); < 81 highest_need = min(highest_need, lo-1); < 82 if( highest_need < A ) < 83 return cnt; < 84 } < 85 return cnt + (highest_need - A + 1); < 86 } < 87 }; < 88 < 89 // BEGIN CUT HERE < 90 #include <ctime> < 91 double start_time; string timer() < 92 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) < 93 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) < 94 { os << "{ "; < 95 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) < 96 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return < 97 void verify_case(const long long& Expected, const long long& Received) { < 98 bool ok = (Expected == Received); < 99 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() < 100 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' < 101 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( < 102 #define END verify_case(_, SetMultiples().smallestSubset(A, B, C, D));} < 103 int main(){ < 104 < 105 CASE(0) < 106 long long A = 1LL; < 107 long long B = 1LL; < 108 long long C = 2LL; < 109 long long D = 2LL; < 110 long long _ = 1LL; < 111 END < 112 CASE(1) < 113 long long A = 1LL; < 114 long long B = 2LL; < 115 long long C = 3LL; < 116 long long D = 4LL; < 117 long long _ = 2LL; < 118 END < 119 CASE(2) < 120 long long A = 2LL; < 121 long long B = 3LL; < 122 long long C = 5LL; < 123 long long D = 7LL; < 124 long long _ = 3LL; < 125 END < 126 CASE(3) < 127 long long A = 1LL; < 128 long long B = 10LL; < 129 long long C = 100LL; < 130 long long D = 1000LL; < 131 long long _ = 500LL; < 132 END < 133 CASE(4) < 134 long long A = 1000000000LL; < 135 long long B = 2000000000LL; < 136 long long C = 9000000000LL; < 137 long long D = 10000000000LL; < 138 long long _ = 1254365078LL; < 139 END < 140 CASE(5) < 141 long long A = 1LL; < 142 long long B = 1000000000LL; < 143 long long C = 2000000000LL; < 144 long long D = 10000000000LL; < 145 long long _ = -1LL; < 146 END < 147 CASE(6) < 148 long long A = 1LL; < 149 long long B = 2LL; < 150 long long C = 3LL; < 151 long long D = 5LL; < 152 long long _ = 3LL; < 153 END < 154 < 155 } < 156 // END CUT HERE <