Overview
| SHA1 Hash: | a0df672a95c2a30229071ab07ccd1b4ce9dd6af2 |
|---|---|
| Date: | 2013-12-04 13:08:48 |
| User: | kinaba |
| Comment: | 598 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/598-U/1A.cpp version [effb84b9c71f12e1]
> 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 <tuple> > 18 using namespace std; > 19 typedef long long LL; > 20 typedef complex<double> CMP; > 21 > 22 class BinPacking { public: > 23 int minBins(vector <int> item) > 24 { > 25 sort(item.begin(), item.end()); > 26 return rec(item); > 27 } > 28 > 29 int rec(vector<int>& item) > 30 { > 31 if(item.empty()) > 32 return 0; > 33 if(item.back() == 100) > 34 return (item.size()+2)/3; > 35 int w = item.back(); > 36 item.pop_back(); > 37 > 38 int i = -1; > 39 for(int k=0; k<item.size(); ++k) > 40 if(item[k] + w <= 300) > 41 i = k; > 42 if(i!=-1) > 43 item.erase(item.begin() + i); > 44 return 1 + rec(item); > 45 } > 46 > 47 }; > 48 > 49 // BEGIN CUT HERE > 50 #include <ctime> > 51 double start_time; string timer() > 52 { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) > 53 template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) > 54 { os << "{ "; > 55 for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) > 56 os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return > 57 void verify_case(const int& Expected, const int& Received) { > 58 bool ok = (Expected == Received); > 59 if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() > 60 cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' > 61 #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock( > 62 #define END verify_case(_, BinPacking().minBins(item));} > 63 int main(){ > 64 > 65 CASE(0) > 66 int item_[] = {150, 150, 150, 150, 150}; > 67 vector <int> item(item_, item_+sizeof(item_)/sizeof(*item_)); > 68 int _ = 3; > 69 END > 70 CASE(1) > 71 int item_[] = {130, 140, 150, 160}; > 72 vector <int> item(item_, item_+sizeof(item_)/sizeof(*item_)); > 73 int _ = 2; > 74 END > 75 CASE(2) > 76 int item_[] = {100, 100, 100, 100, 100, 100, 100, 100, 100}; > 77 vector <int> item(item_, item_+sizeof(item_)/sizeof(*item_)); > 78 int _ = 3; > 79 END > 80 CASE(3) > 81 int item_[] = {100, 200, 100, 100, 100, 100, 200, 100, 200}; > 82 vector <int> item(item_, item_+sizeof(item_)/sizeof(*item_)); > 83 int _ = 4; > 84 END > 85 CASE(4) > 86 int item_[] = {157, 142, 167, 133, 135, 157, 143, 160, 141, 123, 162, 15 > 87 vector <int> item(item_, item_+sizeof(item_)/sizeof(*item_)); > 88 int _ = 8; > 89 END > 90 /* > 91 CASE(5) > 92 int item_[] = ; > 93 vector <int> item(item_, item_+sizeof(item_)/sizeof(*item_)); > 94 int _ = ; > 95 END > 96 CASE(6) > 97 int item_[] = ; > 98 vector <int> item(item_, item_+sizeof(item_)/sizeof(*item_)); > 99 int _ = ; > 100 END > 101 */ > 102 } > 103 // END CUT HERE