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

Added SRM/TCO19-3B-U/1A.cpp version [710858e8febd2397]

            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 TwoLadders { public:
           23  + long long minSteps(int sx, int lx1, int lx2, vector <int> X, vector <int> Y)
           24  + {
           25  +  map<int, vector<int>> y2x;
           26  +  for (int i = 0; i < X.size(); ++i)
           27  +   y2x[Y[i]].push_back(X[i]);
           28  +
           29  +  map<int, pair<int, int>> y2mM;
           30  +  for (auto kv : y2x)
           31  +   y2mM[kv.first] = make_pair(
           32  +    *min_element(kv.second.begin(), kv.second.end()),
           33  +    *max_element(kv.second.begin(), kv.second.end())
           34  +   );
           35  +
           36  +  auto cur = y2mM.begin();
           37  +
           38  +  // best 2 move candidates in the prvious level
           39  +  int p1 = sx;
           40  +  int p2 = sx;
           41  +  LL  b1 = 0;
           42  +  LL  b2 = 0;
           43  +  int yy = 0;
           44  +
           45  +  if(cur->first == 0) {
           46  +   int m = cur->second.first;
           47  +   int M = cur->second.second;
           48  +   ++cur;
           49  +   p1 = m;
           50  +   b1 = abs(sx - M) + abs(M - m);
           51  +   p2 = M;
           52  +   b2 = abs(sx - m) + abs(M - m);
           53  +  }
           54  +
           55  +  for (; cur != y2mM.end(); ++cur) {
           56  +   int ydiff = cur->first - yy;
           57  +   yy = cur->first;
           58  +   int m = cur->second.first;
           59  +   int M = cur->second.second;
           60  +
           61  +   int prev_p1 = p1;
           62  +   int prev_p2 = p2;
           63  +   LL prev_b1 = b1;
           64  +   LL prev_b2 = b2;
           65  +
           66  +   p1 = m;
           67  +   b1 = min({
           68  +    prev_b1 + ydiff + abs(prev_p1 - lx1) + abs(lx1 - M) + abs(M - m),
           69  +    prev_b1 + ydiff + abs(prev_p1 - lx2) + abs(lx2 - M) + abs(M - m),
           70  +    prev_b2 + ydiff + abs(prev_p2 - lx1) + abs(lx1 - M) + abs(M - m),
           71  +    prev_b2 + ydiff + abs(prev_p2 - lx2) + abs(lx2 - M) + abs(M - m),
           72  +   });
           73  +   p2 = M;
           74  +   b2 = min({
           75  +    prev_b1 + ydiff + abs(prev_p1 - lx1) + abs(lx1 - m) + abs(M - m),
           76  +    prev_b1 + ydiff + abs(prev_p1 - lx2) + abs(lx2 - m) + abs(M - m),
           77  +    prev_b2 + ydiff + abs(prev_p2 - lx1) + abs(lx1 - m) + abs(M - m),
           78  +    prev_b2 + ydiff + abs(prev_p2 - lx2) + abs(lx2 - m) + abs(M - m),
           79  +   });
           80  +  }
           81  +  return min(b1, b2);
           82  + }
           83  +};
           84  +
           85  +// BEGIN CUT HERE
           86  +#include <ctime>
           87  +double start_time; string timer()
           88  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           89  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           90  + { os << "{ ";
           91  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           92  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           93  +void verify_case(const long long& Expected, const long long& Received) {
           94  + bool ok = (Expected == Received);
           95  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           96  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           97  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           98  +#define END  verify_case(_, TwoLadders().minSteps(sx, lx1, lx2, X, Y));}
           99  +int main(){
          100  +
          101  +CASE(0)
          102  + int sx = 10;
          103  + int lx1 = 0;
          104  + int lx2 = 100;
          105  + int X_[] = {47, 42};
          106  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          107  + int Y_[] = {0, 0};
          108  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          109  + long long _ = 37LL;
          110  +END
          111  +CASE(1)
          112  + int sx = 10;
          113  + int lx1 = 8;
          114  + int lx2 = 11;
          115  + int X_[] = {10, 12};
          116  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          117  + int Y_[] = {1, 1};
          118  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          119  + long long _ = 5LL;
          120  +END
          121  +CASE(2)
          122  + int sx = 10;
          123  + int lx1 = 8;
          124  + int lx2 = 42;
          125  + int X_[] = {10, 12};
          126  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          127  + int Y_[] = {1, 1};
          128  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          129  + long long _ = 7LL;
          130  +END
          131  +CASE(3)
          132  + int sx = 10;
          133  + int lx1 = 8;
          134  + int lx2 = 42;
          135  + int X_[] = {10, 100, 12};
          136  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          137  + int Y_[] = {1, 0, 1};
          138  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          139  + long long _ = 181LL;
          140  +END
          141  +CASE(4)
          142  + int sx = 500000000;
          143  + int lx1 = 1;
          144  + int lx2 = 999999999;
          145  + int X_[] = {0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000, 0, 1000000000};
          146  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          147  + int Y_[] = {1, 1, 2, 2, 3, 3, 4, 4, 7, 7, 999999947, 999999947, 900000047, 900000047};
          148  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          149  + long long _ = 8499999959LL;
          150  +END
          151  +/*
          152  +CASE(5)
          153  + int sx = ;
          154  + int lx1 = ;
          155  + int lx2 = ;
          156  + int X_[] = ;
          157  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          158  + int Y_[] = ;
          159  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          160  + long long _ = LL;
          161  +END
          162  +CASE(6)
          163  + int sx = ;
          164  + int lx1 = ;
          165  + int lx2 = ;
          166  + int X_[] = ;
          167  +   vector <int> X(X_, X_+sizeof(X_)/sizeof(*X_));
          168  + int Y_[] = ;
          169  +   vector <int> Y(Y_, Y_+sizeof(Y_)/sizeof(*Y_));
          170  + long long _ = LL;
          171  +END
          172  +*/
          173  +}
          174  +// END CUT HERE

Added SRM/TCO19-3B-U/1B.cpp version [70b57b6d4d4ca3f0]

            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 PrefixComposite { public:
           23  + vector<long long> minMax(long long A, long long B)
           24  + {
           25  +  LL r = solve(B);
           26  +  if (r < A)
           27  +   return vector<LL>();
           28  +
           29  +  LL L = A - 1, R = r;
           30  +  while(R-L>1) {
           31  +   LL C = (L + R) / 2;
           32  +   LL c = solve(C);
           33  +   if (c < A)
           34  +    L = C;
           35  +   else
           36  +    R = c;
           37  +  }
           38  +  return vector<LL>({ R, r });
           39  + }
           40  +
           41  + // max such value <= B
           42  + LL solve(LL B) {
           43  +  vector<int> bb;
           44  +  for(; B!=0; B/=10)
           45  +   bb.push_back(B % 10);
           46  +  reverse(bb.begin(), bb.end());
           47  +
           48  +  function<LL(LL, int)> rec = [&](LL pref, int i) {
           49  +   if (i == bb.size())
           50  +    return pref;
           51  +
           52  +   LL pp = pref * 10 + bb[i];
           53  +   if(is_composite(pp)) {
           54  +    LL r = rec(pp, i + 1);
           55  +    if (r)
           56  +     return r;
           57  +   }
           58  +
           59  +   for (int k = bb[i] - 1; k >= 0; --k) {
           60  +    LL pp = pref * 10 + k;
           61  +    if (is_composite(pp)) {
           62  +     int n = bb.size() - i - 1;
           63  +     // get max from pp ++ [0-9]*n
           64  +     for (int j = 0; j < n; ++j)
           65  +      if (is_composite(pp*10+9))
           66  +       pp = pp*10+9;
           67  +      else
           68  +       pp = pp*10+8;
           69  +     return pp;
           70  +    }
           71  +   }
           72  +   return 0LL;
           73  +  };
           74  +  return rec(0, 0);
           75  + }
           76  +
           77  + bool is_composite(LL v)
           78  + {
           79  +  if (v == 0)
           80  +   return true;
           81  +  for (LL p = 2; p*p <= v; ++p)
           82  +   if (v%p == 0)
           83  +    return true;
           84  +  return false;
           85  + }
           86  +};
           87  +
           88  +// BEGIN CUT HERE
           89  +#include <ctime>
           90  +double start_time; string timer()
           91  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           92  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           93  + { os << "{ ";
           94  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           95  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           96  +void verify_case(const vector<long long>& Expected, const vector<long long>& Received) {
           97  + bool ok = (Expected == Received);
           98  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           99  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
          100  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          101  +#define END  verify_case(_, PrefixComposite().minMax(A, B));}
          102  +int main(){
          103  +
          104  +CASE(0)
          105  + long long A = 1LL;
          106  + long long B = 3LL;
          107  + vector<long long> _;
          108  +END
          109  +CASE(1)
          110  + long long A = 1LL;
          111  + long long B = 4LL;
          112  + long long __[] = {4, 4 };
          113  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          114  +END
          115  +CASE(2)
          116  + long long A = 123LL;
          117  + long long B = 838LL;
          118  + long long __[] = {400, 828 };
          119  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          120  +END
          121  +CASE(3)
          122  + long long A = 409LL;
          123  + long long B = 87343LL;
          124  + long long __[] = {420, 87343 };
          125  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          126  +END
          127  +CASE(4)
          128  + long long A = 979797LL;
          129  + long long B = 979898LL;
          130  + vector<long long> _;
          131  +END
          132  +CASE(5)
          133  + long long A = 600LL;
          134  + long long B = 703LL;
          135  + long long __[] = {600, 699 };
          136  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          137  +END
          138  +CASE(6)
          139  + long long A = 1LL;
          140  + long long B = 100000000000LL;
          141  + long long __[] = {4, 99999999999 };
          142  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          143  +END
          144  +CASE(7)
          145  + long long A = 37337999LL;
          146  + long long B = 37337999LL;
          147  + vector<long long> _;
          148  +END
          149  +CASE(8)
          150  + long long A = 22LL;
          151  + long long B = 39LL;
          152  + vector<long long> _;
          153  +END
          154  +CASE(9)
          155  + long long A = 600LL;
          156  + long long B = 699LL;
          157  + long long __[] = { 600, 699 };
          158  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          159  +END
          160  +CASE(10)
          161  + long long A = 1LL;
          162  + long long B = 1LL;
          163  + vector<long long> _;
          164  +END
          165  +CASE(10)
          166  +long long A = 1LL;
          167  +long long B = 6LL;
          168  +vector<long long> _;
          169  +END
          170  +}
          171  +// END CUT HERE

Added SRM/TCO19-3B-U/1C-U.cpp version [4aebde82e204f3cf]

            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  +static const unsigned MODVAL = 1000000007;
           23  +struct mint
           24  +{
           25  + unsigned val;
           26  + mint() :val(0) {}
           27  + mint(int      x) :val(x%MODVAL) {}
           28  + mint(unsigned x) :val(x%MODVAL) {}
           29  + mint(LL       x) :val(x%MODVAL) {}
           30  +};
           31  +mint& operator+=(mint& x, mint y) { return x = x.val + y.val; }
           32  +mint& operator-=(mint& x, mint y) { return x = x.val - y.val + MODVAL; }
           33  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           34  +mint operator+(mint x, mint y) { return x += y; }
           35  +mint operator-(mint x, mint y) { return x -= y; }
           36  +mint operator*(mint x, mint y) { return x *= y; }
           37  +mint POW(mint x, LL e) { mint v = 1; for (; e; x *= x, e >>= 1) if (e & 1) v *= x; return v; }
           38  +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL - 2); }
           39  +mint operator/(mint x, mint y) { return x /= y; }
           40  +
           41  +class DiagonalColumn { public:
           42  + int countGrids(int H, int W)
           43  + {
           44  +  mint ans = 1; // all black
           45  +  for(int l=0; l<W; ++l)
           46  +   for (int r = 0; l + r < W; ++r) {
           47  +    if (W - l - r <= 2)
           48  +     ans += 1;
           49  +    else
           50  +     ans += sub(H, W - l - r);
           51  +   }
           52  +  return ans.val;
           53  + }
           54  +
           55  + mint sub(LL H, LL W)
           56  + {
           57  +  // columns = _?????_
           58  +  mint f = POW(2, W - 2);
           59  +
           60  +  // Diag: H+W-1個のうち
           61  +  // 最初H個のどれかはmust空き
           62  +  // 最後H個のどれかはmust空き
           63  +  // 他でH連続塗りがある場合は縦の自由度が減る /2
           64  +  vector<mint> dp(H+1);
           65  +  dp[0] = f;
           66  +  for (int i = 0; i < H + W - 1; ++i) {
           67  +   vector<mint> dp_prev = dp;
           68  +   vector<mint> dp(H+1);
           69  +   for (int r = 0; r <= H; ++r) {
           70  +    if (r == 0) {
           71  +     accumulate(dp_prev.begin(), dp_prev.end(), mint(0));
           72  +    }
           73  +    else {
           74  +     if(r == H)
           75  +      dp[r] = (i == H - 1 || i == H + W - 2 ? mint(0) : (dp_prev[r - 1]+ dp_prev[r]) / 2);
           76  +     else
           77  +      dp[r] = dp_prev[r - 1];
           78  +    }
           79  +   }
           80  +  }
           81  +  return accumulate(dp.begin(), dp.begin() + H, mint(0));
           82  + }
           83  +};
           84  +
           85  +// BEGIN CUT HERE
           86  +#include <ctime>
           87  +double start_time; string timer()
           88  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           89  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           90  + { os << "{ ";
           91  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           92  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           93  +void verify_case(const int& Expected, const int& Received) {
           94  + bool ok = (Expected == Received);
           95  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           96  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           97  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           98  +#define END  verify_case(_, DiagonalColumn().countGrids(H, W));}
           99  +int main(){
          100  +
          101  +CASE(0)
          102  + int H = 2;
          103  + int W = 2;
          104  + int _ = 12;
          105  +END
          106  +CASE(1)
          107  + int H = 2;
          108  + int W = 3;
          109  + int _ = 37;
          110  +END
          111  +CASE(2)
          112  + int H = 3;
          113  + int W = 2;
          114  + int _ = 28;
          115  +END
          116  +CASE(3)
          117  + int H = 1;
          118  + int W = 5;
          119  + int _ = 32;
          120  +END
          121  +CASE(4)
          122  + int H = 6;
          123  + int W = 1;
          124  + int _ = 64;
          125  +END
          126  +CASE(5)
          127  + int H = 38;
          128  + int W = 38;
          129  + int _ = 173889321;
          130  +END
          131  +/*
          132  +CASE(6)
          133  + int H = ;
          134  + int W = ;
          135  + int _ = ;
          136  +END
          137  +CASE(7)
          138  + int H = ;
          139  + int W = ;
          140  + int _ = ;
          141  +END
          142  +*/
          143  +}
          144  +// END CUT HERE