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

Added SRM/TCO13-3B-U/1A.cpp version [b54e51e3de8ee5c7]

            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<double> CMP;
           21  +
           22  +const int ANY = 0;
           23  +
           24  +static const unsigned MODVAL = 1000000009;
           25  +struct mint
           26  +{
           27  + unsigned val;
           28  + mint():val(0){}
           29  + mint(int      x):val(x%MODVAL) {}
           30  + mint(unsigned x):val(x%MODVAL) {}
           31  + mint(LL       x):val(x%MODVAL) {}
           32  +};
           33  +mint& operator+=(mint& x, mint y) { return x = x.val+y.val; }
           34  +mint& operator-=(mint& x, mint y) { return x = x.val-y.val+MODVAL; }
           35  +mint& operator*=(mint& x, mint y) { return x = LL(x.val)*y.val; }
           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  +
           40  +class SimilarSequences { public:
           41  + int count(vector <int> seq, int bound)
           42  + {
           43  +  vector< vector<int> > cand;
           44  +  cand.push_back(seq);
           45  +  for(int i=0; i<seq.size(); ++i)
           46  +  {
           47  +   vector<int> s = seq;
           48  +   s.erase(s.begin() + i);
           49  +   s.push_back(ANY);
           50  +   cand.push_back(s);
           51  +   for(int w=s.size()-1; w>0; --w) {
           52  +    swap(s[w], s[w-1]);
           53  +    cand.push_back(s);
           54  +   }
           55  +  }
           56  +  vector<int> idx;
           57  +  for(int i=0; i<cand.size(); ++i)
           58  +   idx.push_back(i);
           59  +  return rec(0, cand, idx, bound).val;
           60  + }
           61  +
           62  + mint rec(int I, const vector<vector<int> >& cand, const vector<int>& idx, int B)
           63  + {
           64  +  if(idx.empty())
           65  +   return 0;
           66  +  if(I == cand[0].size())
           67  +   return 1;
           68  +
           69  +  mint total = 0;
           70  +
           71  +  set<int> head;
           72  +  for(int k=0; k<idx.size(); ++k)
           73  +   if( cand[idx[k]][I] != ANY )
           74  +    head.insert(cand[idx[k]][I]);
           75  +  // Use an existing value.
           76  +  for(set<int>::iterator it=head.begin(); it!=head.end(); ++it)
           77  +  {
           78  +   int h = *it;
           79  +   vector<int> idx2;
           80  +   for(int k=0; k<idx.size(); ++k)
           81  +    if(cand[idx[k]][I]==ANY || cand[idx[k]][I]==h)
           82  +     idx2.push_back(idx[k]);
           83  +   total += rec(I+1, cand, idx2, B);
           84  +  }
           85  +
           86  +  // Use nonexisting.
           87  +  if(B > head.size()) {
           88  +   vector<int> idx2;
           89  +   for(int k=0; k<idx.size(); ++k)
           90  +    if(cand[idx[k]][I]==ANY)
           91  +     idx2.push_back(idx[k]);
           92  +   total += rec(I+1, cand, idx2, B) * (B - head.size());
           93  +  }
           94  +
           95  +  return total;
           96  + }
           97  +};
           98  +
           99  +// BEGIN CUT HERE
          100  +#include <ctime>
          101  +double start_time; string timer()
          102  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          103  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          104  + { os << "{ ";
          105  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          106  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          107  +void verify_case(const int& Expected, const int& Received) {
          108  + bool ok = (Expected == Received);
          109  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          110  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          111  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          112  +#define END  verify_case(_, SimilarSequences().count(seq, bound));}
          113  +int main(){
          114  +
          115  +CASE(0)
          116  + int seq_[] = {1, 1};
          117  +   vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
          118  + int bound = 3;
          119  + int _ = 5;
          120  +END
          121  +CASE(1)
          122  + int seq_[] = {1, 2};
          123  +   vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
          124  + int bound = 2;
          125  + int _ = 4;
          126  +END
          127  +CASE(2)
          128  + int seq_[] = {999999999};
          129  +   vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
          130  + int bound = 1000000000;
          131  + int _ = 1000000000;
          132  +END
          133  +CASE(3)
          134  + int seq_[] = {1, 2, 3, 4, 5};
          135  +   vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
          136  + int bound = 5;
          137  + int _ = 97;
          138  +END
          139  +CASE(4)
          140  + int seq_[] = {5, 8, 11, 12, 4, 1, 7, 9};
          141  +   vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
          142  + int bound = 1000000000;
          143  + int _ = 999999363;
          144  +END
          145  +/*
          146  +CASE(5)
          147  + int seq_[] = ;
          148  +   vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
          149  + int bound = ;
          150  + int _ = ;
          151  +END
          152  +CASE(6)
          153  + int seq_[] = ;
          154  +   vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
          155  + int bound = ;
          156  + int _ = ;
          157  +END
          158  +*/
          159  +}
          160  +// END CUT HERE

Added SRM/TCO13-3B-U/1B.cpp version [00e49509bf66508d]

            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<double> CMP;
           21  +
           22  +static const int INF = 999, UNK = -1;
           23  +
           24  +int bitcnt(int x)
           25  +{
           26  + int c = 0;
           27  + for(; x; x>>=1)
           28  +  c += x&1;
           29  + return c;
           30  +}
           31  +
           32  +class AntlerSwapping { public:
           33  + int getmin(vector <int> a, vector <int> b, int capacity)
           34  + {
           35  +  int N = a.size();
           36  +  vector<bool> tbl(1<<N);
           37  +  for(int mask=1; mask<(1<<N); ++mask)
           38  +  {
           39  +   vector<int> c;
           40  +   for(int i=0; (1<<i)<=mask; ++i)
           41  +    if((1<<i) & mask) {
           42  +     c.push_back(a[i]);
           43  +     c.push_back(b[i]);
           44  +    }
           45  +   sort(c.begin(), c.end());
           46  +   bool can = true;
           47  +   for(int i=0; i+1<c.size(); i+=2)
           48  +    if(abs(c[i]-c[i+1]) > capacity)
           49  +     can = false;
           50  +   tbl[mask] = can;
           51  +  }
           52  +  vector<int> memo(1<<N, UNK);
           53  +  int best = rec((1<<N)-1, tbl, memo);
           54  +  return best>=INF ? -1 : best;
           55  + }
           56  +
           57  + int rec(int mask, const vector<bool>& tbl, vector<int>& memo)
           58  + {
           59  +  if(memo[mask] != UNK)
           60  +   return memo[mask];
           61  +  if(mask == 0)
           62  +   return 0;
           63  +  int best = INF;
           64  +  for(int m2=mask; m2; m2=(m2-1)&mask)
           65  +  {
           66  +   int bc = bitcnt(m2);
           67  +   if(tbl[m2])
           68  +    best = min(best, (bc-1) + rec(mask&~m2, tbl, memo));
           69  +  }
           70  +  return memo[mask] = best;
           71  + }
           72  +};
           73  +
           74  +// BEGIN CUT HERE
           75  +#include <ctime>
           76  +double start_time; string timer()
           77  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           78  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           79  + { os << "{ ";
           80  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           81  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           82  +void verify_case(const int& Expected, const int& Received) {
           83  + bool ok = (Expected == Received);
           84  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           85  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           86  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           87  +#define END  verify_case(_, AntlerSwapping().getmin(antler1, antler2, capacity));}
           88  +int main(){
           89  +
           90  +CASE(0)
           91  + int antler1_[] = {3, 2, 2};
           92  +   vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_));
           93  + int antler2_[] = {3, 5, 5};
           94  +   vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_));
           95  + int capacity = 0;
           96  + int _ = 1;
           97  +END
           98  +CASE(1)
           99  + int antler1_[] = {4, 2, 6, 4, 8, 5, 2, 3};
          100  +   vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_));
          101  + int antler2_[] = {3, 4, 5, 2, 8, 5, 7, 6};
          102  +   vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_));
          103  + int capacity = 1;
          104  + int _ = 2;
          105  +END
          106  +CASE(2)
          107  + int antler1_[] = {12, 34, 56, 78};
          108  +   vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_));
          109  + int antler2_[] = {1234, 2345, 3456, 4567};
          110  +   vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_));
          111  + int capacity = 100;
          112  + int _ = -1;
          113  +END
          114  +CASE(3)
          115  + int antler1_[] = {47, 58, 2013};
          116  +   vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_));
          117  + int antler2_[] = {49, 55, 2013};
          118  +   vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_));
          119  + int capacity = 3;
          120  + int _ = 0;
          121  +END
          122  +CASE(4)
          123  + int antler1_[] = {4, 1, 7, 5, 7, 8, 2, 1, 3, 1, 7, 5, 9, 4, 9, 1};
          124  +   vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_));
          125  + int antler2_[] = {10, 6, 5, 3, 1, 8, 4, 4, 4, 7, 1, 4, 6, 5, 10, 10};
          126  +   vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_));
          127  + int capacity = 1;
          128  + int _ = 7;
          129  +END
          130  +/*
          131  +CASE(5)
          132  + int antler1_[] = ;
          133  +   vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_));
          134  + int antler2_[] = ;
          135  +   vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_));
          136  + int capacity = ;
          137  + int _ = ;
          138  +END
          139  +CASE(6)
          140  + int antler1_[] = ;
          141  +   vector <int> antler1(antler1_, antler1_+sizeof(antler1_)/sizeof(*antler1_));
          142  + int antler2_[] = ;
          143  +   vector <int> antler2(antler2_, antler2_+sizeof(antler2_)/sizeof(*antler2_));
          144  + int capacity = ;
          145  + int _ = ;
          146  +END
          147  +*/
          148  +}
          149  +// END CUT HERE