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

Name change from from SRM/TCO15-2B/1A.cpp to SRM/TCO15-2B-U/1A.cpp.

Name change from from SRM/TCO15-2B/1B.cpp to SRM/TCO15-2B-U/1B.cpp.

Deleted SRM/TCO15-2B/1A.cpp version [f77c6b1cfc679969]

     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 Bitwisdom { public:
    23         - double expectedActions(vector <int> p)
    24         - {
    25         -  double e = 0;
    26         -  for(int i=1; i<p.size(); ++i) {
    27         -   e += (p[i]/100.0) * (100-p[i-1])/100.0
    28         -    + (p[i-1]/100.0) * (100-p[i])/100.0;
    29         -  }
    30         -  double q = 1.0;
    31         -  for(int i=0; i<p.size(); ++i)
    32         -   q *= (p[i]/100.0);
    33         -  return e + q;
    34         - }
    35         -};
    36         -
    37         -// BEGIN CUT HERE
    38         -#include <ctime>
    39         -double start_time; string timer()
    40         - { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
    41         -template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
    42         - { os << "{ ";
    43         -   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
    44         -   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
    45         -void verify_case(const double& Expected, const double& Received) {
    46         - bool ok = (abs(Expected - Received) < 1e-9);
    47         - if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
    48         - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
    49         -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
    50         -#define END  verify_case(_, Bitwisdom().expectedActions(p));}
    51         -int main(){
    52         -
    53         -CASE(0)
    54         - int p_[] = {100, 100, 100};
    55         -   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
    56         - double _ = 1.0;
    57         -END
    58         -CASE(1)
    59         - int p_[] = {50, 50};
    60         -   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
    61         - double _ = 0.75;
    62         -END
    63         -CASE(2)
    64         - int p_[] = {0, 40, 50, 60};
    65         -   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
    66         - double _ = 1.4;
    67         -END
    68         -CASE(3)
    69         - int p_[] = {37, 63, 23, 94, 12};
    70         -   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
    71         - double _ = 2.6820475464;
    72         -END
    73         -/*
    74         -CASE(4)
    75         - int p_[] = ;
    76         -   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
    77         - double _ = ;
    78         -END
    79         -CASE(5)
    80         - int p_[] = ;
    81         -   vector <int> p(p_, p_+sizeof(p_)/sizeof(*p_));
    82         - double _ = ;
    83         -END
    84         -*/
    85         -}
    86         -// END CUT HERE

Deleted SRM/TCO15-2B/1B.cpp version [1948580a37893b4c]

     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 Balance { public:
    23         - string canTransform(vector <string> initial, vector <string> target)
    24         - {
    25         -  auto ti = gen_tree(initial);
    26         -  auto tt = gen_tree(target);
    27         -  return tree_eq(ti, tt) ? "Possible" : "Impossible";
    28         - }
    29         -
    30         - vector<vector<int>> gen_tree(vector<string> s) {
    31         -  s.push_back(string(s[0].size(), '#'));
    32         -  s.insert(s.begin(), string(s[0].size(), '#'));
    33         -  for(auto& si: s)
    34         -   si = '#'+si+'#';
    35         -
    36         -  const int H = s.size(), W = s[0].size();
    37         -  const int NOTYET = 0x7fffffff;
    38         -
    39         -  vector<vector<int>> tree;
    40         -  vector<vector<int>> parent_cand(H, vector<int>(W, -1));
    41         -  vector<vector<int>> color(H, vector<int>(W, NOTYET));
    42         -  for(int y=0; y<H; ++y)
    43         -  for(int x=0; x<W; ++x)
    44         -  if(color[y][x]==NOTYET) {
    45         -   const char ME = s[y][x];
    46         -   int newId = tree.size();
    47         -   tree.resize(newId+1);
    48         -
    49         -   // BFS
    50         -   set<int> tonari;
    51         -
    52         -   queue<pair<int,int>> Q;
    53         -   color[y][x] = newId;
    54         -   Q.emplace(y, x);
    55         -   while(!Q.empty()) {
    56         -    int yy = Q.front().first;
    57         -    int xx = Q.front().second;
    58         -    Q.pop();
    59         -
    60         -    int dx[] = {-1,+1,0,0};
    61         -    int dy[] = {0,0,-1,+1};
    62         -    for(int d=0; d<4; ++d) {
    63         -     int y2 = yy+dy[d];
    64         -     int x2 = xx+dx[d];
    65         -     if(0<=x2&&x2<W&&0<=y2&&y2<H) {
    66         -      if(s[y2][x2]==ME&&color[y2][x2]==NOTYET) {
    67         -       color[y2][x2] = newId;
    68         -       Q.emplace(y2, x2);
    69         -      }
    70         -      if(s[y2][x2]!=ME&&color[y2][x2]!=NOTYET) {
    71         -       tonari.insert(color[y2][x2]);
    72         -      }
    73         -     }
    74         -    }
    75         -   }
    76         -   if(tonari.size() == 1)
    77         -    tree[*tonari.begin()].push_back(newId);
    78         -  }
    79         -  return tree;
    80         - }
    81         -
    82         - map<vector<int>, int> hashId;
    83         - bool tree_eq(const vector<vector<int>>& a, const vector<vector<int>>& b)
    84         - {
    85         -  return hash(a,0) == hash(b,0);
    86         - }
    87         -
    88         - int hash(const vector<vector<int>>& a, int r)
    89         - {
    90         -  vector<int> ch;
    91         -  for(int v: a[r])
    92         -   ch.push_back(hash(a, v));
    93         -  sort(ch.begin(), ch.end());
    94         -  if(hashId.count(ch))
    95         -   return hashId[ch];
    96         -  int v = hashId.size();
    97         -  return hashId[ch] = v;
    98         - }
    99         -};
   100         -
   101         -// BEGIN CUT HERE
   102         -#include <ctime>
   103         -double start_time; string timer()
   104         - { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
   105         -template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
   106         - { os << "{ ";
   107         -   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
   108         -   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
   109         -void verify_case(const string& Expected, const string& Received) {
   110         - bool ok = (Expected == Received);
   111         - if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
   112         - cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
   113         -#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
   114         -#define END  verify_case(_, Balance().canTransform(initial, target));}
   115         -int main(){
   116         -
   117         -CASE(0)
   118         - string initial_[] = {"#"};
   119         -   vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_));
   120         - string target_[] = {"."};
   121         -   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
   122         - string _ = "Impossible";
   123         -END
   124         -CASE(1)
   125         - string initial_[] = {"..",
   126         - ".."};
   127         -   vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_));
   128         - string target_[] = {".#",
   129         - "##"};
   130         -   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
   131         - string _ = "Possible";
   132         -END
   133         -CASE(2)
   134         - string initial_[] = {"...",
   135         - ".#.",
   136         - "..."};
   137         -   vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_));
   138         - string target_[] = {"###",
   139         - "#.#",
   140         - "###"};
   141         -   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
   142         - string _ = "Impossible";
   143         -END
   144         -CASE(3)
   145         - string initial_[] = {".#.#.......",
   146         - "####.###...",
   147         - ".....####..",
   148         - "..##.#.##.#",
   149         - ".##..#.##.#",
   150         - ".#######...",
   151         - ".#....###.#",
   152         - ".##.#.#....",
   153         - "..#...#...#",
   154         - "..#####...#",
   155         - "..........."};
   156         -   vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_));
   157         - string target_[] = {"...........",
   158         - ".###....#..",
   159         - ".#.#..#....",
   160         - ".###.......",
   161         - ".#####.....",
   162         - ".#...#####.",
   163         - ".#.#.....#.",
   164         - ".#.#####.#.",
   165         - ".#.......#.",
   166         - ".#########.",
   167         - "..........."};
   168         -   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
   169         - string _ = "Impossible";
   170         -END
   171         -CASE(4)
   172         - string initial_[] = {".....",
   173         - ".###.",
   174         - ".....",
   175         - ".###.",
   176         - "....."};
   177         -   vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_));
   178         - string target_[] = {".....",
   179         - ".#.#.",
   180         - ".#.#.",
   181         - ".#.#.",
   182         - "....."};
   183         -   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
   184         - string _ = "Possible";
   185         -END
   186         -/*
   187         -CASE(5)
   188         - string initial_[] = ;
   189         -   vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_));
   190         - string target_[] = ;
   191         -   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
   192         - string _ = ;
   193         -END
   194         -CASE(6)
   195         - string initial_[] = ;
   196         -   vector <string> initial(initial_, initial_+sizeof(initial_)/sizeof(*initial_));
   197         - string target_[] = ;
   198         -   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
   199         - string _ = ;
   200         -END
   201         -*/
   202         -
   203         -}
   204         -// END CUT HERE

Added SRM/TCO15-2C-U/1A.cpp version [d9b27fe6bd32c9ac]

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