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

Added SRM/TCO11-3/1A.cpp version [7c3fa8bfe90815c9]

            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  +int gcd(int x, int y)
           23  +{
           24  + while(x)
           25  +  swap(x, y%=x);
           26  + return y;
           27  +}
           28  +
           29  +int lcm(int x, int y)
           30  +{
           31  + return x/gcd(x,y)*y;
           32  +}
           33  +
           34  +class ArtShift { public:
           35  + int maxShifts(string sequence)
           36  + {
           37  +  int B=0, W=0;
           38  +  for(int i=0; i<sequence.size(); ++i)
           39  +   (sequence[i]=='B' ? B : W)++;
           40  +  memo.assign(31*31, set<int>());
           41  +  for(int b=0; b<=B; ++b) memo[b*31+0].insert(1);
           42  +  for(int w=0; w<=W; ++w) memo[0*31+w].insert(1);
           43  +  return *rec(B,W).rbegin();
           44  + }
           45  +
           46  + vector< set<int> > memo;
           47  + const set<int>& rec(int B, int W)
           48  + {
           49  +  set<int>& result = memo[B*31+W];
           50  +  if( !result.empty() )
           51  +   return result;
           52  +
           53  +  result.insert(B+W);
           54  +  for(int b= 0; b<=B; ++b)
           55  +  for(int w=!b; w<=W; ++w) {
           56  +   const set<int>& x = rec(b,w);
           57  +   const set<int>& y = rec(B-b,W-w);
           58  +   for(set<int>::const_iterator it=x.begin(); it!=x.end(); ++it)
           59  +   for(set<int>::const_iterator jt=y.begin(); jt!=y.end(); ++jt)
           60  +    result.insert(lcm(*it,*jt));
           61  +  }
           62  +  return result;
           63  + }
           64  +};
           65  +
           66  +// BEGIN CUT HERE
           67  +#include <ctime>
           68  +double start_time; string timer()
           69  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           70  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           71  + { os << "{ ";
           72  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           73  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           74  +void verify_case(const int& Expected, const int& Received) {
           75  + bool ok = (Expected == Received);
           76  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           77  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           78  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           79  +#define END  verify_case(_, ArtShift().maxShifts(sequence));}
           80  +int main(){
           81  +
           82  +CASE(0)
           83  + string sequence = "BW";
           84  + int _ = 2;
           85  +END
           86  +CASE(1)
           87  + string sequence = "BBBWBBB";
           88  + int _ = 7;
           89  +END
           90  +CASE(2)
           91  + string sequence = "BWBWB";
           92  + int _ = 6;
           93  +END
           94  +CASE(3)
           95  + string sequence = "WWWWWWWWW";
           96  + int _ = 1;
           97  +END
           98  +CASE(4)
           99  + string sequence = "WWWWWWWWWBBWB";
          100  + int _ = 60;
          101  +END
          102  +CASE(5)
          103  + string sequence = "W";
          104  + int _ = 1;
          105  +END
          106  +CASE(6)
          107  + string sequence = "B";
          108  + int _ = 1;
          109  +END
          110  +CASE(7)
          111  + string sequence = "BB";
          112  + int _ = 1;
          113  +END
          114  +CASE(8)
          115  + string sequence = "BWBWBWBWBWBWBWBWBWBWBWBWBWBWBW";
          116  + int _ = -1;
          117  +END
          118  +
          119  +}
          120  +// END CUT HERE

Added SRM/TCO11-3/1B.cpp version [b1fd16df13023b5a]

            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 PrefixFreeSuperset { public:
           23  + long long minSumLength(vector <string> cur, long long k)
           24  + {
           25  +  map<int,LL> open; {
           26  +   string me("");
           27  +   rec(me, cur, open);
           28  +  }
           29  +
           30  +  LL totalLen = 0;
           31  +  for(int i=0; i<cur.size(); ++i)
           32  +   totalLen += cur[i].size();
           33  +  k -= cur.size();
           34  +
           35  +  while(k) {
           36  +   if( open.empty() )
           37  +    return -1;
           38  +   map<int,LL>::iterator it = open.begin();
           39  +   int lll = it->first;
           40  +   LL  ccc = it->second;
           41  +   open.erase(it);
           42  +
           43  +   if( k <= ccc ) {
           44  +    totalLen += lll*k;
           45  +    k         = 0;
           46  +   }
           47  +   else if( k <= ccc + open[lll+1] ) {
           48  +    totalLen += lll*ccc;
           49  +    k        -= ccc;
           50  +   }
           51  +   else if( k <= ccc*2 + open[lll+1] ) {
           52  +    LL div = k - (ccc+open[lll+1]);
           53  +    open[lll+1] += div*2;
           54  +    totalLen += (ccc-div)*lll;
           55  +    k        -= (ccc-div);
           56  +   }
           57  +   else
           58  +    open[lll+1] += ccc*2;
           59  +  }
           60  +  return totalLen;
           61  + }
           62  +
           63  + void rec(string& me, const vector<string>& prefix, map<int,LL>& open)
           64  + {
           65  +  bool iamprefix = false;
           66  +  for(int i=0; i<prefix.size(); ++i)
           67  +   if( me == prefix[i] )
           68  +    return;
           69  +   else if( is_prefix(me, prefix[i]) )
           70  +    iamprefix = true;
           71  +  if( iamprefix )
           72  +  {
           73  +   me += '0';
           74  +   rec(me, prefix, open);
           75  +   me.resize(me.size()-1);
           76  +   me += '1';
           77  +   rec(me, prefix, open);
           78  +   me.resize(me.size()-1);
           79  +  }
           80  +  else
           81  +  {
           82  +   open[me.size()] ++;
           83  +  }
           84  + }
           85  +
           86  + bool is_prefix(const string& s, const string& t)
           87  + {
           88  +  return s.size()<=t.size() && s==t.substr(0,s.size());
           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(_, PrefixFreeSuperset().minSumLength(cur, k));}
          106  +int main(){
          107  +
          108  +CASE(0)
          109  + string cur_[] = {"010"};
          110  +   vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
          111  + long long k = 4LL;
          112  + long long _ = 9LL;
          113  +END
          114  +CASE(1)
          115  + string cur_[] = {"01","000"};
          116  +   vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
          117  + long long k = 4LL;
          118  + long long _ = 9LL;
          119  +END
          120  +CASE(2)
          121  + string cur_[] = {"0011","011110101","11101010111","11101010100000000","11101010100000001111"};
          122  +   vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
          123  + long long k = 1000000000000LL;
          124  + long long _ = 39971901640560LL;
          125  +END
          126  +CASE(3)
          127  + string cur_[] = {"010","00","011","1"};
          128  +   vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
          129  + long long k = 4LL;
          130  + long long _ = 9LL;
          131  +END
          132  +CASE(4)
          133  + string cur_[] = {"010","00","011","1"};
          134  +   vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
          135  + long long k = 5LL;
          136  + long long _ = -1LL;
          137  +END
          138  +CASE(5)
          139  + string cur_[] = {"0011010",
          140  +"0011011110",
          141  +"00110111001",
          142  +"0011011111",
          143  +"00110111000",
          144  +};
          145  +   vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
          146  + long long k = 9LL;
          147  + long long _ = 58LL;
          148  +END
          149  +/*
          150  +CASE(6)
          151  + string cur_[] = ;
          152  +   vector <string> cur(cur_, cur_+sizeof(cur_)/sizeof(*cur_));
          153  + long long k = LL;
          154  + long long _ = LL;
          155  +END
          156  +*/
          157  +}
          158  +// END CUT HERE

Added SRM/TCO11-3/1C.cpp version [bb93038d2c81fe7f]

            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 DP3x
           24  +{
           25  + int N1, N2, N3;
           26  + vector<T> data;
           27  + DP3x(int, int N2, int N3, const T& t = T())
           28  +  : N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T) < (1<<26)); }
           29  + T& operator()(int i1, int i2, int i3)
           30  +  { i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; }
           31  +};
           32  +
           33  +static const int MODVAL = 1000000007;
           34  +
           35  +class RowOfColors { public:
           36  + int countWays(int w, int h, int k)
           37  + {
           38  +  DP3x<LL> dp(w+1, h+1, k+1);
           39  +  for(int i=w; i>=0; --i)
           40  +  for(int stack=0; stack<=h; ++stack)
           41  +  for(int used =0; used <=k; ++used)
           42  +   if( i == w )
           43  +    dp(i,stack,used) = (stack==1 && used==k ? 1 : 0);
           44  +   else {
           45  +    LL cnt = 0;
           46  +    if(stack+1<=h && used+1<=k) // push new color
           47  +     cnt += dp(i+1,stack+1,used+1);
           48  +    if(stack) // continue the same color
           49  +     cnt += dp(i+1,stack,used);
           50  +    if(stack && used+1<=k) // replace top
           51  +     cnt += dp(i+1,stack,used+1);
           52  +    if(stack>=2) // pop
           53  +     cnt += dp(i+1,stack-1,used);
           54  +    dp(i,stack,used) = cnt % MODVAL;
           55  +   }
           56  +  LL v = dp(0,0,0);
           57  +  for(int i=1; i<=k; ++i)
           58  +   v = (v*i) % MODVAL;
           59  +  return int(v);
           60  + }
           61  +};
           62  +
           63  +// BEGIN CUT HERE
           64  +#include <ctime>
           65  +double start_time; string timer()
           66  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           67  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           68  + { os << "{ ";
           69  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           70  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           71  +void verify_case(const int& Expected, const int& Received) {
           72  + bool ok = (Expected == Received);
           73  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           74  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           75  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           76  +#define END  verify_case(_, RowOfColors().countWays(w, h, k));}
           77  +int main(){
           78  +
           79  +CASE(0)
           80  + int w = 4;
           81  + int h = 1;
           82  + int k = 2;
           83  + int _ = 6;
           84  +END
           85  +CASE(1)
           86  + int w = 4;
           87  + int h = 3;
           88  + int k = 2;
           89  + int _ = 12;
           90  +END
           91  +CASE(2)
           92  + int w = 4;
           93  + int h = 4;
           94  + int k = 10;
           95  + int _ = 0;
           96  +END
           97  +CASE(3)
           98  + int w = 14;
           99  + int h = 28;
          100  + int k = 14;
          101  + int _ = 178290591;
          102  +END
          103  +/*
          104  +CASE(4)
          105  + int w = ;
          106  + int h = ;
          107  + int k = ;
          108  + int _ = ;
          109  +END
          110  +CASE(5)
          111  + int w = ;
          112  + int h = ;
          113  + int k = ;
          114  + int _ = ;
          115  +END
          116  +*/
          117  +}
          118  +// END CUT HERE