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

Added SRM/TCO19-2B-U/1A.cpp version [a6fb42ce604b79df]

            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 MedianFaking { public:
           23  + vector <int> minimize(int F, int M, vector <int> data, int goal)
           24  + {
           25  +  vector<pair<int, int>> VP;
           26  +  for (int p = 0; p < F; ++p)
           27  +   for (int m = 0; m < M; ++m)
           28  +    VP.emplace_back(data[p*M + m], p);
           29  +  sort(VP.begin(), VP.end());
           30  +
           31  +  const int N = VP.size();
           32  +  const int mid = (N - 1) / 2;
           33  +
           34  +  for (int s = 0; s <= N; ++s) {
           35  +   if (s == N || VP[s].first >= goal) {
           36  +    for (int m = s; m <= N; ++m) {
           37  +     if (m == N || VP[m].first > goal) {
           38  +      // small goal big
           39  +      // [0,s)[s,m)[m,N)
           40  +      if (s <= mid && mid < m)
           41  +       return{ 0,0 };
           42  +      if (s > mid) {
           43  +       return{ choose(s - mid, vector<pair<int, int>>(VP.begin(), VP.begin() + s)), s - mid };
           44  +      }
           45  +      if (m <= mid) {
           46  +       return{ choose(mid - m + 1, vector<pair<int, int>>(VP.begin() + m, VP.end())), mid - m + 1 };
           47  +      }
           48  +      return{ -1,-1 };
           49  +     }
           50  +    }
           51  +    break;
           52  +   }
           53  +  }
           54  +  return{ -1,-1 };
           55  + }
           56  +
           57  + int choose(int k, const vector<pair<int, int>>& VP)
           58  + {
           59  +  map<int, int> pcmap;
           60  +  for (auto vp : VP) pcmap[vp.second]++;
           61  +  vector<int> cs;
           62  +  for (auto pc : pcmap) cs.emplace_back(pc.second);
           63  +  sort(cs.rbegin(), cs.rend());
           64  +
           65  +  int p = 0;
           66  +  for (auto c: cs) {
           67  +   ++p;
           68  +   k -= c;
           69  +   if (k <= 0) break;
           70  +  }
           71  +  return p;
           72  + }
           73  +};
           74  +
           75  +// BEGIN CUT HERE
           76  +#include <ctime>
           77  +double start_time; string timer()
           78  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           79  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           80  + { os << "{ ";
           81  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           82  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           83  +void verify_case(const vector <int>& Expected, const vector <int>& Received) {
           84  + bool ok = (Expected == Received);
           85  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           86  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           87  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           88  +#define END  verify_case(_, MedianFaking().minimize(F, M, data, goal));}
           89  +int main(){
           90  +
           91  +CASE(0)
           92  + int F = 5;
           93  + int M = 5;
           94  + int data_[] = {1,2,3,4,5, 10,9,8,7,6, 25,24,23,22,21, 18,16,17,19,20, 11,13,12,14,15};
           95  +   vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_));
           96  + int goal = 8;
           97  + int __[] = {1, 5 };
           98  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           99  +END
          100  +CASE(1)
          101  + int F = 5;
          102  + int M = 5;
          103  + int data_[] = {1,2,25,24,23, 3,4,22,21,20, 5,6,19,18,17, 7,16,15,14,13, 8,12,11,10,9};
          104  +   vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_));
          105  + int goal = 8;
          106  + int __[] = {2, 5 };
          107  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          108  +END
          109  +CASE(2)
          110  + int F = 1;
          111  + int M = 4;
          112  + int data_[] = {10, 40, 30, 20};
          113  +   vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_));
          114  + int goal = 20;
          115  + int __[] = {0, 0 };
          116  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          117  +END
          118  +CASE(3)
          119  + int F = 4;
          120  + int M = 3;
          121  + int data_[] = {3,8,12, 3,8,12, 3,8,12, 8,12,17};
          122  +   vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_));
          123  + int goal = 12;
          124  + int __[] = {1, 2 };
          125  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          126  +END
          127  +CASE(4)
          128  + int F = 5;
          129  + int M = 1;
          130  + int data_[] = {10, 20, 30, 40, 50};
          131  +   vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_));
          132  + int goal = 23;
          133  + int __[] = {1, 1 };
          134  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          135  +END
          136  +CASE(5)
          137  + int F = 1;
          138  + int data_[] = { 2 };
          139  + vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_));
          140  + int M = data.size()/F;
          141  + int goal = 3;
          142  + int __[] = { 1,1 };
          143  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          144  +END
          145  +/*
          146  +CASE(6)
          147  + int F = ;
          148  + int M = ;
          149  + int data_[] = ;
          150  +   vector <int> data(data_, data_+sizeof(data_)/sizeof(*data_));
          151  + int goal = ;
          152  + int __[] = ;
          153  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          154  +END
          155  +*/
          156  +}
          157  +// END CUT HERE

Added SRM/TCO19-2B-U/1B.cpp version [48bece87186a64cd]

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