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

Added SRM/581-U/1A.cpp version [0a6601339e127c92]

            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  +class SurveillanceSystem { public:
           23  + string getContainerInfo(string containers, vector <int> reports, int L)
           24  + {
           25  +  const int N = containers.size();
           26  +
           27  +  map< int, vector<int> > seen_to_pos;
           28  +  for(int s=0; s+L<=N; ++s)
           29  +   seen_to_pos[count(containers.begin()+s, containers.begin()+s+L, 'X')].push_back(s);
           30  +
           31  +  map<int,int> seen_to_cnt;
           32  +  for(int i=0; i<reports.size(); ++i)
           33  +   seen_to_cnt[reports[i]]++;
           34  +
           35  +  string result(N, '-');
           36  +  for(map<int,int>::iterator it=seen_to_cnt.begin(); it!=seen_to_cnt.end(); ++it)
           37  +  {
           38  +   int s = it->first;
           39  +   int c = it->second;
           40  +   vector<int>& p = seen_to_pos[s];
           41  +   mask(N, L, p, c, result);
           42  +  }
           43  +  return result;
           44  + }
           45  +
           46  + // May/must choose |K| ranges out of |p|. Update |result|.
           47  + void mask(int N, int L, vector<int>& p, int K, string& result)
           48  + {
           49  +  assert(K > 0);
           50  +  sort(p.begin(), p.end());
           51  +
           52  +  // Any range can be watched.
           53  +  for(int i=0; i<p.size(); ++i) {
           54  +   for(int x=p[i]; x<p[i]+L; ++x)
           55  +    if(result[x] == '-')
           56  +     result[x] = '?';
           57  +  }
           58  +
           59  +  // Do "always" check.
           60  +  for(int x=0; x<N; ++x) {
           61  +   int cover = 0;
           62  +   for(int i=0; i<p.size(); ++i)
           63  +    if(p[i]<=x && x<p[i]+L)
           64  +     ++cover;
           65  +   // If |x| is covered by some range but avoiding them leaves <K...
           66  +   if(cover && (p.size()-cover) < K)
           67  +    result[x] = '+';
           68  +  }
           69  + }
           70  +};
           71  +
           72  +// BEGIN CUT HERE
           73  +#include <ctime>
           74  +double start_time; string timer()
           75  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           76  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           77  + { os << "{ ";
           78  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           79  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           80  +void verify_case(const string& Expected, const string& Received) {
           81  + bool ok = (Expected == Received);
           82  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           83  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           84  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           85  +#define END  verify_case(_, SurveillanceSystem().getContainerInfo(containers, reports, L));}
           86  +int main(){
           87  +
           88  +CASE(0)
           89  + string containers = "-X--XX";
           90  + int reports_[] = {1, 2};
           91  +   vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_));
           92  + int L = 3;
           93  + string _ = "??++++";
           94  +END
           95  +CASE(1)
           96  + string containers = "-XXXXX-";
           97  + int reports_[] = {2};
           98  +   vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_));
           99  + int L = 3;
          100  + string _ = "???-???";
          101  +END
          102  +CASE(2)
          103  + string containers = "------X-XX-";
          104  + int reports_[] = {3, 0, 2, 0};
          105  +   vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_));
          106  + int L = 5;
          107  + string _ = "++++++++++?";
          108  +END
          109  +CASE(3)
          110  + string containers = "-XXXXX---X--";
          111  + int reports_[] = {2, 1, 0, 1};
          112  +   vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_));
          113  + int L = 3;
          114  + string _ = "???-??++++??";
          115  +END
          116  +CASE(4)
          117  + string containers = "-XX--X-XX-X-X--X---XX-X---XXXX-----X";
          118  + int reports_[] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3};
          119  +   vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_));
          120  + int L = 7;
          121  + string _ = "???++++?++++++++++++++++++++??????--";
          122  +END
          123  +/*
          124  +CASE(5)
          125  + string containers = ;
          126  + int reports_[] = ;
          127  +   vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_));
          128  + int L = ;
          129  + string _ = ;
          130  +END
          131  +CASE(6)
          132  + string containers = ;
          133  + int reports_[] = ;
          134  +   vector <int> reports(reports_, reports_+sizeof(reports_)/sizeof(*reports_));
          135  + int L = ;
          136  + string _ = ;
          137  +END
          138  +*/
          139  +}
          140  +// END CUT HERE

Added SRM/581-U/1B.cpp version [0ed1faf3d467caed]

            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  +class TreeUnion { public:
           23  + double expectedCycles(vector <string> tree1, vector <string> tree2, int K)
           24  + {
           25  +  vector<int> t1, t2;
           26  +  {
           27  +   stringstream sin(accumulate(tree1.begin(), tree1.end(), string()));
           28  +   for(int v; sin>>v; ) t1.push_back(v);
           29  +  }
           30  +  {
           31  +   stringstream sin(accumulate(tree2.begin(), tree2.end(), string()));
           32  +   for(int v; sin>>v; ) t2.push_back(v);
           33  +  }
           34  +
           35  +  int N = t1.size() + 1;
           36  +  vector<vector<int> > d1 = make_d(t1, N);
           37  +  vector<vector<int> > d2 = make_d(t2, N);
           38  +
           39  +  map<int, int> len_to_cnt_2;
           40  +  for(int u=0; u<N; ++u)
           41  +  for(int v=u+1; v<N; ++v)
           42  +   len_to_cnt_2[d2[u][v]] += 2;
           43  +  int total = N * (N-1);
           44  +
           45  +  double e = 0.0;
           46  +  for(int u=0; u<N; ++u)
           47  +  for(int v=u+1; v<N; ++v)
           48  +  {
           49  +   e += (double)len_to_cnt_2[K - 2 - d1[u][v]] / total;
           50  +  }
           51  +  return e;
           52  + }
           53  +
           54  + vector<vector<int> > make_d(const vector<int>& x, int N)
           55  + {
           56  +  vector<vector<int> > d(N, vector<int>(N, 0x3fffffff));
           57  +  for(int i=0; i<N; ++i) d[i][i] = 0;
           58  +  for(int i=0; i<x.size(); ++i) {
           59  +   d[i+1][x[i]] = 1;
           60  +   d[x[i]][i+1] = 1;
           61  +  }
           62  +  for(int k=0; k<N; ++k)
           63  +  for(int i=0; i<N; ++i)
           64  +  for(int j=0; j<N; ++j)
           65  +   d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
           66  +  return d;
           67  + }
           68  +};
           69  +
           70  +// BEGIN CUT HERE
           71  +#include <ctime>
           72  +double start_time; string timer()
           73  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           74  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           75  + { os << "{ ";
           76  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           77  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           78  +void verify_case(const double& Expected, const double& Received) {
           79  + bool ok = (abs(Expected - Received) < 1e-9);
           80  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           81  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           82  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           83  +#define END  verify_case(_, TreeUnion().expectedCycles(tree1, tree2, K));}
           84  +int main(){
           85  +
           86  +CASE(0)
           87  + string tree1_[] = {"0"};
           88  +   vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
           89  + string tree2_[] = {"0"};
           90  +   vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
           91  + int K = 4;
           92  + double _ = 1.0;
           93  +END
           94  +CASE(1)
           95  + string tree1_[] = {"0 1"};
           96  +   vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
           97  + string tree2_[] = {"0 1"};
           98  +   vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
           99  + int K = 4;
          100  + double _ = 1.3333333333333333;
          101  +END
          102  +CASE(2)
          103  + string tree1_[] = {"0 1"};
          104  +   vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
          105  + string tree2_[] = {"0 1"};
          106  +   vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
          107  + int K = 6;
          108  + double _ = 0.3333333333333333;
          109  +END
          110  +CASE(3)
          111  + string tree1_[] = {"0 ", "1 1 1"};
          112  +   vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
          113  + string tree2_[] = {"0 1 0 ", "1"};
          114  +   vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
          115  + int K = 5;
          116  + double _ = 4.0;
          117  +END
          118  +CASE(4)
          119  + string tree1_[] = {"0 1 2 0 1 2 0 1 2 5 6 1", "0 11", " 4"};
          120  +   vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
          121  + string tree2_[] = {"0 1 1 0 2 3 4 3 4 6 6", " 10 12 12"};
          122  +   vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
          123  + int K = 7;
          124  + double _ = 13.314285714285713;
          125  +END
          126  +/*
          127  +CASE(5)
          128  + string tree1_[] = ;
          129  +   vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
          130  + string tree2_[] = ;
          131  +   vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
          132  + int K = ;
          133  + double _ = ;
          134  +END
          135  +CASE(6)
          136  + string tree1_[] = ;
          137  +   vector <string> tree1(tree1_, tree1_+sizeof(tree1_)/sizeof(*tree1_));
          138  + string tree2_[] = ;
          139  +   vector <string> tree2(tree2_, tree2_+sizeof(tree2_)/sizeof(*tree2_));
          140  + int K = ;
          141  + double _ = ;
          142  +END
          143  +*/
          144  +}
          145  +// END CUT HERE

Added SRM/581-U/1C.cpp version [6e5343b52571efd5]

            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 = 0x1fffffff;
           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 YetAnotherBoardGame { public:
           33  + int g_best;
           34  + int minimumMoves(vector <string> board)
           35  + {
           36  +  int H = board.size();
           37  +  int W = board[0].size();
           38  +  vector<int> b(H);
           39  +  for(int y=0; y<H; ++y)
           40  +   for(int x=0; x<W; ++x)
           41  +    b[y] |= (board[y][x]=='W')<<x;
           42  +  b.push_back(0); // sentinel
           43  +
           44  +  g_best = INF;
           45  +  for(int type=1; type<=2; ++type)
           46  +   for(int mask=0; mask<(1<<W); ++mask)
           47  +   {
           48  +    int cur = b[0];
           49  +    int next = b[1];
           50  +    flip(cur, next, mask, type, W);
           51  +    do_try(cur, next, b, 1, H, W, (type==1 ? mask : 0), (type==2 ? mask : 0), bitcnt(mask));
           52  +   }
           53  +  return g_best==INF ? -1 : g_best;
           54  + }
           55  +
           56  + void flip(int& cur, int& next, int mask, int type, int W)
           57  + {
           58  +  int pat = (type==1 ? 5 : 7);
           59  +  for(int f=0; (1<<f)<=mask; ++f)
           60  +   if((1<<f) & mask)
           61  +    cur ^= (pat<<f>>1)&((1<<W)-1);
           62  +  next ^= mask;
           63  + }
           64  +
           65  + void do_try(int prev, int cur, const vector<int>& b, int y, int H, int W, int must_t1, int must_t2, int acc)
           66  + {
           67  +  if(y==H) {
           68  +   int score = (prev==0 ? 0 : INF) + acc;
           69  +   g_best = min(g_best, score);
           70  +   return;
           71  +  }
           72  +
           73  +  int mask = prev;
           74  +  int score = bitcnt(mask) + acc;
           75  +  if(score >= g_best)
           76  +   return;
           77  +
           78  +  if(!(mask&must_t2)) { // try type 1
           79  +   int curr = cur;
           80  +   int next = b[y+1];
           81  +   flip(curr, next, mask, 1, W);
           82  +   do_try(curr, next, b, y+1, H, W, must_t1|mask, must_t2, score);
           83  +  }
           84  +  if(!(mask&must_t1)) { // try type 2
           85  +   int curr = cur;
           86  +   int next = b[y+1];
           87  +   flip(curr, next, mask, 2, W);
           88  +   do_try(curr, next, b, y+1, H, W, must_t1, must_t2|mask, score);
           89  +  }
           90  + }
           91  +};
           92  +
           93  +// BEGIN CUT HERE
           94  +#include <ctime>
           95  +double start_time; string timer()
           96  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           97  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           98  + { os << "{ ";
           99  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          100  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          101  +void verify_case(const int& Expected, const int& Received) {
          102  + bool ok = (Expected == Received);
          103  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          104  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          105  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          106  +#define END  verify_case(_, YetAnotherBoardGame().minimumMoves(board));}
          107  +int main(){
          108  +
          109  +CASE(0)
          110  + string board_[] = {"BBBBBBBBB",
          111  + "BBWBBBBBB",
          112  + "BWWWBBBBB",
          113  + "BBWBBBWBB",
          114  + "BBBBBWBWB",
          115  + "BBBBBBWBB"};
          116  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          117  + int _ = 2;
          118  +END
          119  +CASE(1)
          120  + string board_[] = {"BBW",
          121  + "WWW",
          122  + "BWW"};
          123  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          124  + int _ = 2;
          125  +END
          126  +CASE(2)
          127  + string board_[] = {"WBW",
          128  + "BBW",
          129  + "WBW"};
          130  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          131  + int _ = 4;
          132  +END
          133  +CASE(3)
          134  + string board_[] = {"BBBB",
          135  + "WBWB",
          136  + "BBBB",
          137  + "BBBB"};
          138  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          139  + int _ = -1;
          140  +END
          141  +CASE(4)
          142  + string board_[] = {"WWWWWBW",
          143  + "WBWBWBW",
          144  + "BBWBBWW"};
          145  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          146  + int _ = 7;
          147  +END
          148  +CASE(5)
          149  + string board_[] = {"WWWWWWWWWW",
          150  + "WWWWWWWWWW",
          151  + "WWWWWWWWWW",
          152  + "WWWWWWWWWW",
          153  + "WWWWWWWWWW",
          154  + "WWWWWWWWWW",
          155  + "WWWWWWWWWW",
          156  + "WWWWWWWWWW",
          157  + "WWWWWWWWWW",
          158  + "WWWWWWWWWW"}
          159  +;
          160  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          161  + int _ = 30;
          162  +END
          163  +/*
          164  +CASE(6)
          165  + string board_[] = ;
          166  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          167  + int _ = ;
          168  +END
          169  +CASE(7)
          170  + string board_[] = ;
          171  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          172  + int _ = ;
          173  +END
          174  +*/
          175  +}
          176  +// END CUT HERE