Check-in [f7e7bde312]
Not logged in
Overview
SHA1 Hash:f7e7bde312d502a7dcc4d3f39a16b65515555f8a
Date: 2012-09-01 14:42:22
User: kinaba
Comment:Practice.
Timelines: family | ancestors | descendants | both | trunk
Downloads: Tarball | ZIP archive
Other Links: files | file ages | manifest
Tags And Properties
Changes
hide diffs side-by-side diffs patch

Added SRM/553-U/1A.cpp version [ede2eda09095edba] 


            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 Suminator { public:
           23  + int findMissing(vector <int> program, int wantedResult)
           24  + {
           25  +  set<int> cand;
           26  +
           27  +  int it = find(program.begin(), program.end(), -1) - program.begin();
           28  +  program[it] = 0;
           29  +  if( eval(program) == complex<LL>(wantedResult, 0) )
           30  +   cand.insert(0);
           31  +  program[it] = -1;
           32  +
           33  +  complex<LL> r = eval(program);
           34  +  if( r.imag()==0 ) {
           35  +   if( r.real()==wantedResult )
           36  +    cand.insert(1);
           37  +  } else {
           38  +   // r.real() + r.imag()*modify == wantedResult
           39  +   if( wantedResult > r.real() )
           40  +    if( (wantedResult - r.real()) % r.imag() == 0 )
           41  +     cand.insert(int((wantedResult - r.real())/r.imag()));
           42  +  }
           43  +
           44  +  return cand.empty() ? -1 : *cand.begin();
           45  + }
           46  +
           47  + complex<LL> eval(const vector<int>& p)
           48  + {
           49  +  stack< complex<LL> > stk;
           50  +  for(int i=0; i<p.size(); ++i)
           51  +   if(p[i] == -1)
           52  +    stk.push(complex<LL>(0,1));
           53  +   else if(p[i] != 0)
           54  +    stk.push(complex<LL>(p[i],0));
           55  +   else {
           56  +    complex<LL> a = 0; if(!stk.empty()){ a=stk.top(); stk.pop(); }
           57  +    complex<LL> b = 0; if(!stk.empty()){ b=stk.top(); stk.pop(); }
           58  +    stk.push(a+b);
           59  +   }
           60  +  complex<LL> r = 0; if(!stk.empty()){ r=stk.top(); stk.pop(); }
           61  +  return r;
           62  + }
           63  +};
           64  +
           65  +// BEGIN CUT HERE
           66  +#include <ctime>
           67  +double start_time; string timer()
           68  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           69  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           70  + { os << "{ ";
           71  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           72  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           73  +void verify_case(const int& Expected, const int& Received) {
           74  + bool ok = (Expected == Received);
           75  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           76  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           77  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           78  +#define END  verify_case(_, Suminator().findMissing(program, wantedResult));}
           79  +int main(){
           80  +
           81  +CASE(0)
           82  + int program_[] = {7,-1,0};
           83  +   vector <int> program(program_, program_+sizeof(program_)/sizeof(*program_));
           84  + int wantedResult = 10;
           85  + int _ = 3;
           86  +END
           87  +CASE(1)
           88  + int program_[] = {100, 200, 300, 0, 100, -1};
           89  +   vector <int> program(program_, program_+sizeof(program_)/sizeof(*program_));
           90  + int wantedResult = 600;
           91  + int _ = 0;
           92  +END
           93  +CASE(2)
           94  + int program_[] = {-1, 7, 3, 0, 1, 2, 0, 0};
           95  +   vector <int> program(program_, program_+sizeof(program_)/sizeof(*program_));
           96  + int wantedResult = 13;
           97  + int _ = 0;
           98  +END
           99  +CASE(3)
          100  + int program_[] = {-1, 8, 4, 0, 1, 2, 0, 0};
          101  +   vector <int> program(program_, program_+sizeof(program_)/sizeof(*program_));
          102  + int wantedResult = 16;
          103  + int _ = -1;
          104  +END
          105  +CASE(4)
          106  + int program_[] = {1000000000, 1000000000, 1000000000,  1000000000, -1, 0, 0, 0, 0};
          107  +   vector <int> program(program_, program_+sizeof(program_)/sizeof(*program_));
          108  + int wantedResult = 1000000000;
          109  + int _ = -1;
          110  +END
          111  +CASE(5)
          112  + int program_[] = {7, -1, 3, 0};
          113  +   vector <int> program(program_, program_+sizeof(program_)/sizeof(*program_));
          114  + int wantedResult = 3;
          115  + int _ = -1;
          116  +END
          117  +/*
          118  +CASE(6)
          119  + int program_[] = ;
          120  +   vector <int> program(program_, program_+sizeof(program_)/sizeof(*program_));
          121  + int wantedResult = ;
          122  + int _ = ;
          123  +END
          124  +CASE(7)
          125  + int program_[] = ;
          126  +   vector <int> program(program_, program_+sizeof(program_)/sizeof(*program_));
          127  + int wantedResult = ;
          128  + int _ = ;
          129  +END
          130  +*/
          131  +}
          132  +// END CUT HERE

Added SRM/553-U/2A.cpp version [438fa969580e8113] 


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

Added SRM/553-U/2C.cpp version [1cbd37b2af1920c6] 


            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 SafeRemoval { public:
           23  + int removeThem(vector <int> seq, int K)
           24  + {
           25  +  sort(seq.begin(), seq.end());
           26  +  const int sum = accumulate(seq.begin(), seq.end(), 0);
           27  +
           28  +  vector<int> cls[4];
           29  +  for(int i=0; i<seq.size(); ++i)
           30  +   cls[seq[i]%4].push_back(seq[i]);
           31  +
           32  +  int best = -1;
           33  +  for(int r=0; r<4; ++r) {
           34  +   int b = rec(cls, 0, 0, 0, 0, K, sum%4);
           35  +   if(b != -1)
           36  +    best = max(best, sum-b);
           37  +  }
           38  +  return best;
           39  + }
           40  +
           41  + map<int, int> memo;
           42  + int rec(const vector<int> cls[4], int a, int b, int c, int d, int K, int R)
           43  + {
           44  +  if(K==0)
           45  +   return (R==0 ? -1 : 0);
           46  +  const int key = ((((K*51+a)*51+b)*51+c)*51+d)*4+R;
           47  +  if(memo.count(key))
           48  +   return memo[key];
           49  +
           50  +  int i[4] = {a,b,c,d};
           51  +  int best = -1;
           52  +  for(int k=0; k<4; ++k) if(R!=k && i[k]<cls[k].size()) {
           53  +   i[k]++;
           54  +   int b = rec(cls, i[0], i[1], i[2], i[3], K-1, (R-k+4)%4);
           55  +   i[k]--;
           56  +   if(b != -1) {
           57  +    b += cls[k][i[k]];
           58  +    best = (best==-1 ? b : min(best, b));
           59  +   }
           60  +  }
           61  +  return memo[key] = best;
           62  + }
           63  +};
           64  +
           65  +// BEGIN CUT HERE
           66  +#include <ctime>
           67  +double start_time; string timer()
           68  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           69  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           70  + { os << "{ ";
           71  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           72  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           73  +void verify_case(const int& Expected, const int& Received) {
           74  + bool ok = (Expected == Received);
           75  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           76  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           77  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           78  +#define END  verify_case(_, SafeRemoval().removeThem(seq, k));}
           79  +int main(){
           80  +
           81  +CASE(0)
           82  + int seq_[] = {3, 8, 4};
           83  +   vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
           84  + int k = 1;
           85  + int _ = 11;
           86  +END
           87  +CASE(1)
           88  + int seq_[] = {1,1,1,1,1,1};
           89  +   vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
           90  + int k = 3;
           91  + int _ = -1;
           92  +END
           93  +CASE(2)
           94  + int seq_[] = {1,6,1,10,1,2,7,11};
           95  +   vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
           96  + int k = 6;
           97  + int _ = 21;
           98  +END
           99  +CASE(3)
          100  + int seq_[] = {1,1,1,1,1,1,1,1,7};
          101  +   vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
          102  + int k = 3;
          103  + int _ = 6;
          104  +END
          105  +/*
          106  +CASE(4)
          107  + int seq_[] = ;
          108  +   vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
          109  + int k = ;
          110  + int _ = ;
          111  +END
          112  +CASE(5)
          113  + int seq_[] = ;
          114  +   vector <int> seq(seq_, seq_+sizeof(seq_)/sizeof(*seq_));
          115  + int k = ;
          116  + int _ = ;
          117  +END
          118  +*/
          119  +}
          120  +// END CUT HERE

Fossil version [8d758d3715] 2012-10-22 12:48:04