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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 67 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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 long D) 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) << " msec)"; return os.str(); } 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 os; } 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() << endl; 100 - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 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