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

Added SRM/678-U/1A.cpp version [52600c1b1ddbdd87]

            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 ANewHope { public:
           23  + int count(vector <int> firstWeek, vector <int> lastWeek, int D)
           24  + {
           25  +  const int N = firstWeek.size();
           26  +  const int s = N-D;
           27  +  int worst = 0;
           28  +  for(int v=1; v<=N; ++v) {
           29  +   int a = find(firstWeek.begin(), firstWeek.end(), v) - firstWeek.begin();
           30  +   int b = find(lastWeek.begin(), lastWeek.end(), v) - lastWeek.begin();
           31  +   worst = max(worst, b==a ? 0 : b>a ? 1 : (a-b+s-1)/s);
           32  +  }
           33  +  return worst+1;
           34  + }
           35  +};
           36  +
           37  +// BEGIN CUT HERE
           38  +#include <ctime>
           39  +double start_time; string timer()
           40  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           41  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           42  + { os << "{ ";
           43  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           44  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           45  +void verify_case(const int& Expected, const int& Received) {
           46  + bool ok = (Expected == Received);
           47  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           48  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           49  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           50  +#define END  verify_case(_, ANewHope().count(firstWeek, lastWeek, D));}
           51  +int main(){
           52  +
           53  +CASE(0)
           54  + int firstWeek_[] = {1,2,3,4};
           55  +   vector <int> firstWeek(firstWeek_, firstWeek_+sizeof(firstWeek_)/sizeof(*firstWeek_));
           56  + int lastWeek_[] = {4,3,2,1};
           57  +   vector <int> lastWeek(lastWeek_, lastWeek_+sizeof(lastWeek_)/sizeof(*lastWeek_));
           58  + int D = 3;
           59  + int _ = 4;
           60  +END
           61  +CASE(1)
           62  + int firstWeek_[] = {8,5,4,1,7,6,3,2};
           63  +   vector <int> firstWeek(firstWeek_, firstWeek_+sizeof(firstWeek_)/sizeof(*firstWeek_));
           64  + int lastWeek_[] = {2,4,6,8,1,3,5,7};
           65  +   vector <int> lastWeek(lastWeek_, lastWeek_+sizeof(lastWeek_)/sizeof(*lastWeek_));
           66  + int D = 3;
           67  + int _ = 3;
           68  +END
           69  +CASE(2)
           70  + int firstWeek_[] = {1,2,3,4};
           71  +   vector <int> firstWeek(firstWeek_, firstWeek_+sizeof(firstWeek_)/sizeof(*firstWeek_));
           72  + int lastWeek_[] = {1,2,3,4};
           73  +   vector <int> lastWeek(lastWeek_, lastWeek_+sizeof(lastWeek_)/sizeof(*lastWeek_));
           74  + int D = 2;
           75  + int _ = 1;
           76  +END
           77  +/*
           78  +CASE(3)
           79  + int firstWeek_[] = ;
           80  +   vector <int> firstWeek(firstWeek_, firstWeek_+sizeof(firstWeek_)/sizeof(*firstWeek_));
           81  + int lastWeek_[] = ;
           82  +   vector <int> lastWeek(lastWeek_, lastWeek_+sizeof(lastWeek_)/sizeof(*lastWeek_));
           83  + int D = ;
           84  + int _ = ;
           85  +END
           86  +CASE(4)
           87  + int firstWeek_[] = ;
           88  +   vector <int> firstWeek(firstWeek_, firstWeek_+sizeof(firstWeek_)/sizeof(*firstWeek_));
           89  + int lastWeek_[] = ;
           90  +   vector <int> lastWeek(lastWeek_, lastWeek_+sizeof(lastWeek_)/sizeof(*lastWeek_));
           91  + int D = ;
           92  + int _ = ;
           93  +END
           94  +*/
           95  +}
           96  +// END CUT HERE

Added SRM/678-U/1B.cpp version [01e65b483160dba9]

            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 TheEmpireStrikesBack { public:
           23  + int find(int AX, int BX, int CX, int AY, int BY, int CY, int N, int M)
           24  + {
           25  +  vector<pair<int,int>> P(N);
           26  +  P[0].first = AX;
           27  +  P[0].second = AY;
           28  +  for(int i=1; i<N; ++i) {
           29  +   P[i].first = int((LL(P[i-1].first) * BX + CX) % 1000000007);
           30  +   P[i].second = int((LL(P[i-1].second) * BY + CY) % 1000000007);
           31  +  }
           32  +
           33  +  // Sort: Large Y first, Large X first
           34  +  sort(P.begin(), P.end(), [&](const pair<int,int>& lhs, const pair<int,int>& rhs){
           35  +   if(lhs.second == rhs.second) return lhs.first > rhs.first;
           36  +   return lhs.second > rhs.second;
           37  +  });
           38  +
           39  +  // Border stars, worth targetting.
           40  +  vector<pair<int,int>> B;
           41  +  for(auto& p: P)
           42  +   if(B.empty() || B.back().first < p.first)
           43  +    B.push_back(p);
           44  +
           45  +  int L=-1, R=1000000007; // (L,R]
           46  +  while(R-L>1) {
           47  +   int C = (L+R)/2;
           48  +   (least_missile_to_destory_all(B, C)<=M ? R : L) = C;
           49  +  }
           50  +  return R;
           51  + }
           52  +
           53  + int least_missile_to_destory_all(const vector<pair<int,int>>& B, int T)
           54  + {
           55  +  // Greedy.
           56  +  int count = 0;
           57  +  for(int to_cover=0; to_cover<B.size(); ) {
           58  +   int missile = to_cover;
           59  +   for(; missile<B.size(); ++missile)
           60  +    if(B[missile].first+T < B[to_cover].first || B[missile].second+T < B[to_cover].second)
           61  +     break;
           62  +   --missile;
           63  +   ++count;
           64  +   for(; to_cover<B.size(); ++to_cover)
           65  +    if(B[missile].first+T < B[to_cover].first || B[missile].second+T < B[to_cover].second)
           66  +     break;
           67  +  }
           68  +  return count;
           69  + }
           70  +};
           71  +
           72  +// BEGIN CUT HERE
           73  +#include <ctime>
           74  +double start_time; string timer()
           75  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           76  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           77  + { os << "{ ";
           78  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           79  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           80  +void verify_case(const int& Expected, const int& Received) {
           81  + bool ok = (Expected == Received);
           82  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           83  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           84  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           85  +#define END  verify_case(_, TheEmpireStrikesBack().find(AX, BX, CX, AY, BY, CY, N, M));}
           86  +int main(){
           87  +
           88  +CASE(0)
           89  + int AX = 2;
           90  + int BX = 2;
           91  + int CX = 2;
           92  + int AY = 2;
           93  + int BY = 2;
           94  + int CY = 2;
           95  + int N = 2;
           96  + int M = 1;
           97  + int _ = 0;
           98  +END
           99  +CASE(1)
          100  + int AX = 2;
          101  + int BX = 2;
          102  + int CX = 2;
          103  + int AY = 2;
          104  + int BY = 4;
          105  + int CY = 1000000000;
          106  + int N = 2;
          107  + int M = 1;
          108  + int _ = 1;
          109  +END
          110  +CASE(2)
          111  + int AX = 1;
          112  + int BX = 3;
          113  + int CX = 8;
          114  + int AY = 10000;
          115  + int BY = 10;
          116  + int CY = 999910000;
          117  + int N = 3;
          118  + int M = 1;
          119  + int _ = 30;
          120  +END
          121  +CASE(3)
          122  + int AX = 0;
          123  + int BX = 0;
          124  + int CX = 0;
          125  + int AY = 0;
          126  + int BY = 0;
          127  + int CY = 0;
          128  + int N = 100000;
          129  + int M = 1000;
          130  + int _ = 0;
          131  +END
          132  +CASE(4)
          133  + int AX = 10;
          134  + int BX = 20;
          135  + int CX = 30;
          136  + int AY = 40;
          137  + int BY = 50;
          138  + int CY = 60;
          139  + int N = 100000;
          140  + int M = 10;
          141  + int _ = 15720;
          142  +END
          143  +/*
          144  +CASE(5)
          145  + int AX = ;
          146  + int BX = ;
          147  + int CX = ;
          148  + int AY = ;
          149  + int BY = ;
          150  + int CY = ;
          151  + int N = ;
          152  + int M = ;
          153  + int _ = ;
          154  +END
          155  +CASE(6)
          156  + int AX = ;
          157  + int BX = ;
          158  + int CX = ;
          159  + int AY = ;
          160  + int BY = ;
          161  + int CY = ;
          162  + int N = ;
          163  + int M = ;
          164  + int _ = ;
          165  +END
          166  +*/
          167  +}
          168  +// END CUT HERE

Added SRM/678-U/1C-U.cpp version [1517aa3e89cb81aa]

            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 ReturnOfTheJedi { public:
           23  + vector <double> minimalExpectation(vector <int> x, vector <int> p)
           24  + {
           25  +  vector<pair<double,double>> item;
           26  +  for(int i=0; i<x.size(); ++i)
           27  +   item.emplace_back(p[i]/100000.0, x[i]);
           28  +
           29  +  vector<double> ans(x.size());
           30  +
           31  +  vector<pair<double,double>> iA = item;
           32  +  double pA = 1.0;
           33  +  double xA = 0.0;
           34  +  vector<pair<double,double>> iB = item;
           35  +  double pB = 1.0;
           36  +  double xB = 0.0;
           37  +  {
           38  +   vector<pair<double,double>>::iterator b1 = iB.begin();
           39  +   double best_score = 1e+300;
           40  +   for(vector<pair<double,double>>::iterator it = iB.begin(); it != iB.end(); ++it) {
           41  +    double score = it->first * it->second;
           42  +    if(best_score > score)
           43  +     {b1 = it, best_score = score;}
           44  +   }
           45  +   pB = b1->first;
           46  +   xB = b1->second;
           47  +   iB.erase(b1);
           48  +   ans[0] = (pB*xB);
           49  +  }
           50  +
           51  +  for(int k=1; k<ans.size(); ++k) {
           52  +   vector<pair<double,double>>::iterator b1 = iB.begin();
           53  +   double best_score = 1e+300;
           54  +   for(vector<pair<double,double>>::iterator it = iB.begin(); it != iB.end(); ++it) {
           55  +    double score = pB*it->first * (xB+it->second);
           56  +    if(best_score > score)
           57  +     {b1 = it, best_score = score;}
           58  +   }
           59  +   vector<pair<double,double>>::iterator b2 = iA.begin();
           60  +   vector<pair<double,double>>::iterator b3 = iA.begin();
           61  +   bool A_mode = false;
           62  +   for(vector<pair<double,double>>::iterator it = iA.begin(); it != iA.end(); ++it)
           63  +   for(vector<pair<double,double>>::iterator kt = it; kt != iA.end(); ++kt) if(kt!=it){
           64  +    double score = pA*it->first*kt->first * (xA+it->second+kt->second);
           65  +    if(best_score > score)
           66  +     {b2 = it, b3 = kt, best_score = score, A_mode = true;}
           67  +   }
           68  +   if(!A_mode) {
           69  +    pA = pB;
           70  +    xA = xB;
           71  +    iA = iB;
           72  +    pB *= b1->first;
           73  +    xB += b1->second;
           74  +    iB.erase(b1);
           75  +   } else {
           76  +    pA *= b2->first * b3->first;
           77  +    xA += b2->second + b3->second;
           78  +    auto xxx = *b3;
           79  +    iA.erase(b2);
           80  +    iA.erase(std::find(iA.begin(), iA.end(), xxx));
           81  +    swap(pA, pB);
           82  +    swap(xA, xB);
           83  +    swap(iA, iB);
           84  +   }
           85  +   ans[k] = pB*xB;
           86  +  }
           87  +  return ans;
           88  + }
           89  +};
           90  +
           91  +// BEGIN CUT HERE
           92  +#include <ctime>
           93  +double start_time; string timer()
           94  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           95  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           96  + { os << "{ ";
           97  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           98  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           99  +void verify_case(const vector <double>& Expected, const vector <double>& Received) {
          100  + bool ok = true;
          101  + for(int i=0; i<Expected.size(); ++i)
          102  +   if( abs(Expected[i]-Received[i]) >= 1e-9 )
          103  +     ok = false;
          104  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          105  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
          106  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          107  +#define END  verify_case(_, ReturnOfTheJedi().minimalExpectation(x, p));}
          108  +int main(){
          109  +
          110  +CASE(0)
          111  + int x_[] = {100,200,300};
          112  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          113  + int p_[] = {50000, 20000, 20000};
          114  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          115  + double __[] = {40.0, 20.000000000000004, 12.000000000000002 };
          116  +   vector <double> _(__, __+sizeof(__)/sizeof(*__));
          117  +END
          118  +CASE(1)
          119  + int x_[] = {200,100,500,300,400};
          120  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          121  + int p_[] = {100000, 100000, 100000, 100000, 100000};
          122  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          123  + double __[] = {100.0, 300.0, 600.0, 1000.0, 1500.0 };
          124  +   vector <double> _(__, __+sizeof(__)/sizeof(*__));
          125  +END
          126  +CASE(2)
          127  + int x_[] = {2,2,100,100};
          128  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          129  + int p_[] = {100000,100000,10000,10000};
          130  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          131  + double __[] = {2.0, 2.0000000000000004, 2.0200000000000005, 2.0400000000000005 };
          132  +   vector <double> _(__, __+sizeof(__)/sizeof(*__));
          133  +END
          134  +CASE(3)
          135  + int x_[] = {1,1,200,200};
          136  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          137  + int p_[] = {100000,100000,10000,10000};
          138  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          139  + double __[] = {1.0, 2.0, 4.010000000000001, 4.0200000000000005 };
          140  +   vector <double> _(__, __+sizeof(__)/sizeof(*__));
          141  +END
          142  +CASE(4)
          143  + int x_[] = {1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000,1000000000};
          144  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          145  + int p_[] = {90000,90000,90000,90000,90000,90000,90000,90000,90000,90000};
          146  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          147  + double __[] = {9.0E8, 1.62E9, 2.1870000000000005E9, 2.6244000000000005E9, 2.952450000000001E9, 3.188646000000001E9, 3.348078300000001E9, 3.4437376800000014E9, 3.4867844010000014E9, 3.4867844010000014E9 };
          148  +   vector <double> _(__, __+sizeof(__)/sizeof(*__));
          149  +END
          150  +/*
          151  +CASE(5)
          152  + int x_[] = ;
          153  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          154  + int p_[] = ;
          155  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          156  + double __[] = ;
          157  +   vector <double> _(__, __+sizeof(__)/sizeof(*__));
          158  +END
          159  +CASE(6)
          160  + int x_[] = ;
          161  +   vector <int> x(x_, x_+sizeof(x_)/sizeof(*x_));
          162  + int p_[] = ;
          163  +   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
          164  + double __[] = ;
          165  +   vector <double> _(__, __+sizeof(__)/sizeof(*__));
          166  +END
          167  +*/
          168  +}
          169  +// END CUT HERE