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

Added SRM/524-U/2C-U.cpp version [925481462bafb3b0]

            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 <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +class MultiplesWithLimit { public:
           29  + string minMultiples(int N, vector <int> forbiddenDigits)
           30  + {
           31  +  vector<int> allowed;
           32  +  for(int i=0; i<=9; ++i)
           33  +   if( find(forbiddenDigits.begin(), forbiddenDigits.end(), i) == forbiddenDigits.end() )
           34  +    allowed.push_back(i);
           35  +
           36  +  vector< vector< pair<char,int> > > G(N);
           37  +  for(int v=0; v<N; ++v)
           38  +   for(int k=0; k<allowed.size(); ++k)
           39  +    G[v].push_back( make_pair(char('0'+allowed[k]), (v*10 + allowed[k])%N) );
           40  +
           41  +  vector<int> dist_to_zero(N, INF);
           42  +  queue<int> Q;
           43  +  dist_to_zero[0] = 0;
           44  +  Q.push(0);
           45  +  while( !Q.empty() )
           46  +  {
           47  +   int v = Q.front();
           48  +   Q.pop();
           49  +   for(int i=0; i<allowed.size(); ++i)
           50  +   {
           51  +    int vv = (allowed[i]*POW(10,dist_to_zero[v],N) + v) % N;
           52  +    if( dist_to_zero[vv] == INF ) {
           53  +     dist_to_zero[vv] = dist_to_zero[v] + 1;
           54  +     Q.push(vv);
           55  +    }
           56  +   }
           57  +  }
           58  +
           59  +  string all;
           60  +  int v = 0;
           61  +  do {
           62  +   int best = INF;
           63  +   int besta = -1;
           64  +   for(int i=0; i<allowed.size(); ++i)
           65  +    if(v>0 || allowed[i]>0)
           66  +    {
           67  +     int vv = (v*10 + allowed[i]) % N;
           68  +     if( dist_to_zero[vv] < best ) {
           69  +      best = dist_to_zero[vv];
           70  +      besta = allowed[i];
           71  +     }
           72  +    }
           73  +   if( best == INF )
           74  +    return "IMPOSSIBLE";
           75  +   all += char('0' + besta);
           76  +   v = (v*10 + besta) % N;
           77  +   cerr << v << " " << dist_to_zero[v] << " " << besta << endl;
           78  +  } while( v );
           79  +
           80  +  if( all.size() <= 8 )
           81  +   return all;
           82  +  else {
           83  +   stringstream ss;
           84  +   ss << all.substr(0,3) << "..." << all.substr(all.size()-3) << "(" << all.size() << " digits)";
           85  +   return ss.str();
           86  +  }
           87  + }
           88  +
           89  + int POW(int v, int e, int m)
           90  + {
           91  +  int r = 1%m;
           92  +  for(; e; e>>=1,v=v*v%m)
           93  +   if( e&1 )
           94  +    r = r*v%m;
           95  +  return r;
           96  + }
           97  +
           98  + static const int INF = 0x1fffffff;
           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(_, MultiplesWithLimit().minMultiples(N, forbiddenDigits));}
          115  +int main(){
          116  +
          117  +CASE(0)
          118  + int N = 8;
          119  + int forbiddenDigits_[] = {2,3,4,5,6,7,8,9};
          120  +   vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
          121  + string _ = "1000";
          122  +END
          123  +CASE(1)
          124  + int N = 9;
          125  + int forbiddenDigits_[] = {1,3,4,5,6,7,8,9};
          126  +   vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
          127  + string _ = "222...222(9 digits)";
          128  +END
          129  +CASE(2)
          130  + int N = 524;
          131  + int forbiddenDigits_[] = {5,2,4};
          132  +   vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
          133  + string _ = "3668";
          134  +END
          135  +CASE(3)
          136  + int N = 10000;
          137  + int forbiddenDigits_[] = {0};
          138  +   vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
          139  + string _ = "IMPOSSIBLE";
          140  +END
          141  +CASE(4)
          142  + int N = 1;
          143  + int forbiddenDigits_[] = {0,1,2,3,4,5,6,7,8,9};
          144  +   vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
          145  + string _ = "IMPOSSIBLE";
          146  +END
          147  +/*
          148  +CASE(5)
          149  + int N = ;
          150  + int forbiddenDigits_[] = ;
          151  +   vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
          152  + string _ = ;
          153  +END
          154  +CASE(6)
          155  + int N = ;
          156  + int forbiddenDigits_[] = ;
          157  +   vector <int> forbiddenDigits(forbiddenDigits_, forbiddenDigits_+sizeof(forbiddenDigits_)/sizeof(*forbiddenDigits_));
          158  + string _ = ;
          159  +END
          160  +*/
          161  +}
          162  +// END CUT HERE

Added SRM/525-U/1A.cpp version [e66e79bfc0293cc6]

            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 <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +class DropCoins { public:
           29  + int getMinimum(vector <string> board, int K)
           30  + {
           31  +  static const int INF = 0x3fffffff;
           32  +  int best = INF;
           33  +  int H = board.size();
           34  +  int W = board[0].size();
           35  +  vector< vector<int> > sum(H, vector<int>(W+1));
           36  +  for(int y=0; y<H; ++y)
           37  +   for(int x=0; x<W; ++x)
           38  +    sum[y][x+1] = sum[y][x] + (board[y][x]=='o' ? 1 : 0);
           39  +
           40  +  for(int x=0; x<W; ++x)
           41  +   for(int X=x; X<=W; ++X)
           42  +    for(int y=0; y<H; ++y)
           43  +     for(int Y=y; Y<=H; ++Y)
           44  +     {
           45  +      // count
           46  +      int cnt = 0;
           47  +      for(int i=y; i<Y; ++i)
           48  +       cnt += sum[i][X]-sum[i][x];
           49  +      if( cnt == K )
           50  +      {
           51  +       int L = x;
           52  +       int R = W-X;
           53  +       int T = y;
           54  +       int B = H-Y;
           55  +       int move = L+R+min(L,R)+T+B+min(T,B);
           56  +       best = min(best, move);
           57  +      }
           58  +     }
           59  +  return best==INF ? -1 : best;
           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 int& Expected, const int& Received) {
           72  + bool ok = (Expected == Received);
           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(_, DropCoins().getMinimum(board, K));}
           77  +int main(){
           78  +
           79  +CASE(0)
           80  + string board_[] = {".o.."
           81  +,"oooo"
           82  +,"..o."}
           83  +;
           84  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
           85  + int K = 3;
           86  + int _ = 2;
           87  +END
           88  +CASE(1)
           89  + string board_[] = {".....o"
           90  +,"......"
           91  +,"oooooo"
           92  +,"oooooo"
           93  +,"......"
           94  +,"o....."}
           95  +;
           96  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
           97  + int K = 12;
           98  + int _ = 3;
           99  +END
          100  +CASE(2)
          101  + string board_[] = {"...."
          102  +,".oo."
          103  +,".oo."
          104  +,"...."}
          105  +;
          106  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          107  + int K = 3;
          108  + int _ = -1;
          109  +END
          110  +CASE(3)
          111  + string board_[] = {"......."
          112  +,"..ooo.."
          113  +,"ooooooo"
          114  +,".oo.oo."
          115  +,"oo...oo"}
          116  +;
          117  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          118  + int K = 12;
          119  + int _ = 4;
          120  +END
          121  +CASE(4)
          122  + string board_[] = {"................."
          123  +,".ooooooo...oooo.."
          124  +,".ooooooo..oooooo."
          125  +,".oo.......oo..oo."
          126  +,".oo.......oo..oo."
          127  +,".ooooo.....oooo.."
          128  +,".ooooooo...oooo.."
          129  +,".....ooo..oo..oo."
          130  +,"......oo..oo..oo."
          131  +,".ooooooo..oooooo."
          132  +,".oooooo....oooo.."
          133  +,"................."}
          134  +;
          135  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          136  + int K = 58;
          137  + int _ = 6;
          138  +END
          139  +CASE(5)
          140  + string board_[] = {"oooooooooooooooooooooooooooooo",
          141  + "oooooooooooooooooooooooooooooo",
          142  + "oooooooooooooooooooooooooooooo",
          143  + "oooooooooooooooooooooooooooooo",
          144  + "oooooooooooooooooooooooooooooo",
          145  + "oooooooooooooooooooooooooooooo",
          146  + "oooooooooooooooooooooooooooooo",
          147  + "oooooooooooooooooooooooooooooo",
          148  + "oooooooooooooooooooooooooooooo",
          149  + "oooooooooooooooooooooooooooooo",
          150  + "oooooooooooooooooooooooooooooo",
          151  + "oooooooooooooooooooooooooooooo",
          152  + "oooooooooooooooooooooooooooooo",
          153  + "oooooooooooooooooooooooooooooo",
          154  + "oooooooooooooooooooooooooooooo",
          155  + "oooooooooooooooooooooooooooooo",
          156  + "oooooooooooooooooooooooooooooo",
          157  + "oooooooooooooooooooooooooooooo",
          158  + "oooooooooooooooooooooooooooooo",
          159  + "oooooooooooooooooooooooooooooo",
          160  + "oooooooooooooooooooooooooooooo",
          161  + "oooooooooooooooooooooooooooooo",
          162  + "oooooooooooooooooooooooooooooo",
          163  + "oooooooooooooooooooooooooooooo",
          164  + "oooooooooooooooooooooooooooooo",
          165  + "oooooooooooooooooooooooooooooo",
          166  + "oooooooooooooooooooooooooooooo",
          167  + "oooooooooooooooooooooooooooooo",
          168  + "oooooooooooooooooooooooooooooo",
          169  + "oooooooooooooooooooooooooooooo",
          170  +};
          171  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          172  + int K = 1;
          173  + int _ = 58;
          174  +END
          175  +/*
          176  +CASE(6)
          177  + string board_[] = ;
          178  +   vector <string> board(board_, board_+sizeof(board_)/sizeof(*board_));
          179  + int K = ;
          180  + int _ = ;
          181  +END
          182  +*/
          183  +}
          184  +// END CUT HERE

Added SRM/525-U/1B.cpp version [1cfc045ea674117f]

            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 <cstring>
           18  +#ifdef __GNUC__
           19  +#include <ext/hash_map>
           20  +#define unordered_map __gnu_cxx::hash_map
           21  +#else
           22  +#include <unordered_map>
           23  +#endif
           24  +using namespace std;
           25  +typedef long long LL;
           26  +typedef complex<double> CMP;
           27  +
           28  +class Rumor { public:
           29  + int getMinimum(string knowledge, vector <string> graph)
           30  + {
           31  +  const int N = knowledge.size();
           32  +  const int ALL = (1<<N) - 1;
           33  +
           34  +  // Turn the input into bit-vectors.
           35  +  int know=0;
           36  +  for(int v=0; v<N; ++v)
           37  +   know |= (knowledge[v]=='Y') << v;
           38  +  vector<int> g(N);
           39  +  for(int v=0; v<N; ++v)
           40  +  for(int u=0; u<N; ++u)
           41  +   g[v] |= (graph[v][u]=='Y') << u;
           42  +
           43  +  // Try all possible patterns (which rumor each rabit spreads first when she knows both), and simulate.
           44  +  int best = N+1;
           45  +  for(int preferA=0; preferA<(1<<N); ++preferA)
           46  +   for(int knowA=know, knowB=know, didA=0, didB=0, step=0; step<best; ++step) {
           47  +    if( knowA==ALL && knowB==ALL )
           48  +     {best=step; break;}
           49  +
           50  +    int doA=0, doB=0;
           51  +    for(int v=0; v<N; ++v) {
           52  +     bool a_ok = (knowA & 1<<v) && !(didA & 1<<v);
           53  +     bool b_ok = (knowB & 1<<v) && !(didB & 1<<v);
           54  +     doA |= (a_ok && b_ok && (preferA & 1<<v) || a_ok && !b_ok) << v;
           55  +     doB |= (a_ok && b_ok && !(preferA & 1<<v) || !a_ok && b_ok) << v;
           56  +    }
           57  +    didA |= doA;
           58  +    didB |= doB;
           59  +    for(int v=0; v<N; ++v) {
           60  +     if(doA & 1<<v) knowA |= g[v];
           61  +     if(doB & 1<<v) knowB |= g[v];
           62  +    }
           63  +   }
           64  +  return best==N+1 ? -1 : best;
           65  + }
           66  +};
           67  +
           68  +// BEGIN CUT HERE
           69  +#include <ctime>
           70  +double start_time; string timer()
           71  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           72  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           73  + { os << "{ ";
           74  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           75  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           76  +void verify_case(const int& Expected, const int& Received) {
           77  + bool ok = (Expected == Received);
           78  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           79  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           80  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           81  +#define END  verify_case(_, Rumor().getMinimum(knowledge, graph));}
           82  +int main(){
           83  +
           84  +CASE(0)
           85  + string knowledge = "YNN";
           86  + string graph_[] = {"NYN"
           87  +,"NNY"
           88  +,"NNN"};
           89  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
           90  + int _ = 3;
           91  +END
           92  +CASE(1)
           93  + string knowledge = "YNNY";
           94  + string graph_[] = {"NYYN"
           95  +,"YNNY"
           96  +,"YNNY"
           97  +,"NYYN"};
           98  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
           99  + int _ = 1;
          100  +END
          101  +CASE(2)
          102  + string knowledge = "YYYY";
          103  + string graph_[] = {"NYNN"
          104  +,"YNYN"
          105  +,"NYNY"
          106  +,"NNYN"};
          107  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
          108  + int _ = 0;
          109  +END
          110  +CASE(3)
          111  + string knowledge = "YYYYYN";
          112  + string graph_[] = {"NYYYYN"
          113  +,"YNYYYN"
          114  +,"YYNYYN"
          115  +,"YYYNYN"
          116  +,"YYYYNN"
          117  +,"NNNNNN"};
          118  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
          119  + int _ = -1;
          120  +END
          121  +CASE(4)
          122  + string knowledge = "NNNY";
          123  + string graph_[] = {"NNNN"
          124  +,"YNNN"
          125  +,"YNNN"
          126  +,"NYYN"};
          127  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
          128  + int _ = 3;
          129  +END
          130  +CASE(5)
          131  + string knowledge =  "NNNNNNNYYY";
          132  + string graph_[] = {"NYNNYNNYNN"
          133  +,"NNYNYNNNNY"
          134  +,"YYNNNYNNNN"
          135  +,"YNNNYNYNNN"
          136  +,"NNYNNYNNYN"
          137  +,"NNNNYNNNYY"
          138  +,"NYNYNYNNNN"
          139  +,"NNNNNNYNYY"
          140  +,"NNNYNNNYNY"
          141  +,"NYYNNNNYNN"}
          142  +;
          143  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
          144  + int _ = 2;
          145  +END
          146  +CASE(6)
          147  +string knowledge = "YYYNNN";
          148  + string graph_[] = {
          149  +  "NNNYNY",
          150  +  "NNNYYN",
          151  +  "NNNNYY",
          152  +  "NNNNNN",
          153  +  "NNNNNN",
          154  +  "NNNNNN"
          155  + };
          156  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
          157  + int _ = 2;
          158  +END
          159  +/*
          160  +CASE(7)
          161  + string knowledge = ;
          162  + string graph_[] = ;
          163  +   vector <string> graph(graph_, graph_+sizeof(graph_)/sizeof(*graph_));
          164  + int _ = ;
          165  +END
          166  +*/
          167  +}
          168  +// END CUT HERE