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

Added SRM/572-U/1A.cpp version [22fb8b993e155b65]

            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  +struct UnionFind
           23  +{
           24  + vector<int> uf, sz;
           25  + int nc;
           26  +
           27  + UnionFind(int N): uf(N), sz(N,1), nc(N)
           28  +  { for(int i=0; i<N; ++i) uf[i] = i; }
           29  + int size()
           30  +  { return nc; }
           31  + int size(int a)
           32  +  { return sz[Find(a)]; }
           33  + int Find(int a)
           34  +  { return uf[a]==a ? a : uf[a]=Find(uf[a]); }
           35  + bool Union(int a, int b)
           36  +  {
           37  +   a = Find(a);
           38  +   b = Find(b);
           39  +   if( a != b )
           40  +   {
           41  +    if( sz[a] >= sz[b] ) swap(a, b);
           42  +    uf[a] = b;
           43  +    sz[b] += sz[a];
           44  +    --nc;
           45  +   }
           46  +   return (a!=b);
           47  +  }
           48  +};
           49  +
           50  +class NewArenaPassword { public:
           51  + int minChange(string oldPassword, int K)
           52  + {
           53  +  int N = oldPassword.size();
           54  +  UnionFind uf(N);
           55  +  for(int i=0; i<K; ++i)
           56  +   uf.Union(i, N-K+i);
           57  +
           58  +  int total = 0;
           59  +  for(int r=0; r<N; ++r) if(uf.Find(r) == r) {
           60  +   map<char,int> freq;
           61  +   for(int i=0; i<N; ++i)
           62  +    if(uf.Find(i) == r)
           63  +     freq[oldPassword[i]]++;
           64  +   vector<int> fff;
           65  +   for(map<char,int>::iterator it=freq.begin(); it!=freq.end(); ++it)
           66  +    fff.push_back(it->second);
           67  +   total += accumulate(fff.begin(), fff.end(), -*max_element(fff.begin(), fff.end()));
           68  +  }
           69  +  return total;
           70  + }
           71  +};
           72  +
           73  +// BEGIN CUT HERE
           74  +#include <ctime>
           75  +double start_time; string timer()
           76  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           77  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           78  + { os << "{ ";
           79  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           80  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           81  +void verify_case(const int& Expected, const int& Received) {
           82  + bool ok = (Expected == Received);
           83  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           84  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           85  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           86  +#define END  verify_case(_, NewArenaPassword().minChange(oldPassword, K));}
           87  +int main(){
           88  +
           89  +CASE(0)
           90  + string oldPassword = "topcoderopen";
           91  + int K = 5;
           92  + int _ = 3;
           93  +END
           94  +CASE(1)
           95  + string oldPassword = "puyopuyo";
           96  + int K = 4;
           97  + int _ = 0;
           98  +END
           99  +CASE(2)
          100  + string oldPassword = "loool";
          101  + int K = 3;
          102  + int _ = 1;
          103  +END
          104  +CASE(3)
          105  + string oldPassword = "arena";
          106  + int K = 5;
          107  + int _ = 0;
          108  +END
          109  +CASE(4)
          110  + string oldPassword = "amavckdkz";
          111  + int K = 7;
          112  + int _ = 5;
          113  +END
          114  +/*
          115  +CASE(5)
          116  + string oldPassword = ;
          117  + int K = ;
          118  + int _ = ;
          119  +END
          120  +CASE(6)
          121  + string oldPassword = ;
          122  + int K = ;
          123  + int _ = ;
          124  +END
          125  +*/
          126  +}
          127  +// END CUT HERE

Added SRM/572-U/1B.cpp version [b8011a6ba09fe38f]

            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 EllysBulls { public:
           23  + string getNumber(vector <string> guesses, vector <int> bulls)
           24  + {
           25  +  vector<int> pTen(1,1);
           26  +  for(int i=0; i<10; ++i)
           27  +   pTen.push_back(pTen.back()*10);
           28  +
           29  +  int Q = guesses.size();
           30  +  int N = guesses[0].size();
           31  +  int B = min(N, 4);
           32  +  int F = N - B;
           33  +  map<string, vector<int> > back;
           34  +  for(int b=0; b<pTen[B]; ++b)
           35  +  {
           36  +   string sig;
           37  +   for(int i=0; i<Q; ++i)
           38  +   {
           39  +    int s = bulls[i];
           40  +    for(int k=0; k<B; ++k)
           41  +     if( (guesses[i][N-1-k]-'0') == b/pTen[k]%10 )
           42  +      --s;
           43  +    if(s>=0)
           44  +     sig += char('0'+s);
           45  +    else
           46  +     goto next;
           47  +   }
           48  +   back[sig].push_back(b);
           49  +  next:;
           50  +  }
           51  +
           52  +  string cand = "";
           53  +  for(int f=0; f<pTen[F]; ++f)
           54  +  {
           55  +   string sig;
           56  +   map<string, vector<int> >::iterator it;
           57  +   for(int i=0; i<Q; ++i)
           58  +   {
           59  +    int s = 0;
           60  +    for(int k=0; k<F; ++k)
           61  +     if( (guesses[i][F-1-k]-'0') == f/pTen[k]%10 )
           62  +      ++s;
           63  +    if(s<=bulls[i])
           64  +     sig += char('0'+s);
           65  +    else
           66  +     goto next2;
           67  +   }
           68  +   it = back.find(sig);
           69  +   if( it != back.end() ) {
           70  +    for(int j=0; j<it->second.size(); ++j) {
           71  +     if(!cand.empty())
           72  +      return "Ambiguity";
           73  +     for(int k=0; k<F; ++k)
           74  +      cand += char('0'+f/pTen[F-1-k]%10);
           75  +     for(int k=0; k<B; ++k)
           76  +      cand += char('0'+it->second[j]/pTen[B-1-k]%10);
           77  +    }
           78  +   }
           79  +  next2:;
           80  +  }
           81  +
           82  +  if(cand.empty())
           83  +   return "Liar";
           84  +  return cand;
           85  + }
           86  +};
           87  +
           88  +// BEGIN CUT HERE
           89  +#include <ctime>
           90  +double start_time; string timer()
           91  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           92  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           93  + { os << "{ ";
           94  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           95  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           96  +void verify_case(const string& Expected, const string& Received) {
           97  + bool ok = (Expected == Received);
           98  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           99  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
          100  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          101  +#define END  verify_case(_, EllysBulls().getNumber(guesses, bulls));}
          102  +int main(){
          103  +
          104  +CASE(0)
          105  + string guesses_[] = {"1234", "4321", "1111", "2222", "3333", "4444", "5555", "6666", "7777", "8888", "9999"};
          106  +   vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_));
          107  + int bulls_[] = {2, 1, 1, 0, 2, 0, 0, 0, 1, 0, 0};
          108  +   vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_));
          109  + string _ = "1337";
          110  +END
          111  +CASE(1)
          112  + string guesses_[] = {"0000", "1111", "2222"};
          113  +   vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_));
          114  + int bulls_[] = {2, 2, 2};
          115  +   vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_));
          116  + string _ = "Liar";
          117  +END
          118  +CASE(2)
          119  + string guesses_[] = {"666666", "666677", "777777", "999999"};
          120  +   vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_));
          121  + int bulls_[] = {2, 3, 1, 0};
          122  +   vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_));
          123  + string _ = "Ambiguity";
          124  +END
          125  +CASE(3)
          126  + string guesses_[] = {"000", "987", "654", "321", "100", "010"};
          127  +   vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_));
          128  + int bulls_[] = {2, 1, 0, 0, 1, 1};
          129  +   vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_));
          130  + string _ = "007";
          131  +END
          132  +CASE(4)
          133  + string guesses_[] = {"28", "92", "70", "30", "67", "63", "06", "65",
          134  + "11", "06", "88", "48", "09", "65", "48", "08"};
          135  +   vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_));
          136  + int bulls_[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
          137  +   vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_));
          138  + string _ = "54";
          139  +END
          140  +CASE(5)
          141  + string guesses_[] = {"0294884", "1711527", "2362216", "7666148", "7295642",
          142  + "4166623", "1166638", "2767693", "8650248", "2486509",
          143  + "6138934", "4018642", "6236742", "2961643", "8407361",
          144  + "2097376", "6575410", "6071777", "3569948", "2606380"};
          145  +   vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_));
          146  + int bulls_[] = {1, 0, 1, 3, 4, 4, 3, 2, 1, 1, 0, 4, 4, 3, 0, 0, 0, 0, 2, 1};
          147  +   vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_));
          148  + string _ = "4266642";
          149  +END
          150  +/*
          151  +CASE(6)
          152  + string guesses_[] = ;
          153  +   vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_));
          154  + int bulls_[] = ;
          155  +   vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_));
          156  + string _ = ;
          157  +END
          158  +CASE(7)
          159  + string guesses_[] = ;
          160  +   vector <string> guesses(guesses_, guesses_+sizeof(guesses_)/sizeof(*guesses_));
          161  + int bulls_[] = ;
          162  +   vector <int> bulls(bulls_, bulls_+sizeof(bulls_)/sizeof(*bulls_));
          163  + string _ = ;
          164  +END
          165  +*/
          166  +}
          167  +// END CUT HERE