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

Added SRM/TCO12-2B-U/1A.cpp version [02db4ce3f40ece1c]

            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 BlurredDartboard { public:
           29  + int minThrows(vector <int> points, int P)
           30  + {
           31  +  const int N = points.size();
           32  +
           33  +  int VisibleMax = *max_element(points.begin(), points.end());
           34  +
           35  +  vector<int> hidden;
           36  +  for(int x=1; x<=N; ++x)
           37  +   if( count(points.begin(), points.end(), x) == 0 )
           38  +    hidden.push_back(x);
           39  +
           40  +  int K = hidden.size();
           41  +  if( hidden.empty() || hidden.back() < VisibleMax )
           42  +   return (P+VisibleMax-1) / VisibleMax;
           43  +
           44  +  partial_sum(hidden.begin(), hidden.end(), hidden.begin());
           45  +  vector<int> vis;
           46  +  for(int i=1; i<=K; ++i)
           47  +   vis.push_back(i*VisibleMax);
           48  +
           49  +  int turn = max(vis.back(), hidden.back());
           50  +  int n = (P/turn)*K;
           51  +  if(P%turn) {
           52  +   ++n;
           53  +   for(int i=0; max(vis[i],hidden[i]) < (P%turn); ++i)
           54  +    ++n;
           55  +  }
           56  +  return n;
           57  + }
           58  +};
           59  +
           60  +// BEGIN CUT HERE
           61  +#include <ctime>
           62  +double start_time; string timer()
           63  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
           64  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
           65  + { os << "{ ";
           66  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
           67  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
           68  +void verify_case(const int& Expected, const int& Received) {
           69  + bool ok = (Expected == Received);
           70  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
           71  + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
           72  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
           73  +#define END  verify_case(_, BlurredDartboard().minThrows(points, P));}
           74  +int main(){
           75  +
           76  +CASE(0)
           77  + int points_[] = {0, 3, 4, 0, 0};
           78  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
           79  + int P = 8;
           80  + int _ = 2;
           81  +END
           82  +CASE(1)
           83  + int points_[] = {0, 0, 0, 0, 0};
           84  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
           85  + int P = 15;
           86  + int _ = 5;
           87  +END
           88  +CASE(2)
           89  + int points_[] = {4, 7, 8, 1, 3, 2, 6, 5};
           90  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
           91  + int P = 2012;
           92  + int _ = 252;
           93  +END
           94  +CASE(3)
           95  + int points_[] = {0, 0, 5, 0, 0, 0, 1, 3, 0, 0};
           96  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
           97  + int P = 2012;
           98  + int _ = 307;
           99  +END
          100  +CASE(4)
          101  + int points_[] = {0, 2, 0, 0, 0, 0, 0, 0, 0, 9, 0, 0, 6, 0, 0, 0, 4, 0, 0, 0};
          102  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          103  + int P = 1000000000;
          104  + int _ = 84656087;
          105  +END
          106  +CASE(5)
          107  +int points_[] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
          108  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          109  + int P = 1000000000;
          110  + int _ = -1;
          111  +END
          112  +/*
          113  +CASE(6)
          114  + int points_[] = ;
          115  +   vector <int> points(points_, points_+sizeof(points_)/sizeof(*points_));
          116  + int P = ;
          117  + int _ = ;
          118  +END
          119  +*/
          120  +}
          121  +// END CUT HERE

Added SRM/TCO12-2B-U/1B.cpp version [b2dc4bd6b9ccd651]

            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  +template<typename T>
           29  +struct DP2
           30  +{
           31  + const int N1, N2;
           32  + vector<T> data;
           33  + DP2(int N1, int N2, const T& t = T())
           34  +  : N1(N1), N2(N2), data(N1*N2, t) { assert(data.size()*sizeof(T)<(1<<26)); }
           35  + T& operator()(int i1, int i2)
           36  +  { return data[ (i1*N2)+i2 ]; }
           37  + void swap(DP2& rhs)
           38  +  { data.swap(rhs.data); }
           39  +};
           40  +
           41  +class HeavyBooks { public:
           42  + vector <int> findWeight(vector <int> books, vector <int> moves)
           43  + {
           44  +  const int K = moves[0];
           45  +
           46  +  vector<int> tomek, wojtek;
           47  +  for(int i=0; i<K; ++i)
           48  +   wojtek.push_back(i);
           49  +
           50  +  for(int i=1; i<moves.size(); ++i) {
           51  +   vector<int>& fr = (i%2 == 0 ? tomek : wojtek);
           52  +   vector<int>& to = (i%2 == 0 ? wojtek : tomek);
           53  +   for(int k=0; k<moves[i] && !fr.empty(); ++k) {
           54  +    to.push_back(fr.back());
           55  +    fr.pop_back();
           56  +   }
           57  +   sort(fr.begin(), fr.end());
           58  +   sort(to.begin(), to.end());
           59  +  }
           60  +
           61  +  vector<bool> for_tomek(K);
           62  +  for(int i=0; i<tomek.size(); ++i)
           63  +   for_tomek[tomek[i]] = true;
           64  +
           65  +  sort(books.begin(), books.end());
           66  +
           67  +  DP2< pair<int,int> > dp(books.size(), K+1);
           68  +  for(int i=0; i<books.size(); ++i)
           69  +  for(int k=0; k<=K; ++k)
           70  +  {
           71  +   int DifIncr = for_tomek[k-1] ? -books[i] : +books[i];
           72  +   int SumIncr = books[i];
           73  +   if( i == 0 ) {
           74  +    if( k == 0 )
           75  +     dp(i, k) = make_pair(0, 0);
           76  +    else if( k == 1 )
           77  +     dp(i, k) = make_pair(DifIncr, SumIncr);
           78  +    else
           79  +     dp(i, k) = make_pair(-123456789, -123456789);
           80  +   } else {
           81  +    dp(i, k) = dp(i-1, k);
           82  +    if( k == 0 ) {
           83  +    } else {
           84  +     int PrevDif = dp(i-1,k-1).first;
           85  +     int PrevSum = dp(i-1,k-1).second;
           86  +     pair<int,int> next(PrevDif+DifIncr, PrevSum+SumIncr);
           87  +     if( dp(i,k) < next )
           88  +      dp(i,k) = next;
           89  +    }
           90  +   }
           91  +  }
           92  +
           93  +  int WminusT = dp(books.size()-1, K).first;
           94  +  int WplusT = dp(books.size()-1, K).second;
           95  +  vector<int> answer;
           96  +  answer.push_back( (WplusT - WminusT)/2 );
           97  +  answer.push_back( (WplusT + WminusT)/2 );
           98  +  return answer;
           99  + }
          100  +};
          101  +
          102  +// BEGIN CUT HERE
          103  +#include <ctime>
          104  +double start_time; string timer()
          105  + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
          106  +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
          107  + { os << "{ ";
          108  +   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
          109  +   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
          110  +void verify_case(const vector <int>& Expected, const vector <int>& Received) {
          111  + bool ok = (Expected == Received);
          112  + if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
          113  + cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
          114  +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
          115  +#define END  verify_case(_, HeavyBooks().findWeight(books, moves));}
          116  +int main(){
          117  +
          118  +CASE(0)
          119  + int books_[] = {5,2,3,1};
          120  +   vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_));
          121  + int moves_[] = {3,2,1,1,1};
          122  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          123  + int __[] = {3, 7 };
          124  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          125  +END
          126  +CASE(1)
          127  + int books_[] = {10, 100, 1000};
          128  +   vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_));
          129  + int moves_[] = {2, 3};
          130  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          131  + int __[] = {110, 0 };
          132  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          133  +END
          134  +CASE(2)
          135  + int books_[] = {155870,565381};
          136  +   vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_));
          137  + int moves_[] = {1,1,1};
          138  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          139  + int __[] = {0, 565381 };
          140  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          141  +END
          142  +CASE(3)
          143  + int books_[] = {500,500,500,500};
          144  +   vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_));
          145  + int moves_[] = {4,1,1,3,2};
          146  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          147  + int __[] = {500, 1500 };
          148  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          149  +END
          150  +CASE(4)
          151  + int books_[] = {1,1,1,1,1000000};
          152  +   vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_));
          153  + int moves_[] = {1};
          154  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          155  + int __[] = {0, 1000000 };
          156  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          157  +END
          158  +CASE(5)
          159  + int books_[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
          160  +   vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_));
          161  + int moves_[] = {20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1};
          162  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          163  + int __[] = {110, 100 };
          164  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          165  +END
          166  +/*
          167  +CASE(6)
          168  + int books_[] = ;
          169  +   vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_));
          170  + int moves_[] = ;
          171  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          172  + int __[] = ;
          173  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          174  +END
          175  +CASE(7)
          176  + int books_[] = ;
          177  +   vector <int> books(books_, books_+sizeof(books_)/sizeof(*books_));
          178  + int moves_[] = ;
          179  +   vector <int> moves(moves_, moves_+sizeof(moves_)/sizeof(*moves_));
          180  + int __[] = ;
          181  +   vector <int> _(__, __+sizeof(__)/sizeof(*__));
          182  +END
          183  +*/
          184  +}
          185  +// END CUT HERE