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

Added SRM/526-U/2A.cpp version [aa83e3a5e10e2fe4]

            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 CheatingQuiz { public:
           29  + vector <int> howMany(string answers)
           30  + {
           31  +  int N = answers.size();
           32  +  vector<int> re;
           33  +  int A = count(answers.begin(), answers.end(), 'A');
           34  +  int B = count(answers.begin(), answers.end(), 'B');
           35  +  int C = count(answers.begin(), answers.end(), 'C');
           36  +  for(int i=0; i<N; ++i) {
           37  +   re.push_back(!!A + !!B + !!C);
           38  +   (answers[i]=='A' ? A : answers[i]=='B' ? B : C)--;
           39  +  }
           40  +  return re;
           41  + }
           42  +};
           43  +
           44  +// BEGIN CUT HERE
           45  +#include <ctime>
           46  +double start_time; string timer()
           47  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           48  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           49  + { os << "{ ";
           50  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           51  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           52  +void verify_case(const vector <int>& Expected, const vector <int>& Received) {
           53  + bool ok = (Expected == Received);
           54  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           55  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           56  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           57  +#define END  verify_case(_, CheatingQuiz().howMany(answers));}
           58  +int main(){
           59  +
           60  +CASE(0)
           61  + string answers = "AAAAA";
           62  + int __[] = {1, 1, 1, 1, 1 };
           63  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           64  +END
           65  +CASE(1)
           66  + string answers = "AAABBB";
           67  + int __[] = {2, 2, 2, 1, 1, 1 };
           68  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           69  +END
           70  +CASE(2)
           71  + string answers = "CAAAAAC";
           72  + int __[] = {2, 2, 2, 2, 2, 2, 1 };
           73  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           74  +END
           75  +CASE(3)
           76  + string answers = "BBCA";
           77  + int __[] = {3, 3, 2, 1 };
           78  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           79  +END
           80  +CASE(4)
           81  + string answers = "BACACABCBBBBCAAAAACCCABBCAA";
           82  + int __[] = {3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1 };
           83  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           84  +END
           85  +/*
           86  +CASE(5)
           87  + string answers = ;
           88  + int __[] = ;
           89  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           90  +END
           91  +CASE(6)
           92  + string answers = ;
           93  + int __[] = ;
           94  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
           95  +END
           96  +*/
           97  +}
           98  +// END CUT HERE

Added SRM/527-U/1A.cpp version [e86c37863d2b6878]

            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 P8XGraphBuilder { public:
           29  + int solve(vector <int> scores)
           30  + {
           31  +  scores.insert(scores.begin(), 9999999);
           32  +  const int N = scores.size();
           33  +
           34  +  int best = 0;
           35  +  for(int leaves=1; leaves<N; ++leaves)
           36  +   best = max(best, scores[1]*leaves + calc(leaves, N-leaves, scores));
           37  +  return best;
           38  + }
           39  +
           40  + map<pair<int,int>,int> memo;
           41  + int calc(int leaves, int nodes, const vector<int>& scores)
           42  + {
           43  +  if( nodes == 1 )
           44  +   return scores[leaves];
           45  +
           46  +  pair<int,int> key(leaves, nodes);
           47  +  if( memo.count(key) )
           48  +   return memo[key];
           49  +
           50  +  int best = 0;
           51  +  for(int k=1; k<=leaves; ++k)
           52  +   best = max(best, scores[k+1] + calc(leaves-k+1, nodes-1, scores));
           53  +  return memo[key] = best;
           54  + }
           55  +};
           56  +
           57  +// BEGIN CUT HERE
           58  +#include <ctime>
           59  +double start_time; string timer()
           60  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           61  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           62  + { os << "{ ";
           63  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           64  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           65  +void verify_case(const int& Expected, const int& Received) {
           66  + bool ok = (Expected == Received);
           67  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           68  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           69  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           70  +#define END  verify_case(_, P8XGraphBuilder().solve(scores));}
           71  +int main(){
           72  +
           73  +CASE(0)
           74  + int scores_[] = {1, 3, 0};
           75  +   vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_));
           76  + int _ = 8;
           77  +END
           78  +CASE(1)
           79  + int scores_[] = {0, 0, 0, 10};
           80  +   vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_));
           81  + int _ = 10;
           82  +END
           83  +CASE(2)
           84  + int scores_[] = {1, 2, 3, 4, 5, 6};
           85  +   vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_));
           86  + int _ = 12;
           87  +END
           88  +CASE(3)
           89  + int scores_[] = {5, 0, 0};
           90  +   vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_));
           91  + int _ = 15;
           92  +END
           93  +CASE(4)
           94  + int scores_[] = {1, 3, 2, 5, 3, 7, 5};
           95  +   vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_));
           96  + int _ = 20;
           97  +END
           98  +CASE(5)
           99  +int scores_[] = {1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10};
          100  +   vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_));
          101  + int _ = -1;
          102  +END
          103  +CASE(6)
          104  + int scores_[] = {2};
          105  +   vector <int> scores(scores_, scores_+sizeof(scores_)/sizeof(*scores_));
          106  + int _ = 4;
          107  +END
          108  +
          109  +}
          110  +// END CUT HERE

Added SRM/527-U/1B.cpp version [9446f824184a311c]

            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  +typedef int           vert;
           29  +typedef vert          edge;
           30  +typedef vector<edge>  edges;
           31  +typedef vector<edges> graph;
           32  +
           33  +bool augment( graph& G, int v, vector<vert>& matchTo, bool visited[] )
           34  +{
           35  + for(int i=0; i<G[v].size(); ++i) {
           36  +  vert u = G[v][i];
           37  +  if( visited[u] ) continue;
           38  +  visited[u] = true;
           39  +
           40  +  if( matchTo[u]<0 || augment(G, matchTo[u], matchTo, visited) )
           41  +   { matchTo[v]=u, matchTo[u]=v; return true; }
           42  + }
           43  + return false;
           44  +}
           45  +
           46  +template<int NV>
           47  +int biMatch( graph& G, int L ) // [0,L):left, [L,?):right
           48  +    // only left->right edges are used during computation
           49  +{
           50  + vector<vert> matchTo(G.size(), -1);
           51  + int ans = 0;
           52  + for(vert v=0; v<L; ++v) {
           53  +  bool visited[NV] = {};
           54  +  if( augment(G, v, matchTo, visited) )
           55  +   ++ans;
           56  + }
           57  + return ans;
           58  +}
           59  +
           60  +class P8XMatrixRecovery { public:
           61  + int H, W;
           62  + vector <string> solve(vector <string> rows, vector <string> columns)
           63  + {
           64  +  H = rows.size();
           65  +  W = rows[0].size();
           66  +  for(int y=0; y<H; ++y)
           67  +   for(int x=0; x<W; ++x)
           68  +    if( rows[y][x] == '?' ) {
           69  +     rows[y][x] = '0';
           70  +     if( !can(rows, columns) )
           71  +      rows[y][x] = '1';
           72  +    }
           73  +  return rows;
           74  + }
           75  +
           76  + bool can(const vector<string>& rows, const vector<string>& columns)
           77  + {
           78  +  graph G(W*2);
           79  +  for(int x1=0; x1<W; ++x1) {
           80  +   string left;
           81  +   for(int y=0; y<H; ++y)
           82  +    left += rows[y][x1];
           83  +   for(int x2=0; x2<W; ++x2)
           84  +    if( match(left, columns[x2]) )
           85  +     G[x1].push_back(x2+W);
           86  +  }
           87  +  return biMatch<60>(G, W) == W;
           88  + }
           89  +
           90  + bool match( const string& l, const string& r )
           91  + {
           92  +  for(int i=0; i<l.size(); ++i)
           93  +   if( l[i]!=r[i] && l[i]!='?' && r[i]!='?' )
           94  +    return false;
           95  +  return true;
           96  + }
           97  +};
           98  +
           99  +// BEGIN CUT HERE
          100  +#include <ctime>
          101  +double start_time; string timer()
          102  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          103  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          104  + { os << "{ ";
          105  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          106  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          107  +void verify_case(const vector <string>& Expected, const vector <string>& Received) {
          108  + bool ok = (Expected == Received);
          109  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          110  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
          111  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          112  +#define END  verify_case(_, P8XMatrixRecovery().solve(rows, columns));}
          113  +int main(){
          114  +
          115  +CASE(0)
          116  + string rows_[] = {"10?"
          117  +,"?11"};
          118  +   vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_));
          119  + string columns_[] = {"01"
          120  +,"10"
          121  +,"1?"}
          122  +;
          123  +   vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_));
          124  + string __[] = {"101", "011" };
          125  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          126  +END
          127  +CASE(1)
          128  + string rows_[] = {"0"
          129  +,"?"
          130  +,"1"};
          131  +   vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_));
          132  + string columns_[] = {"0?1"};
          133  +   vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_));
          134  + string __[] = {"0", "0", "1" };
          135  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          136  +END
          137  +CASE(2)
          138  + string rows_[] = {"10"
          139  +,"01"};
          140  +   vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_));
          141  + string columns_[] = {"10"
          142  +,"01"};
          143  +   vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_));
          144  + string __[] = {"10", "01" };
          145  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          146  +END
          147  +CASE(3)
          148  + string rows_[] = {"??0"
          149  +,"11?"
          150  +,"?01"
          151  +,"1?1"};
          152  +   vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_));
          153  + string columns_[] = {"1???"
          154  +,"?111"
          155  +,"0?1?"};
          156  +   vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_));
          157  + string __[] = {"010", "110", "101", "101" };
          158  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          159  +END
          160  +CASE(4)
          161  + string rows_[] = {
          162  +  "??????????????????????????????",
          163  +  "??????????????????????????????",
          164  +  "??????????????????????????????",
          165  +  "??????????????????????????????",
          166  +  "??????????????????????????????",
          167  +  "??????????????????????????????",
          168  +  "??????????????????????????????",
          169  +  "??????????????????????????????",
          170  +  "??????????????????????????????",
          171  +  "??????????????????????????????",
          172  +  "??????????????????????????????",
          173  +  "??????????????????????????????",
          174  +  "??????????????????????????????",
          175  +  "??????????????????????????????",
          176  +  "??????????????????????????????",
          177  +  "??????????????????????????????",
          178  +  "??????????????????????????????",
          179  +  "??????????????????????????????",
          180  +  "??????????????????????????????",
          181  +  "??????????????????????????????",
          182  +  "??????????????????????????????",
          183  +  "??????????????????????????????",
          184  +  "??????????????????????????????",
          185  +  "??????????????????????????????",
          186  +  "??????????????????????????????",
          187  +  "??????????????????????????????",
          188  +  "??????????????????????????????",
          189  +  "??????????????????????????????",
          190  +  "??????????????????????????????",
          191  +  "??????????????????????????????",
          192  + };
          193  +   vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_));
          194  + string columns_[] = {
          195  +  "??????????????????????????????",
          196  +  "??????????????????????????????",
          197  +  "??????????????????????????????",
          198  +  "??????????????????????????????",
          199  +  "??????????????????????????????",
          200  +  "??????????????????????????????",
          201  +  "??????????????????????????????",
          202  +  "??????????????????????????????",
          203  +  "??????????????????????????????",
          204  +  "??????????????????????????????",
          205  +  "??????????????????????????????",
          206  +  "??????????????????????????????",
          207  +  "??????????????????????????????",
          208  +  "??????????????????????????????",
          209  +  "??????????????????????????????",
          210  +  "??????????????????????????????",
          211  +  "??????????????????????????????",
          212  +  "??????????????????????????????",
          213  +  "??????????????????????????????",
          214  +  "??????????????????????????????",
          215  +  "??????????????????????????????",
          216  +  "??????????????????????????????",
          217  +  "??????????????????????????????",
          218  +  "??????????????????????????????",
          219  +  "??????????????????????????????",
          220  +  "??????????????????????????????",
          221  +  "??????????????????????????????",
          222  +  "??????????????????????????????",
          223  +  "??????????????????????????????",
          224  +  "??????????????????????????????",
          225  + };
          226  +   vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_));
          227  +  string __[] = {"?"};
          228  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          229  +END
          230  +CASE(5)
          231  +string rows_[] = {"?"};
          232  +   vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_));
          233  + string columns_[] = {"?"};
          234  +   vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_));
          235  + string __[] = {"0"};
          236  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          237  +END
          238  +CASE(6)
          239  + string rows_[] = {"??","??"};
          240  +   vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_));
          241  + string columns_[] = {"00","11"};
          242  +   vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_));
          243  + string __[] = {"01","01"};
          244  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          245  +END
          246  +CASE(7)
          247  + string rows_[] = {"0??", "?0?"};
          248  +   vector <string> rows(rows_, rows_+sizeof(rows_)/sizeof(*rows_));
          249  + string columns_[] = {"01", "00", "10"};
          250  +   vector <string> columns(columns_, columns_+sizeof(columns_)/sizeof(*columns_));
          251  + string __[] = {"001", "100"};
          252  +   vector <string> _(__, __+sizeof(__)/sizeof(*__));
          253  +END
          254  +
          255  +}
          256  +// END CUT HERE

Added SRM/527-U/2A.cpp version [395d0c02f1fc9461]

            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 P8XMatrixTransformation { public:
           29  + string solve(vector <string> original, vector <string> target)
           30  + {
           31  +  int so = 0, st = 0;
           32  +  for(int y=0; y<original.size(); ++y) {
           33  +   so += accumulate(original[y].begin(), original[y].end(), 0);
           34  +   st += accumulate(target[y].begin(), target[y].end(), 0);
           35  +  }
           36  +  return so==st ? "YES" : "NO";
           37  + }
           38  +};
           39  +
           40  +// BEGIN CUT HERE
           41  +#include <ctime>
           42  +double start_time; string timer()
           43  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           44  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           45  + { os << "{ ";
           46  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           47  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           48  +void verify_case(const string& Expected, const string& Received) {
           49  + bool ok = (Expected == Received);
           50  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           51  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           52  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           53  +#define END  verify_case(_, P8XMatrixTransformation().solve(original, target));}
           54  +int main(){
           55  +
           56  +CASE(0)
           57  + string original_[] = {"01"
           58  +,"11"};
           59  +   vector <string> original(original_, original_+sizeof(original_)/sizeof(*original_));
           60  + string target_[] = {"11"
           61  +,"10"};
           62  +   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
           63  + string _ = "YES";
           64  +END
           65  +CASE(1)
           66  + string original_[] = {"0111"
           67  +,"0011"};
           68  +   vector <string> original(original_, original_+sizeof(original_)/sizeof(*original_));
           69  + string target_[] = {"1011"
           70  +,"1100"};
           71  +   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
           72  + string _ = "YES";
           73  +END
           74  +CASE(2)
           75  + string original_[] = {"0"};
           76  +   vector <string> original(original_, original_+sizeof(original_)/sizeof(*original_));
           77  + string target_[] = {"1"};
           78  +   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
           79  + string _ = "NO";
           80  +END
           81  +CASE(3)
           82  + string original_[] = {"1111"
           83  +,"1111"
           84  +,"0000"
           85  +,"0000"};
           86  +   vector <string> original(original_, original_+sizeof(original_)/sizeof(*original_));
           87  + string target_[] = {"1111"
           88  +,"1111"
           89  +,"0000"
           90  +,"0000"};
           91  +   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
           92  + string _ = "YES";
           93  +END
           94  +CASE(4)
           95  + string original_[] = {"0110"
           96  +,"1001"
           97  +,"0110"};
           98  +   vector <string> original(original_, original_+sizeof(original_)/sizeof(*original_));
           99  + string target_[] = {"1111"
          100  +,"0110"
          101  +,"0000"};
          102  +   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
          103  + string _ = "YES";
          104  +END
          105  +CASE(5)
          106  + string original_[] = {"0000"
          107  +,"1111"
          108  +,"0000"};
          109  +   vector <string> original(original_, original_+sizeof(original_)/sizeof(*original_));
          110  + string target_[] = {"1111"
          111  +,"0000"
          112  +,"1111"};
          113  +   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
          114  + string _ = "NO";
          115  +END
          116  +/*
          117  +CASE(6)
          118  + string original_[] = ;
          119  +   vector <string> original(original_, original_+sizeof(original_)/sizeof(*original_));
          120  + string target_[] = ;
          121  +   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
          122  + string _ = ;
          123  +END
          124  +CASE(7)
          125  + string original_[] = ;
          126  +   vector <string> original(original_, original_+sizeof(original_)/sizeof(*original_));
          127  + string target_[] = ;
          128  +   vector <string> target(target_, target_+sizeof(target_)/sizeof(*target_));
          129  + string _ = ;
          130  +END
          131  +*/
          132  +}
          133  +// END CUT HERE

Added SRM/527-U/2C.cpp version [8a1cb626f49403d6]

            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 P8XCoinChangeAnother { public:
           29  + vector<long long> solve(int N, long long coins_sum, long long coins_count)
           30  + {
           31  +  vector<LL> result;
           32  +  for(int i=0; i<N; ++i) {
           33  +   LL tick = i==N-1 ? coins_sum>>i : ((1LL<<i)&coins_sum ? 1 : 0);
           34  +   result.push_back( tick );
           35  +   coins_count -= tick;
           36  +  }
           37  +  if( coins_count < 0 )
           38  +   return vector<LL>();
           39  +
           40  +  for(int i=N-1; i>0; --i) {
           41  +   if( coins_count == 0 )
           42  +    return result;
           43  +   else {
           44  +    LL& me = result[i];
           45  +    LL dec = min(me, coins_count);
           46  +    me -= dec;
           47  +    result[i-1] += dec*2;
           48  +    coins_count -= dec;
           49  +   }
           50  +  }
           51  +  return coins_count == 0 ? result : vector<LL>();
           52  + }
           53  +};
           54  +
           55  +// BEGIN CUT HERE
           56  +#include <ctime>
           57  +double start_time; string timer()
           58  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           59  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           60  + { os << "{ ";
           61  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           62  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           63  +void verify_case(const vector<long long>& Expected, const vector<long long>& Received) {
           64  + bool ok = (Expected == Received);
           65  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           66  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
           67  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           68  +#define END  verify_case(_, P8XCoinChangeAnother().solve(N, coins_sum, coins_count));}
           69  +int main(){
           70  +
           71  +CASE(0)
           72  + int N = 2;
           73  + long long coins_sum = 4LL;
           74  + long long coins_count = 3LL;
           75  + long long __[] = {2, 1 };
           76  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
           77  +END
           78  +CASE(1)
           79  + int N = 3;
           80  + long long coins_sum = 6LL;
           81  + long long coins_count = 3LL;
           82  + long long __[] = {0, 3, 0 };
           83  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
           84  +END
           85  +CASE(2)
           86  + int N = 2;
           87  + long long coins_sum = 8LL;
           88  + long long coins_count = 1LL;
           89  + vector<long long> _;
           90  +END
           91  +CASE(3)
           92  + int N = 1;
           93  + long long coins_sum = 10000000000LL;
           94  + long long coins_count = 10000000000LL;
           95  + long long __[] = {10000000000 };
           96  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
           97  +END
           98  +/*
           99  +CASE(4)
          100  + int N = ;
          101  + long long coins_sum = LL;
          102  + long long coins_count = LL;
          103  + long long __[] = ;
          104  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          105  +END
          106  +CASE(5)
          107  + int N = ;
          108  + long long coins_sum = LL;
          109  + long long coins_count = LL;
          110  + long long __[] = ;
          111  +   vector<long long> _(__, __+sizeof(__)/sizeof(*__));
          112  +END
          113  +*/
          114  +}
          115  +// END CUT HERE