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

Added SRM/TCO12-3B-U/1A.cpp version [8cb659246b1c63d7]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +class CrossingTheRiver { public:
           23  + string isItEvenPossible(int waterWidth, int landWidth, vector <int> blockHeight, int depth)
           24  + {
           25  +  return solve(waterWidth, landWidth, blockHeight, depth) ? "POSSIBLE" : "IMPOSSIBLE";
           26  + }
           27  +
           28  + bool solve(int WW, int LW, vector<int> B, int D)
           29  + {
           30  +  if( count(B.begin(), B.end(), D) >= WW )
           31  +   return true;
           32  +
           33  +  sort(B.begin(), B.end());
           34  +  for(int lastW=D;       lastW<=D+WW;       ++lastW)
           35  +  for(int lastL=lastW-D; lastL<=lastW-D+LW; ++lastL)
           36  +   if( solve2(B, WW, D, lastW, LW, lastW-D, lastL) )
           37  +    return true;
           38  +  return false;
           39  + }
           40  +
           41  + bool solve2(vector<int> B, int WW, int W_min, int W_max, int LW, int L_min, int L_max)
           42  + {
           43  +  for(int h=W_min+1; h<=W_max; ++h,--WW)
           44  +   if(!erase(B, h))
           45  +    return false;
           46  +  for(int h=L_min+1; h<=L_max; ++h,--LW)
           47  +   if(!erase(B, h))
           48  +    return false;
           49  +
           50  +  int both = 0;
           51  +  for(int i=0; i<B.size(); ++i)
           52  +   if( W_min<=B[i] && B[i]<=W_max && L_min<=B[i] && B[i]<=L_max )
           53  +    both++;
           54  +   else if( W_min<=B[i] && B[i]<=W_max )
           55  +    --WW;
           56  +   else if( L_min<=B[i] && B[i]<=L_max )
           57  +    --LW;
           58  +  return (max(WW,0)+max(LW,0) <= both);
           59  + }
           60  +
           61  + bool erase(vector<int>& v, int n)
           62  + {
           63  +  vector<int>::iterator it = find(v.begin(), v.end(), n);
           64  +  if( it == v.end() )
           65  +   return false;
           66  +  v.erase(it);
           67  +  return true;
           68  + }
           69  +};
           70  +
           71  +// BEGIN CUT HERE
           72  +#include <ctime>
           73  +double start_time; string timer()
           74  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           75  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           76  + { os << "{ ";
           77  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           78  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           79  +void verify_case(const string& Expected, const string& Received) {
           80  + bool ok = (Expected == Received);
           81  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           82  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           83  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           84  +#define END  verify_case(_, CrossingTheRiver().isItEvenPossible(waterWidth, landWidth, blockHeight, depth));}
           85  +int main(){
           86  +
           87  +CASE(0)
           88  + int waterWidth = 3;
           89  + int landWidth = 3;
           90  + int blockHeight_[] = {3,4,4,5,5, 6};
           91  +   vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight_)/sizeof(*blockHeight_));
           92  + int depth = 2;
           93  + string _ = "POSSIBLE";
           94  +END
           95  +CASE(1)
           96  + int waterWidth = 3;
           97  + int landWidth = 3;
           98  + int blockHeight_[] = {3,4,4,5,6, 6};
           99  +   vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight_)/sizeof(*blockHeight_));
          100  + int depth = 2;
          101  + string _ = "IMPOSSIBLE";
          102  +END
          103  +CASE(2)
          104  + int waterWidth = 5;
          105  + int landWidth = 2;
          106  + int blockHeight_[] = {4,4,4,4,4};
          107  +   vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight_)/sizeof(*blockHeight_));
          108  + int depth = 4;
          109  + string _ = "POSSIBLE";
          110  +END
          111  +CASE(3)
          112  + int waterWidth = 5;
          113  + int landWidth = 5;
          114  + int blockHeight_[] = {5,5,5,5,5,5, 2,3,4,4,6, 7, 3, 2};
          115  +   vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight_)/sizeof(*blockHeight_));
          116  + int depth = 2;
          117  + string _ = "POSSIBLE";
          118  +END
          119  +CASE(4)
          120  + int waterWidth = 5;
          121  + int landWidth = 7;
          122  + int blockHeight_[] = {6,6,6,6,6,6,6, 6,6,6,6,6,7,8,9,10};
          123  +   vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight_)/sizeof(*blockHeight_));
          124  + int depth = 5;
          125  + string _ = "POSSIBLE";
          126  +END
          127  +CASE(5)
          128  + int waterWidth = 1;
          129  + int landWidth = 1;
          130  + int blockHeight_[] = {5,3,4};
          131  +   vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight_)/sizeof(*blockHeight_));
          132  + int depth = 2;
          133  + string _ = "IMPOSSIBLE";
          134  +END
          135  +CASE(6)
          136  + int waterWidth = 3;
          137  + int landWidth = 1;
          138  + int blockHeight_[] = {2, 3, 4, 5};
          139  +   vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight_)/sizeof(*blockHeight_));
          140  + int depth = 2;
          141  + string _ = "IMPOSSIBLE";
          142  +END
          143  +/*
          144  +CASE(7)
          145  + int waterWidth = ;
          146  + int landWidth = ;
          147  + int blockHeight_[] = ;
          148  +   vector <int> blockHeight(blockHeight_, blockHeight_+sizeof(blockHeight_)/sizeof(*blockHeight_));
          149  + int depth = ;
          150  + string _ = ;
          151  +END
          152  +*/
          153  +}
          154  +// END CUT HERE

Added SRM/TCO12-3B-U/1B-U.cpp version [c64847afba8ca911]

            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  +using namespace std;
           18  +typedef long long LL;
           19  +typedef long double LD;
           20  +typedef complex<LD> CMP;
           21  +
           22  +static const int MODVAL = 1000000007;
           23  +struct mint
           24  +{
           25  + int val;
           26  + mint():val(0){}
           27  + mint(int    x):val(x%MODVAL) {}
           28  + mint(size_t 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 POW(mint x, LL e) { mint v=1; for(;e;x*=x,e>>=1) if(e&1) v*=x; return v; }
           35  +mint& operator/=(mint& x, mint y) { return x *= POW(y, MODVAL-2); }
           36  +mint operator+(mint x, mint y) { return x+=y; }
           37  +mint operator-(mint x, mint y) { return x-=y; }
           38  +mint operator*(mint x, mint y) { return x*=y; }
           39  +mint operator/(mint x, mint y) { return x/=y; }
           40  +vector<mint> FAC_(1,1);
           41  +mint FAC(LL n) { while( FAC_.size()<=n ) FAC_.push_back( FAC_.back()*FAC_.size() ); return FAC_[n]; }
           42  +vector< vector<mint> > CP_; // Pascal's triangle: if O(1) nCk is needed.
           43  +mint C(LL n, LL k) {
           44  + while( CP_.size() <= n ) {
           45  +  int nn = CP_.size();
           46  +  CP_.push_back(vector<mint>(nn+1,1));
           47  +  for(int kk=1; kk<nn; ++kk)
           48  +   CP_[nn][kk] = CP_[nn-1][kk-1] + CP_[nn-1][kk];
           49  + }
           50  + return k<0 || n<k ? 0 : CP_[n][k];
           51  +}
           52  +
           53  +template<typename T>
           54  +struct DP3
           55  +{
           56  + int N1, N2, N3;
           57  + vector<T> data;
           58  + DP3(int N1, int N2, int N3, const T& t = T())
           59  +  : N1(N1), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T)<(1<<26)); }
           60  + T& operator()(int i1, int i2, int i3)
           61  +  { return data[ ((i1*N2)+i2)*N3+i3 ]; }
           62  + void swap(DP3& rhs)
           63  +  { data.swap(rhs.data); }
           64  +};
           65  +
           66  +class ElevenMultiples { public:
           67  + // (10^p)%11
           68  + int rem11(int p)
           69  + {
           70  +  return p%2==0 ? 1 : 10;
           71  + }
           72  +
           73  + int countMultiples(vector <string> pieces)
           74  + {
           75  +  vector<int> es, os;
           76  +  for(int i=0; i<pieces.size(); ++i) {
           77  +   int r = 0;
           78  +   for(int k=0; k<pieces[i].size(); ++k)
           79  +    r = (r + (pieces[i][k]-'0')*rem11(k)) % 11;
           80  +   (pieces.size()%2==0 ? es : os).push_back(r);
           81  +  }
           82  +  return solve(es, os).val;
           83  + }
           84  +
           85  + mint solve(const vector<int>& es, const vector<int>& os)
           86  + {
           87  +  DP3<mint> dpE(es.size(), 11, es.size()+1);
           88  +  int rE = accumulate(es.begin(), es.end(), 0) % 11;
           89  +  for(int i=0; i<es.size(); ++i)
           90  +  for(int r=0; r<11; ++r)
           91  +  for(int n=0; n<=es.size(); ++n)
           92  +  {
           93  +   int v = es[i];
           94  +   if(i==0) {
           95  +    if(r==0 && n==0 || r==v && n==1)
           96  +     dpE(i,r,n) = 1;
           97  +   } else {
           98  +    if(n>0)
           99  +     dpE(i,r,n) = dpE(i-1,r,n) + dpE(i-1, (r-v+11)%11, n-1);
          100  +    else
          101  +     dpE(i,r,n) = dpE(i-1,r,n);
          102  +   }
          103  +  }
          104  +  DP3<mint> dpO(os.size(), 11, os.size()+1);
          105  +  int rO = accumulate(os.begin(), os.end(), 0) % 11;
          106  +  for(int i=0; i<os.size(); ++i)
          107  +  for(int r=0; r<11; ++r)
          108  +  for(int n=0; n<=os.size(); ++n)
          109  +  {
          110  +   int v = os[i];
          111  +   if(i==0) {
          112  +    if(r==0 && n==0 || r==v && n==1)
          113  +     dpO(i,r,n) = 1;
          114  +   } else {
          115  +    if(n>0)
          116  +     dpO(i,r,n) = dpO(i-1,r,n) + dpO(i-1, (r-v+11)%11, n-1);
          117  +    else
          118  +     dpO(i,r,n) = dpO(i-1,r,n);
          119  +   }
          120  +  }
          121  +
          122  +  mint total = 0;
          123  +  for(int re=0; re<11; ++re)
          124  +  for(int ne=0; ne<=es.size(); ++ne)
          125  +  for(int ro=0; ro<11; ++ro)
          126  +  for(int no=0; no<=os.size(); ++no)
          127  +  {
          128  +   int re2 = (rE - re + 11)*10%11;
          129  +   int ne2 = es.size() - ne;
          130  +   int ro2 = (rO - ro + 11)*10%11;
          131  +   int no2 = os.size() - no;
          132  +   if((re + re2 + ro + ro2)%11 == 0)
          133  +   if( ne2+no2==0 || no>0 )
          134  +   if(no==no2 || no==no2+1) {
          135  +    mint choice = (es.empty() ? re==0?1:0 : dpE(es.size()-1, re, ne))
          136  +     * (os.empty() ? ro==0?1:0 : dpO(os.size()-1, ro, no));
          137  +    total += choice * cnt(ne, ne2, no, no2);
          138  +   }
          139  +  }
          140  +  return total;
          141  + }
          142  +
          143  + mint cnt(int ne, int ne2, int no, int no2)
          144  + {
          145  +  mint x = FAC(no) * FAC(no2);
          146  +  int nec = (no==no2 ? no+1 : no);
          147  +  int ne2c = no;
          148  +  return x * dist(nec, ne) * dist(ne2c, ne2);
          149  + }
          150  +
          151  + mint dist(int n, int k)
          152  + {
          153  +  return FAC(n) * C(n+k-1, k-1);
          154  + }
          155  +};
          156  +
          157  +// BEGIN CUT HERE
          158  +#include <ctime>
          159  +double start_time; string timer()
          160  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          161  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          162  + { os << "{ ";
          163  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          164  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          165  +void verify_case(const int& Expected, const int& Received) {
          166  + bool ok = (Expected == Received);
          167  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          168  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          169  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          170  +#define END  verify_case(_, ElevenMultiples().countMultiples(pieces));}
          171  +int main(){
          172  +
          173  +CASE(0)
          174  + string pieces_[] = {"58", "2012", "123"};
          175  +   vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
          176  + int _ = 2;
          177  +END
          178  +CASE(1)
          179  + string pieces_[] = {"1", "1111", "1", "11"};
          180  +   vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
          181  + int _ = 24;
          182  +END
          183  +CASE(2)
          184  + string pieces_[] = {"43925486943738659795389387498953274"};
          185  +   vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
          186  + int _ = 1;
          187  +END
          188  +CASE(3)
          189  + string pieces_[] = {"983", "4654", "98", "3269", "861", "30981"};
          190  +   vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
          191  + int _ = 96;
          192  +END
          193  +CASE(4)
          194  + string pieces_[] = {"193", "8819", "40676", "97625892", "5719", "45515667", "32598836", "70559374", "38756", "724",
          195  +"93391", "942068", "506", "901150", "874", "895567", "7560480", "7427691", "799450", "85127"};
          196  +   vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
          197  + int _ = 537147821;
          198  +END
          199  +CASE(5)
          200  + string pieces_[] = {"687045939630", "997856158148599044", "2014910234712225061", "9658113323175370226", "1584118137",
          201  +"67925153345598920", "6960366756", "863413844386808834", "799302243562410012", "44481835751",
          202  +"8004606814733183", "19623906615609", "23859998326058162", "461385591582", "9261878982390119",
          203  +"1569373294276", "318106951168934", "65389049931", "12791173342", "507877942026",
          204  +"3947173045690", "472425746178910", "524552931853595", "40771812249667850232", "563988469071932",
          205  +"28147819070", "797007158858587", "5716177008624223", "387565700495309324", "4716621063133318"}
          206  +;
          207  +   vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
          208  + int _ = 814880650;
          209  +END
          210  +/*
          211  +CASE(6)
          212  + string pieces_[] = ;
          213  +   vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
          214  + int _ = ;
          215  +END
          216  +CASE(7)
          217  + string pieces_[] = ;
          218  +   vector <string> pieces(pieces_, pieces_+sizeof(pieces_)/sizeof(*pieces_));
          219  + int _ = ;
          220  +END
          221  +*/
          222  +}
          223  +// END CUT HERE