• branch=trunk inherited from [9165bd3629]
• sym-trunk inherited from [9165bd3629]

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) << " msec)"; return os.str(); }
           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 os; }
           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() << endl;
           56  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           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(undertoasted_)/sizeof(*undertoasted_));
           64  + int overtoasted_[] = {5,6,3};
           65  +   vector <int> overtoasted(overtoasted_, overtoasted_+sizeof(overtoasted_)/sizeof(*overtoasted_));
           66  + int _ = 2;
           67  +END
           68  +CASE(1)
           69  + int undertoasted_[] = {5};
           70  +   vector <int> undertoasted(undertoasted_, undertoasted_+sizeof(undertoasted_)/sizeof(*undertoasted_));
           71  + int overtoasted_[] = {4};
           72  +   vector <int> overtoasted(overtoasted_, overtoasted_+sizeof(overtoasted_)/sizeof(*overtoasted_));
           73  + int _ = -1;
           74  +END
           75  +CASE(2)
           76  + int undertoasted_[] = {1,2,3};
           77  +   vector <int> undertoasted(undertoasted_, undertoasted_+sizeof(undertoasted_)/sizeof(*undertoasted_));
           78  + int overtoasted_[] = {5,6,7};
           79  +   vector <int> overtoasted(overtoasted_, overtoasted_+sizeof(overtoasted_)/sizeof(*overtoasted_));
           80  + int _ = 1;
           81  +END
           82  +CASE(3)
           83  + int undertoasted_[] = {1,3,5};
           84  +   vector <int> undertoasted(undertoasted_, undertoasted_+sizeof(undertoasted_)/sizeof(*undertoasted_));
           85  + int overtoasted_[] = {2,4,6};
           86  +   vector <int> overtoasted(overtoasted_, overtoasted_+sizeof(overtoasted_)/sizeof(*overtoasted_));
           87  + int _ = 2;
           88  +END
           89  +/*
           90  +CASE(4)
           91  + int undertoasted_[] = ;
           92  +   vector <int> undertoasted(undertoasted_, undertoasted_+sizeof(undertoasted_)/sizeof(*undertoasted_));
           93  + int overtoasted_[] = ;
           94  +   vector <int> overtoasted(overtoasted_, overtoasted_+sizeof(overtoasted_)/sizeof(*overtoasted_));
           95  + int _ = ;
           96  +END
           97  +CASE(5)
           98  + int undertoasted_[] = ;
           99  +   vector <int> undertoasted(undertoasted_, undertoasted_+sizeof(undertoasted_)/sizeof(*undertoasted_));
          100  + int overtoasted_[] = ;
          101  +   vector <int> overtoasted(overtoasted_, overtoasted_+sizeof(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 <int> villageX, vector <int> villageY)
           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], cityX[j], cityY[j]));
           34  +
           35  +   vector<double> d;
           36  +   for(int j=0; j<V; ++j)
           37  +    if( j != i )
           38  +     d.push_back( distance(villageX[i], villageY[i], villageX[j], villageY[j]) );
           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) << " msec)"; return os.str(); }
           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 os; }
           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() << endl;
           70  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           71  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           72  +#define END  verify_case(_, KingdomXCitiesandVillages().determineLength(cityX, cityY, villageX, villageY));}
           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(*villageX_));
           82  + int villageY_[] = {2,1};
           83  +   vector <int> villageY(villageY_, villageY_+sizeof(villageY_)/sizeof(*villageY_));
           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(*villageX_));
           93  + int villageY_[] = {4,4,4,4};
           94  +   vector <int> villageY(villageY_, villageY_+sizeof(villageY_)/sizeof(*villageY_));
           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(*villageX_));
          104  + int villageY_[] = {4,4,4};
          105  +   vector <int> villageY(villageY_, villageY_+sizeof(villageY_)/sizeof(*villageY_));
          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(*villageX_));
          115  +   int villageY_[] = {1};
          116  +   vector <int> villageY(villageY_, villageY_+sizeof(villageY_)/sizeof(*villageY_));
          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(*villageX_));
          127  + int villageY_[] = ;
          128  +   vector <int> villageY(villageY_, villageY_+sizeof(villageY_)/sizeof(*villageY_));
          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)<(1<<26)); }
           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, vector <int> cost)
           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)/2-1];
           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)/2-1];
           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[(ll+2)/2-1]=='Y' )
           73  +       cover_cost += cost[(l-ll-2)/2 - 1];
           74  +      cur_best = min(cur_best, dp(ll,r)+cost[mid-1]+cover_cost);
           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[(rr+2)/2-1]=='Y' )
           80  +       cover_cost += cost[(r-rr-2)/2 - 1];
           81  +      cur_best = min(cur_best, dp(l,rr)+cost[W-mid-1]+cover_cost);
           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) << " msec)"; return os.str(); }
           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 os; }
          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() << endl;
          103  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          104  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          105  +#define END  verify_case(_, KingdomXEmergencyStaircase().determineCost(leftBuilding, rightBuilding, cost));}
          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,800000000,800000000,800000000};
          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, 998998998, 987987987, 999888777, 1000000000, 1000000000};
          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