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

Added SRM/549-U/1A.cpp version [9fc4b0d6d011b0bd]

            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<LD> CMP;
           21  +
           22  +typedef int           vert;
           23  +typedef vert          edge;
           24  +typedef vector<edge>  edges;
           25  +typedef vector<edges> graph;
           26  +
           27  +bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] )
           28  +{
           29  + for(int i=0; i<G[v].size(); ++i) {
           30  +  vert u = G[v][i];
           31  +  if( visited[u] ) continue;
           32  +  visited[u] = true;
           33  +
           34  +  if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) )
           35  +   { matchTo[v]=u, matchTo[u]=v; return true; }
           36  + }
           37  + return false;
           38  +}
           39  +
           40  +template<int NV>
           41  +int biMatch( graph& G, int L ) // [0,L):left, [L,?):right
           42  +{
           43  + vector<vert> matchTo(G.size(), -1);
           44  + int ans = 0;
           45  + for(vert v=0; v<L; ++v) {
           46  +  bool visited[NV] = {};
           47  +  if( augment(G, v, matchTo, visited) )
           48  +   ++ans;
           49  + }
           50  + return ans;
           51  +}
           52  +
           53  +class PointyWizardHats { public:
           54  + int getNumHats(vector <int> topHeight, vector <int> topRadius, vector <int> bottomHeight, vector <int> bottomRadius)
           55  + {
           56  +  int L = topHeight.size();
           57  +  int R = bottomHeight.size();
           58  +  graph G(L+R);
           59  +  for(int i=0; i<L; ++i)
           60  +   for(int k=0; k<R; ++k)
           61  +    if( ok(topHeight[i], topRadius[i], bottomHeight[k], bottomRadius[k]) )
           62  +     G[i].push_back(L+k);
           63  +  return biMatch<100>(G, L);
           64  + }
           65  +
           66  + bool ok(int th, int tr, int bh, int br)
           67  + {
           68  +  if( th*br > bh*tr ) {
           69  +   return br > tr;
           70  +  }
           71  +  return false;
           72  + }
           73  +};
           74  +
           75  +// BEGIN CUT HERE
           76  +#include <ctime>
           77  +double start_time; string timer()
           78  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           79  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           80  + { os << "{ ";
           81  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           82  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           83  +void verify_case(const int& Expected, const int& Received) {
           84  + bool ok = (Expected == Received);
           85  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           86  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           87  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           88  +#define END  verify_case(_, PointyWizardHats().getNumHats(topHeight, topRadius, bottomHeight, bottomRadius));}
           89  +int main(){
           90  +
           91  +CASE(0)
           92  + int topHeight_[] = {30};
           93  +   vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_));
           94  + int topRadius_[] = {3};
           95  +   vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_));
           96  + int bottomHeight_[] = {3};
           97  +   vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_));
           98  + int bottomRadius_[] = {30};
           99  +   vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_));
          100  + int _ = 1;
          101  +END
          102  +CASE(1)
          103  + int topHeight_[] = {4,4};
          104  +   vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_));
          105  + int topRadius_[] = {4,3};
          106  +   vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_));
          107  + int bottomHeight_[] = {5,12};
          108  +   vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_));
          109  + int bottomRadius_[] = {5,4};
          110  +   vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_));
          111  + int _ = 1;
          112  +END
          113  +CASE(2)
          114  + int topHeight_[] = {3};
          115  +   vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_));
          116  + int topRadius_[] = {3};
          117  +   vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_));
          118  + int bottomHeight_[] = {1,1};
          119  +   vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_));
          120  + int bottomRadius_[] = {2,4};
          121  +   vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_));
          122  + int _ = 1;
          123  +END
          124  +CASE(3)
          125  + int topHeight_[] = {10,10};
          126  +   vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_));
          127  + int topRadius_[] = {2,5};
          128  +   vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_));
          129  + int bottomHeight_[] = {2,9};
          130  +   vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_));
          131  + int bottomRadius_[] = {3,6};
          132  +   vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_));
          133  + int _ = 2;
          134  +END
          135  +CASE(4)
          136  + int topHeight_[] = {3,4,5};
          137  +   vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_));
          138  + int topRadius_[] = {5,4,3};
          139  +   vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_));
          140  + int bottomHeight_[] = {3,4,5};
          141  +   vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_));
          142  + int bottomRadius_[] = {3,8,5};
          143  +   vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_));
          144  + int _ = 2;
          145  +END
          146  +CASE(5)
          147  + int topHeight_[] = {1,2,3,4,5};
          148  +   vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_));
          149  + int topRadius_[] = {2,3,4,5,6};
          150  +   vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_));
          151  + int bottomHeight_[] = {2,3,4,5,6};
          152  +   vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_));
          153  + int bottomRadius_[] = {1,2,3,4,5};
          154  +   vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_));
          155  + int _ = 0;
          156  +END
          157  +CASE(6)
          158  + int topHeight_[] = {123,214,232,323,342,343};
          159  +   vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_));
          160  + int topRadius_[] = {123,123,232,123,323,434};
          161  +   vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_));
          162  + int bottomHeight_[] = {545,322,123,545,777,999};
          163  +   vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_));
          164  + int bottomRadius_[] = {323,443,123,656,767,888};
          165  +   vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_));
          166  + int _ = 5;
          167  +END
          168  +CASE(7)
          169  + int topHeight_[] = {999,999,999,10000,10000,10000};
          170  +   vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_));
          171  + int topRadius_[] = {10000,10000,10000,1,2,3};
          172  +   vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_));
          173  + int bottomHeight_[] = {2324,2323,234,5454,323,232};
          174  +   vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_));
          175  + int bottomRadius_[] = {1,2,3222,434,5454,23};
          176  +   vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_));
          177  + int _ = 3;
          178  +END
          179  +/*
          180  +CASE(8)
          181  + int topHeight_[] = ;
          182  +   vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_));
          183  + int topRadius_[] = ;
          184  +   vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_));
          185  + int bottomHeight_[] = ;
          186  +   vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_));
          187  + int bottomRadius_[] = ;
          188  +   vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_));
          189  + int _ = ;
          190  +END
          191  +CASE(9)
          192  + int topHeight_[] = ;
          193  +   vector <int> topHeight(topHeight_, topHeight_+sizeof(topHeight_)/sizeof(*topHeight_));
          194  + int topRadius_[] = ;
          195  +   vector <int> topRadius(topRadius_, topRadius_+sizeof(topRadius_)/sizeof(*topRadius_));
          196  + int bottomHeight_[] = ;
          197  +   vector <int> bottomHeight(bottomHeight_, bottomHeight_+sizeof(bottomHeight_)/sizeof(*bottomHeight_));
          198  + int bottomRadius_[] = ;
          199  +   vector <int> bottomRadius(bottomRadius_, bottomRadius_+sizeof(bottomRadius_)/sizeof(*bottomRadius_));
          200  + int _ = ;
          201  +END
          202  +*/
          203  +}
          204  +// END CUT HERE

Added SRM/549-U/1B.cpp version [124cec5a706621e0]

            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<LD> CMP;
           21  +
           22  +class MagicalHats { public:
           23  + int NC, NH, H, W, NG;
           24  + vector<int> gain;
           25  + vector< pair<int,int> > hats;
           26  + vector<int> tate_base, yoko_base;
           27  +
           28  + int findMaximumReward(vector <string> board, vector <int> coins, int numGuesses)
           29  + {
           30  +  NC = coins.size();
           31  +  sort(coins.begin(), coins.end());
           32  +  gain.assign(NC+1, 0);
           33  +  partial_sum(coins.begin(), coins.end(), gain.begin()+1);
           34  +
           35  +  H = board.size();
           36  +  W = board[0].size();
           37  +  hats.clear();
           38  +  tate_base.resize(W);
           39  +  yoko_base.resize(H);
           40  +  for(int y=0; y<H; ++y)
           41  +  for(int x=0; x<W; ++x)
           42  +   if(board[y][x] == 'H') {
           43  +    hats.push_back( make_pair(y,x) );
           44  +    tate_base[x]++;
           45  +    yoko_base[y]++;
           46  +   }
           47  +  NH = hats.size();
           48  +  NG = numGuesses;
           49  +
           50  +  int m = 0;
           51  +  for(int i=0; i<NH; ++i)
           52  +   m = m*3 + 2;
           53  +  p_memo.resize(m+1);
           54  +  p_memo_set.resize(m+1);
           55  +  b_memo.resize(m+1);
           56  +  b_memo_set.resize(m+1);
           57  +  return is_possible(m) ? gain[best_num(m, NG)] : -1;
           58  + }
           59  +
           60  + vector<bool> p_memo;
           61  + vector<bool> p_memo_set;
           62  + bool is_possible(int state)
           63  + {
           64  +  if(p_memo_set[state])
           65  +   return p_memo[state];
           66  +  p_memo_set[state] = true;
           67  +
           68  +  vector<int> yoko = yoko_base, tate = tate_base, next;
           69  +  int cnt = 0;
           70  +  for(int i=0,m=1; i<NH; ++i,m*=3)
           71  +  {
           72  +   int v = (state/m)%3;
           73  +   if( v == 1 ) {
           74  +    int y = hats[i].first;
           75  +    int x = hats[i].second;
           76  +    yoko[y]++;
           77  +    tate[x]++;
           78  +    ++cnt;
           79  +   } else if( v == 2 ) {
           80  +    next.push_back(m);
           81  +   }
           82  +  }
           83  +  if( next.empty() )
           84  +  {
           85  +   if( cnt != NC )
           86  +    return false;
           87  +   for(int y=0; y<yoko.size(); ++y)
           88  +    if(yoko[y]%2 != 0)
           89  +     return p_memo[state] = false;
           90  +   for(int x=0; x<tate.size(); ++x)
           91  +    if(tate[x]%2 != 0)
           92  +     return p_memo[state] = false;
           93  +   return p_memo[state] = true;
           94  +  }
           95  +  else
           96  +  {
           97  +   int m = next[0];
           98  +   int s[] = {state-2*m, state-m};
           99  +   return p_memo[state] = ( is_possible(s[0]) || is_possible(s[1]) );
          100  +  }
          101  + }
          102  +
          103  + vector<char> b_memo;
          104  + vector<bool> b_memo_set;
          105  + char best_num(int state, int guess)
          106  + {
          107  +  if( guess==0 )
          108  +   return 0;
          109  +  if(b_memo_set[state])
          110  +   return b_memo[state];
          111  +  b_memo_set[state] = true;
          112  +
          113  +  char best = 0;
          114  +  for(int i=0,m=1; i<NH; ++i,m*=3)
          115  +  {
          116  +   int v = (state/m)%3;
          117  +   if( v == 2 )
          118  +   {
          119  +    int s[] = {state-2*m, state-m};
          120  +    char score = 13;
          121  +    if( is_possible(s[0]) )
          122  +     score = min(score, best_num(s[0], guess-1));
          123  +    if( is_possible(s[1]) )
          124  +     score = min<char>(score, best_num(s[1], guess-1)+1);
          125  +    best = max(best, score);
          126  +   }
          127  +  }
          128  +  return b_memo[state] = best;
          129  + }
          130  +};
          131  +
          132  +// BEGIN CUT HERE
          133  +#include <ctime>
          134  +double start_time; string timer()
          135  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          136  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          137  + { os << "{ ";
          138  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          139  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          140  +void verify_case(const int& Expected, const int& Received) {
          141  + bool ok = (Expected == Received);
          142  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          143  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          144  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          145  +#define END  verify_case(_, MagicalHats().findMaximumReward(board, coins, numGuesses));}
          146  +int main(){
          147  +
          148  +CASE(0)
          149  + string board_[] = {"H"};
          150  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          151  + int coins_[] = {1};
          152  +   vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_));
          153  + int numGuesses = 1;
          154  + int _ = 1;
          155  +END
          156  +CASE(1)
          157  + string board_[] = {"HHH",
          158  + "H.H",
          159  + "HH."};
          160  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          161  + int coins_[] = {9};
          162  +   vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_));
          163  + int numGuesses = 1;
          164  + int _ = 9;
          165  +END
          166  +CASE(2)
          167  + string board_[] = {"HH",
          168  + "HH"};
          169  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          170  + int coins_[] = {1,2,3,4};
          171  +   vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_));
          172  + int numGuesses = 3;
          173  + int _ = 6;
          174  +END
          175  +CASE(3)
          176  + string board_[] = {"HHH",
          177  + "HHH",
          178  + "H.H"};
          179  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          180  + int coins_[] = {13,13,13,13};
          181  +   vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_));
          182  + int numGuesses = 2;
          183  + int _ = 13;
          184  +END
          185  +CASE(4)
          186  + string board_[] = {"HHH",
          187  + "HHH",
          188  + "H.H"};
          189  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          190  + int coins_[] = {13,13,13,13};
          191  +   vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_));
          192  + int numGuesses = 3;
          193  + int _ = 26;
          194  +END
          195  +CASE(5)
          196  + string board_[] = {"H.H.",
          197  + ".H.H",
          198  + "H.H."};
          199  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          200  + int coins_[] = {17};
          201  +   vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_));
          202  + int numGuesses = 6;
          203  + int _ = -1;
          204  +END
          205  +CASE(6)
          206  + string board_[] = {"HHH..........",
          207  + "H.H..........",
          208  + "HHH..........",
          209  + "H.H..........",
          210  + "HHH.........."
          211  +".............",
          212  +".............",
          213  +".............",
          214  +".............",
          215  +".............",
          216  +".............",
          217  +".............",
          218  +".............",
          219  +};
          220  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          221  + int coins_[] = {33,337,1007,2403,5601,6003,9999};
          222  +   vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_));
          223  + int numGuesses = 5;
          224  + int _ = 1377;
          225  +END
          226  +CASE(7)
          227  + string board_[] = {".............",
          228  + ".............",
          229  + ".............",
          230  + ".............",
          231  + ".............",
          232  + ".............",
          233  + ".....H.H.....",
          234  + "......H......",
          235  + ".....H.H.....",
          236  + ".............",
          237  + ".............",
          238  + ".............",
          239  + "............."};
          240  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          241  + int coins_[] = {22};
          242  +   vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_));
          243  + int numGuesses = 3;
          244  + int _ = 22;
          245  +END
          246  +/*
          247  +CASE(8)
          248  + string board_[] = ;
          249  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          250  + int coins_[] = ;
          251  +   vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_));
          252  + int numGuesses = ;
          253  + int _ = ;
          254  +END
          255  +CASE(9)
          256  + string board_[] = ;
          257  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          258  + int coins_[] = ;
          259  +   vector <int> coins(coins_, coins_+sizeof(coins_)/sizeof(*coins_));
          260  + int numGuesses = ;
          261  + int _ = ;
          262  +END
          263  +*/
          264  +}
          265  +// END CUT HERE