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

Added 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

Added 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