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

Added SRM/625-U/1A.cpp version [e6519d12c7580902]

            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 PalindromePermutations { public:
           23  + double palindromeProbability(string word)
           24  + {
           25  +  map<char, int> cnt;
           26  +  for(char c: word) cnt[c]++;
           27  +
           28  +  vector<int> ns;
           29  +  for(auto cn: cnt) ns.emplace_back(cn.second);
           30  +
           31  +  return solve(ns);
           32  + }
           33  +
           34  + double solve(vector<int> c)
           35  + {
           36  +  if(count_if(c.begin(), c.end(), [&](int x){return x%2==1;}) >= 2)
           37  +   return 0.0;
           38  +  return rec(c);
           39  + }
           40  +
           41  + double rec(vector<int> c)
           42  + {
           43  +  if(c.size() <= 1)
           44  +   return 1.0;
           45  +
           46  +  int n = accumulate(c.begin(), c.end(), 0);
           47  +  int n2 = n/2;
           48  +  int k = c.back();
           49  +  int k2 = k/2;
           50  +  c.pop_back();
           51  +  return C(n2,k2) / C(n,k) * rec(c);
           52  + }
           53  +
           54  + double C(int n, int k)
           55  + {
           56  +  double v = 1.0;
           57  +  for(int i=1; i<=k; ++i)
           58  +   v = v * (n+1-i) / i;
           59  +  return v;
           60  + }
           61  +};
           62  +
           63  +// BEGIN CUT HERE
           64  +#include <ctime>
           65  +double start_time; string timer()
           66  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           67  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           68  + { os << "{ ";
           69  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           70  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           71  +void verify_case(const double& Expected, const double& Received) {
           72  + bool ok = (abs(Expected - Received) < 1e-9);
           73  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           74  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           75  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           76  +#define END  verify_case(_, PalindromePermutations().palindromeProbability(word));}
           77  +int main(){
           78  +
           79  +CASE(0)
           80  + string word = "haha";
           81  + double _ = 0.3333333333333333;
           82  +END
           83  +CASE(1)
           84  + string word = "xxxxy";
           85  + double _ = 0.2;
           86  +END
           87  +CASE(2)
           88  + string word = "xxxx";
           89  + double _ = 1.0;
           90  +END
           91  +CASE(3)
           92  + string word = "abcde";
           93  + double _ = 0.0;
           94  +END
           95  +CASE(4)
           96  + string word = "hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhff";
           97  + double _ = 0.025641025641025637;
           98  +END
           99  +/*
          100  +CASE(5)
          101  + string word = ;
          102  + double _ = ;
          103  +END
          104  +CASE(6)
          105  + string word = ;
          106  + double _ = ;
          107  +END
          108  +*/
          109  +}
          110  +// END CUT HERE

Added SRM/625-U/1B.cpp version [8c270447eda5e6fb]

            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  +template<typename Vert=int, typename Flow=int, int NV=2048>
           23  +class MaxFlow
           24  +{
           25  + vector<int> G[NV];
           26  + Flow F[NV][NV];
           27  +
           28  +public:
           29  + void addEdge( Vert s, Vert t, Flow f )
           30  + {
           31  +  G[s].push_back(t);
           32  +  G[t].push_back(s);
           33  +  F[s][t] = f;
           34  +  F[t][s] = 0;
           35  + }
           36  +
           37  + Flow calc( Vert S, Vert D )
           38  + {
           39  +  for( Flow total=0 ;; ) {
           40  +   // Do BFS and compute the level for each node.
           41  +   int LV[NV] = {0};
           42  +   vector<int> Q(1, S);
           43  +   for(int lv=1; !Q.empty(); ++lv) {
           44  +    vector<int> Q2;
           45  +    for(size_t i=0; i!=Q.size(); ++i) {
           46  +     const vector<int>& ne = G[Q[i]];
           47  +     for(size_t j=0; j!=ne.size(); ++j)
           48  +      if( F[Q[i]][ne[j]] && !LV[ne[j]] && ne[j]!=S )
           49  +       LV[ne[j]]=lv, Q2.push_back(ne[j]);
           50  +    }
           51  +    Q.swap(Q2);
           52  +   }
           53  +
           54  +   // Destination is now unreachable. Done.
           55  +   if( !LV[D] )
           56  +    return total;
           57  +
           58  +   // Iterating DFS.
           59  +   bool blocked[NV] = {};
           60  +   total += dinic_dfs( S, D, LV, 0x7fffffff, blocked );
           61  +  }
           62  + }
           63  +
           64  +private:
           65  + Flow dinic_dfs( int v, int D, int LV[], Flow flow_in, bool blocked[] )
           66  + {
           67  +  Flow flow_out = 0;
           68  +  for(size_t i=0; i!=G[v].size(); ++i) {
           69  +   int u = G[v][i];
           70  +   if( LV[v]+1==LV[u] && F[v][u] ) {
           71  +    Flow f = min(flow_in-flow_out, F[v][u]);
           72  +    if( u==D || !blocked[u] && (f=dinic_dfs(u,D,LV,f,blocked))>0 ) {
           73  +     F[v][u]  -= f;
           74  +     F[u][v]  += f;
           75  +     flow_out += f;
           76  +     if( flow_in == flow_out ) return flow_out;
           77  +    }
           78  +   }
           79  +  }
           80  +  blocked[v] = (flow_out==0);
           81  +  return flow_out;
           82  + }
           83  +};
           84  +
           85  +class BlockTheBlockPuzzle { public:
           86  + int minimumHoles(vector <string> board)
           87  + {
           88  +  const int H = board.size();
           89  +  const int W = board[0].size();
           90  +  const int INF = 2500;
           91  +  for(int gy=0; gy<H; ++gy)
           92  +  for(int gx=0; gx<W; ++gx) if(board[gy][gx] == '$')
           93  +  {
           94  +   map<pair<int,int>, int> id;
           95  +   for(int y=gy%3; y<H; y+=3)
           96  +   for(int x=gx%3; x<W; x+=3)
           97  +   {
           98  +    int new_id = id.size();
           99  +    id[make_pair(y,x)] = new_id;
          100  +   }
          101  +
          102  +   int N = id.size();
          103  +   MaxFlow<>* mf = new MaxFlow<>;
          104  +   enum {IN, OUT};
          105  +
          106  +   int Goal;
          107  +   vector<int> Start;
          108  +   for(int y=gy%3; y<H; y+=3)
          109  +   for(int x=gx%3; x<W; x+=3)if(board[y][x]!='H')
          110  +   {
          111  +    int v1 = id[make_pair(y,x)];
          112  +    if(board[y][x]=='$')
          113  +     Goal = v1;
          114  +    if(board[y][x]=='b')
          115  +     Start.push_back(v1);
          116  +
          117  +    int e = (board[y][x]=='.' ? 1 : INF);
          118  +    mf->addEdge(v1*2+IN, v1*2+OUT, e);
          119  +    //cerr << v1 << " -- " << e << " -- " << v1 << endl;
          120  +
          121  +    const int dy[] = {+1,0};
          122  +    const int dx[] = {0,+1};
          123  +    for(int d=0; d<2; ++d)
          124  +    {
          125  +     int Y = y+dy[d]*3;
          126  +     int X = x+dx[d]*3;
          127  +     if(0<=Y&&Y<H&&0<=X&&X<W&&board[Y][X]!='H')
          128  +     {
          129  +      int v2 = id[make_pair(Y,X)];
          130  +
          131  +      int y1=y+dy[d]*1;
          132  +      int x1=x+dx[d]*1;
          133  +      int y2=y+dy[d]*2;
          134  +      int x2=x+dx[d]*2;
          135  +      int e = INF;
          136  +      if(board[y1][x1]!='b'&&board[y2][x2]!='b')
          137  +       e = (board[y1][x1]=='.')+(board[y2][x2]=='.');
          138  +      if(e) {
          139  +       mf->addEdge(v1*2+OUT, v2*2+IN, e);
          140  +       mf->addEdge(v2*2+OUT, v1*2+IN, e);
          141  +       //cerr << v1 << " -- " << e << " -- " << v2 << endl;
          142  +      }
          143  +     }
          144  +    }
          145  +   }
          146  +
          147  +   for(int v: Start) {
          148  +    //cerr << "S: " << v << endl;
          149  +    mf->addEdge(v*2+OUT, N*2+IN, INF);
          150  +   }
          151  +   //cerr << "G: " << Goal << endl;
          152  +   int ans = mf->calc(Goal*2+OUT, N*2+IN);
          153  +   delete mf;
          154  +   return ans>=INF ? -1 : ans;
          155  +  }
          156  +  return -1;
          157  + }
          158  +};
          159  +
          160  +// BEGIN CUT HERE
          161  +#include <ctime>
          162  +double start_time; string timer()
          163  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          164  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          165  + { os << "{ ";
          166  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          167  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          168  +void verify_case(const int& Expected, const int& Received) {
          169  + bool ok = (Expected == Received);
          170  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          171  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          172  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          173  +#define END  verify_case(_, BlockTheBlockPuzzle().minimumHoles(board));}
          174  +int main(){
          175  +
          176  +CASE(0)
          177  + string board_[] = {"b..$",
          178  + "....",
          179  + "HHHH",
          180  + "HHHH"};
          181  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          182  + int _ = 2;
          183  +END
          184  +CASE(1)
          185  + string board_[] = {"............H..",
          186  + "...............",
          187  + "...............",
          188  + "HHH$HHH.....H..",
          189  + "HHHHHHH........",
          190  + "HHHHHHHH.......",
          191  + "......b..H.....",
          192  + "...............",
          193  + "...............",
          194  + "...H..H..H.....",
          195  + "...............",
          196  + "...............",
          197  + "...............",
          198  + "...............",
          199  + "..............."};
          200  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          201  + int _ = 0;
          202  +END
          203  +CASE(2)
          204  + string board_[] = {"............H..",
          205  + "...............",
          206  + "...............",
          207  + "HHH$HHH........",
          208  + "HHHHHHH........",
          209  + "HHHHHHHH.......",
          210  + "......b..H.....",
          211  + "...............",
          212  + "...............",
          213  + "...H..H..H.....",
          214  + "...............",
          215  + "...............",
          216  + "...............",
          217  + "...............",
          218  + "..............."};
          219  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          220  + int _ = 1;
          221  +END
          222  +CASE(3)
          223  + string board_[] = {"b..$...",
          224  + "...H...",
          225  + ".......",
          226  + "b..b..b",
          227  + "...H...",
          228  + ".......",
          229  + "b..b..b"}
          230  +
          231  +;
          232  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          233  + int _ = 4;
          234  +END
          235  +CASE(4)
          236  + string board_[] = {"b..b..b",
          237  + "..b..b.",
          238  + ".......",
          239  + "b..$bbb",
          240  + ".b.....",
          241  + "....b..",
          242  + "b..b..b"}
          243  +;
          244  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          245  + int _ = -1;
          246  +END
          247  +/*
          248  +CASE(5)
          249  + string board_[] = ;
          250  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          251  + int _ = ;
          252  +END
          253  +CASE(6)
          254  + string board_[] = ;
          255  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          256  + int _ = ;
          257  +END
          258  +*/
          259  +}
          260  +// END CUT HERE