Overview
| SHA1 Hash: | 9b65a86a4f6a84d0819e78b0c5ee6c7fe0d291c0 |
|---|---|
| Date: | 2011-05-03 10:55:27 |
| User: | kinaba |
| Comment: | 503 |
| 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/503-U/1A.cpp version [b72e6c3073212025]
> 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 ToastXToast { public: > 23 int bake(vector <int> undertoasted, vector <int> overtoasted) > 24 { > 25 vector< pair<int,bool> > t_o; > 26 for(int i=0; i<undertoasted.size(); ++i) > 27 t_o.push_back( make_pair(undertoasted[i], false) ); > 28 for(int i=0; i<overtoasted.size(); ++i) > 29 t_o.push_back( make_pair(overtoasted[i], true) ); > 30 sort(t_o.begin(), t_o.end()); > 31 > 32 vector<bool> o; > 33 for(int i=0; i<t_o.size(); ++i) > 34 o.push_back( t_o[i].second ); > 35 > 36 if( o.front() || !o.back() ) > 37 return -1; > 38 for(int i=0; i+1<o.size(); ++i) > 39 if( o[i] && !o[i+1] ) > 40 return 2; > 41 return 1; > 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 int& Expected, const int& 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(_, ToastXToast().bake(undertoasted, overtoasted));} > 59 int main(){ > 60 > 61 CASE(0) > 62 int undertoasted_[] = {2,4}; > 63 vector <int> undertoasted(undertoasted_, undertoasted_+sizeof(undertoa > 64 int overtoasted_[] = {5,6,3}; > 65 vector <int> overtoasted(overtoasted_, overtoasted_+sizeof(overtoasted > 66 int _ = 2; > 67 END > 68 CASE(1) > 69 int undertoasted_[] = {5}; > 70 vector <int> undertoasted(undertoasted_, undertoasted_+sizeof(undertoa > 71 int overtoasted_[] = {4}; > 72 vector <int> overtoasted(overtoasted_, overtoasted_+sizeof(overtoasted > 73 int _ = -1; > 74 END > 75 CASE(2) > 76 int undertoasted_[] = {1,2,3}; > 77 vector <int> undertoasted(undertoasted_, undertoasted_+sizeof(undertoa > 78 int overtoasted_[] = {5,6,7}; > 79 vector <int> overtoasted(overtoasted_, overtoasted_+sizeof(overtoasted > 80 int _ = 1; > 81 END > 82 CASE(3) > 83 int undertoasted_[] = {1,3,5}; > 84 vector <int> undertoasted(undertoasted_, undertoasted_+sizeof(undertoa > 85 int overtoasted_[] = {2,4,6}; > 86 vector <int> overtoasted(overtoasted_, overtoasted_+sizeof(overtoasted > 87 int _ = 2; > 88 END > 89 /* > 90 CASE(4) > 91 int undertoasted_[] = ; > 92 vector <int> undertoasted(undertoasted_, undertoasted_+sizeof(undertoa > 93 int overtoasted_[] = ; > 94 vector <int> overtoasted(overtoasted_, overtoasted_+sizeof(overtoasted > 95 int _ = ; > 96 END > 97 CASE(5) > 98 int undertoasted_[] = ; > 99 vector <int> undertoasted(undertoasted_, undertoasted_+sizeof(undertoa > 100 int overtoasted_[] = ; > 101 vector <int> overtoasted(overtoasted_, overtoasted_+sizeof(overtoasted > 102 int _ = ; > 103 END > 104 */ > 105 } > 106 // END CUT HERE
Added SRM/503-U/1B.cpp version [fe5a596038457912]
> 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 KingdomXCitiesandVillages { public: > 23 double determineLength(vector <int> cityX, vector <int> cityY, vector <i > 24 { > 25 const int C = cityX.size(); > 26 const int V = villageX.size(); > 27 double answer = 0.0; > 28 > 29 for(int i=0; i<V; ++i) > 30 { > 31 double nc = 1e+30; > 32 for(int j=0; j<C; ++j) > 33 nc = min(nc, distance(villageX[i], villageY[i], > 34 > 35 vector<double> d; > 36 for(int j=0; j<V; ++j) > 37 if( j != i ) > 38 d.push_back( distance(villageX[i], villa > 39 sort(d.begin(), d.end()); > 40 > 41 double prob = 1.0; > 42 for(int j=0; j<d.size() && d[j]<nc; ++j) > 43 { > 44 double p = 1.0 / (j+1) / (j+2); > 45 answer += p * d[j]; > 46 prob -= p; > 47 } > 48 answer += prob * nc; > 49 } > 50 return answer; > 51 } > 52 > 53 static double distance(double x, double y, double X, double Y) > 54 { > 55 return hypot(x-X, y-Y); > 56 } > 57 }; > 58 > 59 // BEGIN CUT HERE > 60 #include <ctime> > 61 double start_time; string timer() > 62 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 63 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 64 { os << "{ "; > 65 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 66 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 67 void verify_case(const double& Expected, const double& Received) { > 68 bool ok = (abs(Expected - Received) < 1e-9); > 69 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 70 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 71 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 72 #define END verify_case(_, KingdomXCitiesandVillages().determineLength(city > 73 int main(){ > 74 > 75 CASE(0) > 76 int cityX_[] = {3}; > 77 vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); > 78 int cityY_[] = {0}; > 79 vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); > 80 int villageX_[] = {3,3}; > 81 vector <int> villageX(villageX_, villageX_+sizeof(villageX_)/sizeof(*v > 82 int villageY_[] = {2,1}; > 83 vector <int> villageY(villageY_, villageY_+sizeof(villageY_)/sizeof(*v > 84 double _ = 2.5; > 85 END > 86 CASE(1) > 87 int cityX_[] = {1,4,7,10}; > 88 vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); > 89 int cityY_[] = {5,5,5,5}; > 90 vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); > 91 int villageX_[] = {1,4,7,10}; > 92 vector <int> villageX(villageX_, villageX_+sizeof(villageX_)/sizeof(*v > 93 int villageY_[] = {4,4,4,4}; > 94 vector <int> villageY(villageY_, villageY_+sizeof(villageY_)/sizeof(*v > 95 double _ = 4.0; > 96 END > 97 CASE(2) > 98 int cityX_[] = {1,2,3}; > 99 vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); > 100 int cityY_[] = {4,4,4}; > 101 vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); > 102 int villageX_[] = {4,5,6}; > 103 vector <int> villageX(villageX_, villageX_+sizeof(villageX_)/sizeof(*v > 104 int villageY_[] = {4,4,4}; > 105 vector <int> villageY(villageY_, villageY_+sizeof(villageY_)/sizeof(*v > 106 double _ = 4.166666666666667; > 107 END > 108 CASE(3) > 109 int cityX_[] = {1}; > 110 vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); > 111 int cityY_[] = {1}; > 112 vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); > 113 int villageX_[] = {2}; > 114 vector <int> villageX(villageX_, villageX_+sizeof(villageX_)/sizeof(*v > 115 int villageY_[] = {1}; > 116 vector <int> villageY(villageY_, villageY_+sizeof(villageY_)/sizeof(*v > 117 double _ = 1; > 118 END > 119 /* > 120 CASE(4) > 121 int cityX_[] = ; > 122 vector <int> cityX(cityX_, cityX_+sizeof(cityX_)/sizeof(*cityX_)); > 123 int cityY_[] = ; > 124 vector <int> cityY(cityY_, cityY_+sizeof(cityY_)/sizeof(*cityY_)); > 125 int villageX_[] = ; > 126 vector <int> villageX(villageX_, villageX_+sizeof(villageX_)/sizeof(*v > 127 int villageY_[] = ; > 128 vector <int> villageY(villageY_, villageY_+sizeof(villageY_)/sizeof(*v > 129 double _ = ; > 130 END > 131 */ > 132 } > 133 // END CUT HERE
Added SRM/503-U/1C-U.cpp version [852235c2e0a91bd6]
> 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 template<typename T> > 23 struct DP2 > 24 { > 25 const int N1, N2; > 26 vector<T> data; > 27 DP2(int N1, int N2, const T& t = T()) > 28 : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)< > 29 T& operator()(int i1, int i2) > 30 { return data[ (i1*N2)+i2 ]; } > 31 }; > 32 > 33 class KingdomXEmergencyStaircase { public: > 34 long long determineCost(string leftBuilding, string rightBuilding, vecto > 35 { > 36 const LL oo = 1LL<<50; > 37 const int W = cost.size(); > 38 const int L = leftBuilding.find_last_of('Y')+1; > 39 const int R = rightBuilding.find_last_of('Y')+1; > 40 const int H = 2*max(L,R)+W; > 41 > 42 LL best = oo; > 43 DP2<LL> dp(H+1, H+1, oo); > 44 for(int l=0; l<=H; l+=2) > 45 for(int r=0; r<=H; r+=2) > 46 if( abs(l-r)<=W && W<=l+r ) > 47 { > 48 if( l==0 ) > 49 { > 50 LL cover_cost = 0; > 51 for(int rr=r-2; rr>=0; rr-=2) > 52 if( rightBuilding[rr/2-1] == 'Y' > 53 cover_cost += cost[(r-rr > 54 dp(l,r) = cost[W-1] + cover_cost; > 55 } > 56 else if( r==0 ) > 57 { > 58 LL cover_cost = 0; > 59 for(int ll=l-2; ll>=0; ll-=2) > 60 if( leftBuilding[ll/2-1] == 'Y' > 61 cover_cost += cost[(l-ll > 62 dp(l,r) = cost[W-1] + cover_cost; > 63 } > 64 else > 65 { > 66 const int mid = W/2 - (r-l)/2; > 67 > 68 LL cur_best = oo; > 69 LL cover_cost = 0; > 70 for(int ll=l-2; ll>=0 && ll>=r-W; ll-=2) > 71 { > 72 if( ll+2 != l && leftBuilding[(l > 73 cover_cost += cost[(l-ll > 74 cur_best = min(cur_best, dp(ll,r > 75 } > 76 cover_cost = 0; > 77 for(int rr=r-2; rr>=0 && rr>=l-W; rr-=2) > 78 { > 79 if( rr+2 != r && rightBuilding[( > 80 cover_cost += cost[(r-rr > 81 cur_best = min(cur_best, dp(l,rr > 82 } > 83 dp(l,r) = cur_best; > 84 } > 85 if( 2*L<=l && 2*R<=r ) > 86 best = min(best, dp(l,r)); > 87 } > 88 return best; > 89 } > 90 }; > 91 > 92 // BEGIN CUT HERE > 93 #include <ctime> > 94 double start_time; string timer() > 95 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 96 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 97 { os << "{ "; > 98 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 99 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 100 void verify_case(const long long& Expected, const long long& Received) { > 101 bool ok = (Expected == Received); > 102 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 103 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 104 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 105 #define END verify_case(_, KingdomXEmergencyStaircase().determineCost(leftB > 106 int main(){ > 107 > 108 CASE(0) > 109 string leftBuilding = "YNYY"; > 110 string rightBuilding = "NNNY"; > 111 int cost_[] = {10, 40, 18, 25}; > 112 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 113 long long _ = 98LL; > 114 END > 115 CASE(1) > 116 string leftBuilding = "N"; > 117 string rightBuilding = "Y"; > 118 int cost_[] = {1, 1000}; > 119 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 120 long long _ = 1000LL; > 121 END > 122 CASE(2) > 123 string leftBuilding = "NNNNNNNY"; > 124 string rightBuilding = "NNNNNNNY"; > 125 int cost_[] = {1, 2}; > 126 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 127 long long _ = 17LL; > 128 END > 129 CASE(3) > 130 string leftBuilding = "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN"; > 131 string rightBuilding = "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNY"; > 132 int cost_[] = {800000000,800000000,800000000,800000000,800000000,8000000 > 133 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 134 long long _ = 6400000000LL; > 135 END > 136 CASE(4) > 137 string leftBuilding = "NNY"; > 138 string rightBuilding = "NNYYY"; > 139 int cost_[] = {10000, 10, 40, 10000, 80, 80}; > 140 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 141 long long _ = 220LL; > 142 END > 143 CASE(5) > 144 string leftBuilding = "YNYNYYNYNYYNYNYYNYNYYNYNYYNYNYYNYNYYNYNYYNYNYYNYNY"; > 145 string rightBuilding = "YNYNYYNYNYYNYNYYNYNYYNYNYYNYNYYNYNYYNYNYYNYNYYNYNY"; > 146 int cost_[] = {958231113, 959939939, 999999999, 954321321, 1000000000, 9 > 147 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 148 long long _ = 58212305211LL; > 149 END > 150 /* > 151 CASE(6) > 152 string leftBuilding = ; > 153 string rightBuilding = ; > 154 int cost_[] = ; > 155 vector <int> cost(cost_, cost_+sizeof(cost_)/sizeof(*cost_)); > 156 long long _ = LL; > 157 END > 158 */ > 159 } > 160 // END CUT HERE