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

Added SRM/659-U/1A.cpp version [6cad379ca924cee7]

            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 ApplesAndOrangesEasy { public:
           23  + int maximumApples(int N, int K, vector <int> info)
           24  + {
           25  +  vector<bool> ate_apple(N, false);
           26  +  for(auto i: info)
           27  +   ate_apple[i-1] = true;
           28  +  for(int i=0; i<N; ++i)
           29  +   if(!ate_apple[i]) {
           30  +    ate_apple[i] = true;
           31  +    if(!ok(N,K,ate_apple))
           32  +     ate_apple[i] = false;
           33  +   }
           34  +  return count(ate_apple.begin(), ate_apple.end(), true);
           35  + }
           36  +
           37  + bool ok(int N, int K, const vector<bool>& A)
           38  + {
           39  +  int cnt = 0;
           40  +  for(int i=0; i<N; ++i) {
           41  +   if(A[i]) cnt++;
           42  +   if(i-K>=0 && A[i-K]) cnt--;
           43  +   if(cnt>K/2)
           44  +    return false;
           45  +  }
           46  +  return true;
           47  + }
           48  +};
           49  +
           50  +// BEGIN CUT HERE
           51  +#include <ctime>
           52  +double start_time; string timer()
           53  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           54  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           55  + { os << "{ ";
           56  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           57  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           58  +void verify_case(const int& Expected, const int& Received) {
           59  + bool ok = (Expected == Received);
           60  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           61  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           62  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           63  +#define END  verify_case(_, ApplesAndOrangesEasy().maximumApples(N, K, info));}
           64  +int main(){
           65  +
           66  +CASE(0)
           67  + int N = 3;
           68  + int K = 2;
           69  + vector <int> info;
           70  + int _ = 2;
           71  +END
           72  +CASE(1)
           73  + int N = 10;
           74  + int K = 3;
           75  + int info_[] = {3, 8};
           76  +   vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_));
           77  + int _ = 2;
           78  +END
           79  +CASE(2)
           80  + int N = 9;
           81  + int K = 4;
           82  + int info_[] = {1, 4};
           83  +   vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_));
           84  + int _ = 5;
           85  +END
           86  +CASE(3)
           87  + int N = 9;
           88  + int K = 4;
           89  + int info_[] = {2, 4};
           90  +   vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_));
           91  + int _ = 4;
           92  +END
           93  +CASE(4)
           94  + int N = 23;
           95  + int K = 7;
           96  + int info_[] = {3, 2, 9, 1, 15, 23, 20, 19};
           97  +   vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_));
           98  + int _ = 10;
           99  +END
          100  +/*
          101  +CASE(5)
          102  + int N = ;
          103  + int K = ;
          104  + int info_[] = ;
          105  +   vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_));
          106  + int _ = ;
          107  +END
          108  +CASE(6)
          109  + int N = ;
          110  + int K = ;
          111  + int info_[] = ;
          112  +   vector <int> info(info_, info_+sizeof(info_)/sizeof(*info_));
          113  + int _ = ;
          114  +END
          115  +*/
          116  +}
          117  +// END CUT HERE

Added SRM/659-U/1B.cpp version [31849cb71c63089e]

            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  +
           38  +class CampLunch { public:
           39  + int count(int N, int M, vector <string> a)
           40  + {
           41  +  memo.assign(N<<M, -1);
           42  +  memo2.assign(N*M<<M, -1);
           43  +  return rec(N, M, a, 0, 0);
           44  + }
           45  +
           46  + vector<int> memo;
           47  + int rec(int N, int M, const vector<string>& A, int d, int yesterday_free) {
           48  +  if(d == N)
           49  +   return 1;
           50  +
           51  +  const int key = (d<<M) | yesterday_free;
           52  +  if(memo[key] >= 0)
           53  +   return memo[key];
           54  +
           55  +  return memo[key] = rec2(N, M, A, d, 0, yesterday_free, 0);
           56  + }
           57  +
           58  + vector<int> memo2;
           59  + int rec2(int N, int M, const vector<string>& A,
           60  +       int d, int i, int yesterday_free, int today_free) {
           61  +  if(i == M)
           62  +   return rec(N,M,A,d+1,today_free);
           63  +
           64  +  const int key = ((d*M+i)<<M) | yesterday_free | today_free;
           65  +  if(memo2[key] >= 0)
           66  +   return memo2[key];
           67  +
           68  +  mint total = 0;
           69  +
           70  +  // Plan 2.
           71  +  int p =  A[d][i] - 'A';
           72  +  if(yesterday_free & (1<<p))
           73  +   total += rec2(N,M,A,d,i+1,yesterday_free&~(1<<p),today_free);
           74  +  // Plan 1.
           75  +  if(i+1<M) {
           76  +   int p2 = A[d][i+1]-'A';
           77  +   total += rec2(N,M,A,d,i+2,yesterday_free&~(1<<p)&~(1<<p2),today_free);
           78  +  }
           79  +  // No Plan.
           80  +  total += rec2(N,M,A,d,i+1,yesterday_free&~(1<<p),today_free|(1<<p));
           81  +  return memo2[key] = total.val;
           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(_, CampLunch().count(N, M, a));}
           99  +int main(){
          100  +
          101  +CASE(0)
          102  + int N = 2;
          103  + int M = 2;
          104  + string a_[] = {"AB","AB"};
          105  +   vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_));
          106  + int _ = 7;
          107  +END
          108  +CASE(1)
          109  + int N = 2;
          110  + int M = 3;
          111  + string a_[] = {"ABC","ABC"};
          112  +   vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_));
          113  + int _ = 22;
          114  +END
          115  +CASE(2)
          116  + int N = 2;
          117  + int M = 3;
          118  + string a_[] = {"ABC","BAC"};
          119  +   vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_));
          120  + int _ = 21;
          121  +END
          122  +CASE(3)
          123  + int N = 1;
          124  + int M = 1;
          125  + string a_[] = {"A"};
          126  +   vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_));
          127  + int _ = 1;
          128  +END
          129  +CASE(4)
          130  + int N = 1;
          131  + int M = 10;
          132  + string a_[] = {"ABDEFHIGJC"};
          133  +   vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_));
          134  + int _ = 89;
          135  +END
          136  +CASE(5)
          137  + int N = 16;
          138  + int M = 16;
          139  + string a_[] = {"ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP","ABCDEFGHIJKLMNOP"};
          140  +   vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_));
          141  + int _ = 950052677;
          142  +END
          143  +/*
          144  +CASE(6)
          145  + int N = ;
          146  + int M = ;
          147  + string a_[] = ;
          148  +   vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_));
          149  + int _ = ;
          150  +END
          151  +CASE(7)
          152  + int N = ;
          153  + int M = ;
          154  + string a_[] = ;
          155  +   vector <string> a(a_, a_+sizeof(a_)/sizeof(*a_));
          156  + int _ = ;
          157  +END
          158  +*/
          159  +}
          160  +// END CUT HERE