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

Added SRM/TCO12-1/1A.cpp version [5b4985a0bbd0b903]

            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 EllysJuice { public:
           29  + vector <string> getWinners(vector <string> players)
           30  + {
           31  +  set<string> winners;
           32  +
           33  +  sort(players.begin(), players.end());
           34  +  do
           35  +   winners.insert( play(players) );
           36  +  while( next_permutation(players.begin(), players.end()) );
           37  +
           38  +  winners.erase("");
           39  +  return vector<string>(winners.begin(), winners.end());
           40  + }
           41  +
           42  + string play(const vector<string>& p)
           43  + {
           44  +  int juice[2] = {65536, 65536};
           45  +  map<string, int> total;
           46  +  for(int i=0; i<p.size(); ++i)
           47  +   total[p[i]] += (juice[i%2]/=2);
           48  +
           49  +  string best_name;
           50  +  int best = 0;
           51  +  bool tie = false;
           52  +  for(map<string, int>::iterator it=total.begin(); it!=total.end(); ++it)
           53  +   if( it->second > best ) {
           54  +    best_name = it->first;
           55  +    best = it->second;
           56  +    tie = false;
           57  +   }
           58  +   else if( it->second == best )
           59  +    tie = true;
           60  +  return tie ? "" : best_name;
           61  + }
           62  +};
           63  +
           64  +// BEGIN CUT HERE
           65  +#include <ctime>
           66  +double start_time; string timer()
           67  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           68  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           69  + { os << "{ ";
           70  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           71  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           72  +void verify_case(const vector <string>& Expected, const vector <string>& Received) {
           73  + bool ok = (Expected == Received);
           74  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           75  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           76  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           77  +#define END  verify_case(_, EllysJuice().getWinners(players));}
           78  +int main(){
           79  +
           80  +CASE(0)
           81  + string players_[] = { "elly", "kriss", "stancho", "elly", "stancho" };
           82  +   vector <string> players(players_, players_+sizeof(players_)/sizeof(*players_));
           83  + string __[] = {"elly", "stancho" };
           84  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
           85  +END
           86  +CASE(1)
           87  + string players_[] = {"torb", "elly", "stancho", "kriss"};
           88  +   vector <string> players(players_, players_+sizeof(players_)/sizeof(*players_));
           89  + vector <string> _;
           90  +END
           91  +CASE(2)
           92  + string players_[] = {"elly", "elly", "elly", "elly", "elly"};
           93  +   vector <string> players(players_, players_+sizeof(players_)/sizeof(*players_));
           94  + string __[] = {"elly" };
           95  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
           96  +END
           97  +CASE(3)
           98  + string players_[] = { "ariadne", "elly", "ariadne", "stancho", "stancho", "kriss", "stancho", "elly" };
           99  +   vector <string> players(players_, players_+sizeof(players_)/sizeof(*players_));
          100  + string __[] = {"ariadne", "elly", "stancho" };
          101  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          102  +END
          103  +CASE(4)
          104  + string players_[] = {"b","b","a","a"};
          105  +   vector <string> players(players_, players_+sizeof(players_)/sizeof(*players_));
          106  +    string __[] = {"a","b"};
          107  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          108  +END
          109  +/*
          110  +CASE(5)
          111  + string players_[] = ;
          112  +   vector <string> players(players_, players_+sizeof(players_)/sizeof(*players_));
          113  + string __[] = ;
          114  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          115  +END
          116  +*/
          117  +}
          118  +// END CUT HERE

Added SRM/TCO12-1/1B.cpp version [ada6668a1964faea]

            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 EllysFractions { public:
           29  + long long getCount(int N)
           30  + {
           31  +  LL total = 0;
           32  +  for(int k=2; k<=N; ++k)
           33  +   total += getExact(k);
           34  +  return total;
           35  + }
           36  +
           37  + LL getExact(int N)
           38  + {
           39  +  int np = 0;
           40  +  for(int p=2; p<=N; ++p)
           41  +   if(is_prime(p))
           42  +    ++np;
           43  +  LL v = 1;
           44  +  for(int i=0; i<np; ++i)
           45  +   v *= 2;
           46  +  return v/2;
           47  + }
           48  +
           49  + bool is_prime(int n)
           50  + {
           51  +  for(int k=2; k<n; ++k)
           52  +   if(n%k == 0)
           53  +    return false;
           54  +  return true;
           55  + }
           56  +};
           57  +
           58  +// BEGIN CUT HERE
           59  +#include <ctime>
           60  +double start_time; string timer()
           61  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           62  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           63  + { os << "{ ";
           64  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           65  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           66  +void verify_case(const long long& Expected, const long long& Received) {
           67  + bool ok = (Expected == Received);
           68  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           69  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           70  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           71  +#define END  verify_case(_, EllysFractions().getCount(N));}
           72  +int main(){
           73  +
           74  +CASE(0)
           75  + int N = 1;
           76  + long long _ = 0LL;
           77  +END
           78  +CASE(1)
           79  + int N = 2;
           80  + long long _ = 1LL;
           81  +END
           82  +CASE(2)
           83  + int N = 3;
           84  + long long _ = 3LL;
           85  +END
           86  +CASE(3)
           87  + int N = 5;
           88  + long long _ = 9LL;
           89  +END
           90  +CASE(4)
           91  + int N = 100;
           92  + long long _ = 177431885LL;
           93  +END
           94  +CASE(5)
           95  + int N = 250;
           96  + long long _ = -1LL;
           97  +END
           98  +CASE(6)
           99  + int N = 4;
          100  + long long _ = 5LL;
          101  +END
          102  +}
          103  +// END CUT HERE

Added SRM/TCO12-1/1C.cpp version [add6efd3494f287b]

            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  +struct UnionFind
           29  +{
           30  + vector<int> uf, sz;
           31  + int nc;
           32  +
           33  + UnionFind(int N): uf(N), sz(N,1), nc(N)
           34  +  { for(int i=0; i<N; ++i) uf[i] = i; }
           35  + int size()
           36  +  { return nc; }
           37  + int Find(int a)
           38  +  { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
           39  + bool Union(int a, int b)
           40  +  {
           41  +   a = Find(a);
           42  +   b = Find(b);
           43  +   if( a != b )
           44  +   {
           45  +    if( sz[a] >= sz[b] ) swap(a, b);
           46  +    uf[a] = b;
           47  +    sz[b] += sz[a];
           48  +    --nc;
           49  +   }
           50  +   return (a!=b);
           51  +  }
           52  +};
           53  +
           54  +class EllysLights { public:
           55  + int getMinimum(string initial, vector <string> switches)
           56  + {
           57  +  int N = switches.size();
           58  +  UnionFind uf(N*2+2);
           59  +  #define TR 0
           60  +  #define FL 1
           61  +  #define POS(x) ((x)+2)
           62  +  #define NEG(x) ((x)+N+2)
           63  +
           64  +  for(int i=0; i<initial.size(); ++i)
           65  +  {
           66  +   vector<int> sw;
           67  +   for(int k=0; k<N; ++k)
           68  +    if( switches[k][i]=='Y' )
           69  +     sw.push_back(k);
           70  +
           71  +   if(initial[i] == 'Y')
           72  +    if(sw.size() == 0)
           73  +    {
           74  +     return -1;
           75  +    }
           76  +    else if(sw.size() == 1)
           77  +    {
           78  +     uf.Union(POS(sw[0]), TR);
           79  +     uf.Union(NEG(sw[0]), FL);
           80  +    }
           81  +    else
           82  +    {
           83  +     uf.Union(POS(sw[0]), NEG(sw[1]));
           84  +     uf.Union(NEG(sw[0]), POS(sw[1]));
           85  +    }
           86  +   else
           87  +    if(sw.size() == 0)
           88  +    {
           89  +    }
           90  +    else if(sw.size() == 1)
           91  +    {
           92  +     uf.Union(POS(sw[0]), FL);
           93  +     uf.Union(NEG(sw[0]), TR);
           94  +    }
           95  +    else
           96  +    {
           97  +     uf.Union(POS(sw[0]), POS(sw[1]));
           98  +     uf.Union(NEG(sw[0]), NEG(sw[1]));
           99  +    }
          100  +  }
          101  +
          102  +  if( uf.Find(TR) == uf.Find(FL) )
          103  +   return -1;
          104  +  for(int k=0; k<N; ++k)
          105  +   if( uf.Find(POS(k)) == uf.Find(NEG(k)) )
          106  +    return -1;
          107  +
          108  +  int minSwitch = 0;
          109  +  set<int> done;
          110  +  for(int k=0; k<N; ++k)
          111  +   if( !done.count(k) )
          112  +   {
          113  +    vector<int> pos(1, k);
          114  +    vector<int> neg;
          115  +    for(int j=k+1; j<N; ++j)
          116  +     if( !done.count(j) )
          117  +      if( uf.Find(POS(k)) == uf.Find(POS(j)) ) {
          118  +       pos.push_back(j);
          119  +       done.insert(j);
          120  +      } else if( uf.Find(POS(k)) == uf.Find(NEG(j)) ) {
          121  +       neg.push_back(j);
          122  +       done.insert(j);
          123  +      }
          124  +    if( uf.Find(POS(k)) == uf.Find(TR) ) {
          125  +     minSwitch += pos.size();
          126  +    }
          127  +    else if( uf.Find(POS(k)) == uf.Find(FL) ) {
          128  +     minSwitch += neg.size();
          129  +    }
          130  +    else {
          131  +     minSwitch += min(pos.size(), neg.size());
          132  +    }
          133  +   }
          134  +  return minSwitch;
          135  + }
          136  +};
          137  +
          138  +// BEGIN CUT HERE
          139  +#include <ctime>
          140  +double start_time; string timer()
          141  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          142  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          143  + { os << "{ ";
          144  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          145  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          146  +void verify_case(const int& Expected, const int& Received) {
          147  + bool ok = (Expected == Received);
          148  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          149  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          150  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          151  +#define END  verify_case(_, EllysLights().getMinimum(initial, switches));}
          152  +int main(){
          153  +
          154  +CASE(0)
          155  + string initial = "YNYNNN";
          156  + string switches_[] = {"YNNYNY", "NYYYNN", "YNYNYN", "NNNNYN", "NYNNNY"};
          157  +   vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_));
          158  + int _ = 2;
          159  +END
          160  +CASE(1)
          161  + string initial = "YNYNYN";
          162  + string switches_[] = {"NNNNNN", "YYYYYY", "NYNNNN", "NNNYNN", "NNNNNY"};
          163  +   vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_));
          164  + int _ = 4;
          165  +END
          166  +CASE(2)
          167  + string initial = "YYN";
          168  + string switches_[] = {"YNY", "NYN"};
          169  +   vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_));
          170  + int _ = -1;
          171  +END
          172  +CASE(3)
          173  + string initial = "NNYNYNYYYNNYYYYN";
          174  + string switches_[] = {"NYNYNYNYNYNYNYNY",
          175  + "YNYNYNYNYNYNYNYN",
          176  + "NNNNNNNNNNNNNNNN",
          177  + "YNNNNNNNNNNNNNNN",
          178  + "NYNNNNNNNNNNNNNN",
          179  + "NNYNNNNNNNNNNNNN",
          180  + "NNNYNNNNNNNNNNNN",
          181  + "NNNNYNNNNNNNNNNN",
          182  + "NNNNNYNNNNNNNNNN",
          183  + "NNNNNNYNNNNNNNNN",
          184  + "NNNNNNNYNNNNNNNN",
          185  + "NNNNNNNNYNNNNNNN",
          186  + "NNNNNNNNNYNNNNNN",
          187  + "NNNNNNNNNNYNNNNN",
          188  + "NNNNNNNNNNNYNNNN",
          189  + "NNNNNNNNNNNNYNNN",
          190  + "NNNNNNNNNNNNNYNN",
          191  + "NNNNNNNNNNNNNNYN",
          192  + "NNNNNNNNNNNNNNNY"};
          193  +   vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_));
          194  + int _ = 6;
          195  +END
          196  +CASE(4)
          197  + string initial = "NYNYNYYYNNYYYNNYNNYYYYYNNYNYYYY";
          198  + string switches_[] = {"NNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN",
          199  + "NNNNNNNNYNNNYNNNNYYNYNNNNYNNNNN",
          200  + "NNNNNNNNNYNNNNNNNNNNNNYNNNNNNNN",
          201  + "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNN",
          202  + "NYNNNNNNNNNNNNYNNNNNNNNNNNNNNNN",
          203  + "NNNNNNNNNNNNNYYNNNNNNNNNNNNNNNY",
          204  + "NNNNNNYNNNNNNNNNNNNYNNNNNYNNNNN",
          205  + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          206  + "YNNNNNNNNNNNNNNNNNNYNNNNNNNNNNN",
          207  + "NNNYNNNNNNNNNNNNNNNNNNNYYNNNNNN",
          208  + "NYNNNNNNNNNNYNNNNNNNNNNNNNNNYNN",
          209  + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          210  + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          211  + "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNY",
          212  + "NNNNNNNNNNYNNNNNNNNNYYYNNNNNNNN",
          213  + "NNNYNNNNNNNNNNNNNNNNNNNNNNNYNNN",
          214  + "NNNNNNNNYNNNNNNNNNNNNNNNYNNNNNN",
          215  + "YNNNYNNNNNNNNNNNNNNNNNNNNNNYNNN",
          216  + "NNNNNNNNNNYNNNNNNNNNNNNNNNNNNNN",
          217  + "NNNNYNNYNNNNNNNNNNNNNNNNNNNNNNN",
          218  + "NNNNNNNYNNNYNNNYNNNNNNNNNNNNNYN"};
          219  +   vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_));
          220  + int _ = 7;
          221  +END
          222  +CASE(5)
          223  + string initial = "NYNYYNYNYYYYNNYNYNNYYNNNNNYNYNNNNNYNNNYN";
          224  + string switches_[] = {"NNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNYNNNN",
          225  + "NNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNN",
          226  + "NNNNNNNNNYNNNNYNNYNNNNNNNNNNNNNNNNNNNNNN",
          227  + "NNNNNNNNNNNNNNNNNNNYNNNNYNNNNNNNYNNNNNNN",
          228  + "NNNNNYNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNN",
          229  + "NNNNNNNNNNNNNNNNNNYNNNNNNNNYNNNYNNNNNYNN",
          230  + "NNNNNNNNNNYNNNNNNNNNNNNNNYNNNNNYNNYNNNNN",
          231  + "NNNNNYNNYNNYNNNNNNNNNNNNNNNNNNNNNYNNNNNN",
          232  + "YNNNYNNNNNNNNNNNNNYNNNYNNYNNNNNNNYNNNNNN",
          233  + "NNNNNNNNNYYNNNNNNNNNNNNYNNNNYNNNNNNNNNNN",
          234  + "NNNNNNNNNNNYNYNNNNNNNNNNNNNNNNNNNNNNNNNY",
          235  + "NNNNNNNNNNNNYNNNNNNNNNNNYNNNNNNNNNNNNNNN",
          236  + "NNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNN",
          237  + "NNNYNNNNNNNNNNNNNNNNNYNNNNNNNNNNYNNNNNNN",
          238  + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          239  + "NNNNNNNNNNNNNNYNNYNNNNNNNNNNNNNNNNNNNNNN",
          240  + "NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYYNNY",
          241  + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNN",
          242  + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          243  + "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          244  + "NNNNNNNYNNNNNYNYNNNNNNNNNNNNNNNNNNNNNNNN",
          245  + "NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNN",
          246  + "NYNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNN",
          247  + "NNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          248  + "NYNNNNYNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN",
          249  + "NNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNN",
          250  + "NNNNNNNNNNNNYNNYYNNNNNNNNNNNNNNNNNNNNNNN",
          251  + "NNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
          252  + "NNNYNNNNNNNNNNNNNNNNYYNNNNNNNNNNNNNNNNNN",
          253  + "NNNNNNNNYNNNNNNNNNNNNNNNNNNNYNYNNNNNNNNN",
          254  + "NNNNNNNNNNNNNNNNNNNNNNNNNNYNNYNNNNNNYNNN"};
          255  +   vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_));
          256  + int _ = -1;
          257  +END
          258  +/*
          259  +CASE(6)
          260  + string initial = ;
          261  + string switches_[] = ;
          262  +   vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_));
          263  + int _ = ;
          264  +END
          265  +CASE(7)
          266  + string initial = ;
          267  + string switches_[] = ;
          268  +   vector <string> switches(switches_, switches_+sizeof(switches_)/sizeof(*switches_));
          269  + int _ = ;
          270  +END
          271  +*/
          272  +}
          273  +// END CUT HERE