1e11150f2a 2014-02-26 kinaba: #include <iostream> 1e11150f2a 2014-02-26 kinaba: #include <sstream> 1e11150f2a 2014-02-26 kinaba: #include <iomanip> 1e11150f2a 2014-02-26 kinaba: #include <vector> 1e11150f2a 2014-02-26 kinaba: #include <string> 1e11150f2a 2014-02-26 kinaba: #include <map> 1e11150f2a 2014-02-26 kinaba: #include <set> 1e11150f2a 2014-02-26 kinaba: #include <algorithm> 1e11150f2a 2014-02-26 kinaba: #include <numeric> 1e11150f2a 2014-02-26 kinaba: #include <iterator> 1e11150f2a 2014-02-26 kinaba: #include <functional> 1e11150f2a 2014-02-26 kinaba: #include <complex> 1e11150f2a 2014-02-26 kinaba: #include <queue> 1e11150f2a 2014-02-26 kinaba: #include <stack> 1e11150f2a 2014-02-26 kinaba: #include <cmath> 1e11150f2a 2014-02-26 kinaba: #include <cassert> 1e11150f2a 2014-02-26 kinaba: #include <tuple> 1e11150f2a 2014-02-26 kinaba: using namespace std; 1e11150f2a 2014-02-26 kinaba: typedef long long LL; 1e11150f2a 2014-02-26 kinaba: typedef complex<double> CMP; 1e11150f2a 2014-02-26 kinaba: 1e11150f2a 2014-02-26 kinaba: class PackingBallsDiv1 { public: 1e11150f2a 2014-02-26 kinaba: int minPacks(int K, int A, int B, int C, int D) 1e11150f2a 2014-02-26 kinaba: { 1e11150f2a 2014-02-26 kinaba: vector<int> X(K); 1e11150f2a 2014-02-26 kinaba: X[0] = A; 1e11150f2a 2014-02-26 kinaba: for(int i=1; i<K; ++i) 1e11150f2a 2014-02-26 kinaba: X[i] = int((LL(X[i-1]) * B + C) % D + 1); 1e11150f2a 2014-02-26 kinaba: 1e11150f2a 2014-02-26 kinaba: int base = 0; 1e11150f2a 2014-02-26 kinaba: for(int i=0; i<K; ++i) { 1e11150f2a 2014-02-26 kinaba: base += X[i] / K; 1e11150f2a 2014-02-26 kinaba: X[i] %= K; 1e11150f2a 2014-02-26 kinaba: } 1e11150f2a 2014-02-26 kinaba: sort(X.begin(), X.end()); 1e11150f2a 2014-02-26 kinaba: 1e11150f2a 2014-02-26 kinaba: int i = 0; while(i<X.size() && X[i]==0) i++; 1e11150f2a 2014-02-26 kinaba: 1e11150f2a 2014-02-26 kinaba: int best = base + X.size()-i; 1e11150f2a 2014-02-26 kinaba: for(; i<X.size(); ++i) 1e11150f2a 2014-02-26 kinaba: best = min<int>(best, base + X[i] + X.size()-i-1); 1e11150f2a 2014-02-26 kinaba: return best; 1e11150f2a 2014-02-26 kinaba: } 1e11150f2a 2014-02-26 kinaba: }; 1e11150f2a 2014-02-26 kinaba: 1e11150f2a 2014-02-26 kinaba: // BEGIN CUT HERE 1e11150f2a 2014-02-26 kinaba: #include <ctime> 1e11150f2a 2014-02-26 kinaba: double start_time; string timer() 1e11150f2a 2014-02-26 kinaba: { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 1e11150f2a 2014-02-26 kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 1e11150f2a 2014-02-26 kinaba: { os << "{ "; 1e11150f2a 2014-02-26 kinaba: for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 1e11150f2a 2014-02-26 kinaba: os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 1e11150f2a 2014-02-26 kinaba: void verify_case(const int& Expected, const int& Received) { 1e11150f2a 2014-02-26 kinaba: bool ok = (Expected == Received); 1e11150f2a 2014-02-26 kinaba: if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 1e11150f2a 2014-02-26 kinaba: cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 1e11150f2a 2014-02-26 kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 1e11150f2a 2014-02-26 kinaba: #define END verify_case(_, PackingBallsDiv1().minPacks(K, A, B, C, D));} 1e11150f2a 2014-02-26 kinaba: int main(){ 1e11150f2a 2014-02-26 kinaba: 1e11150f2a 2014-02-26 kinaba: CASE(0) 1e11150f2a 2014-02-26 kinaba: int K = 3; 1e11150f2a 2014-02-26 kinaba: int A = 4; 1e11150f2a 2014-02-26 kinaba: int B = 2; 1e11150f2a 2014-02-26 kinaba: int C = 5; 1e11150f2a 2014-02-26 kinaba: int D = 6; 1e11150f2a 2014-02-26 kinaba: int _ = 4; 1e11150f2a 2014-02-26 kinaba: END 1e11150f2a 2014-02-26 kinaba: CASE(1) 1e11150f2a 2014-02-26 kinaba: int K = 1; 1e11150f2a 2014-02-26 kinaba: int A = 58; 1e11150f2a 2014-02-26 kinaba: int B = 23; 1e11150f2a 2014-02-26 kinaba: int C = 39; 1e11150f2a 2014-02-26 kinaba: int D = 93; 1e11150f2a 2014-02-26 kinaba: int _ = 58; 1e11150f2a 2014-02-26 kinaba: END 1e11150f2a 2014-02-26 kinaba: CASE(2) 1e11150f2a 2014-02-26 kinaba: int K = 23; 1e11150f2a 2014-02-26 kinaba: int A = 10988; 1e11150f2a 2014-02-26 kinaba: int B = 5573; 1e11150f2a 2014-02-26 kinaba: int C = 4384; 1e11150f2a 2014-02-26 kinaba: int D = 100007; 1e11150f2a 2014-02-26 kinaba: int _ = 47743; 1e11150f2a 2014-02-26 kinaba: END 1e11150f2a 2014-02-26 kinaba: CASE(3) 1e11150f2a 2014-02-26 kinaba: int K = 100000; 1e11150f2a 2014-02-26 kinaba: int A = 123456789; 1e11150f2a 2014-02-26 kinaba: int B = 234567890; 1e11150f2a 2014-02-26 kinaba: int C = 345678901; 1e11150f2a 2014-02-26 kinaba: int D = 1000000000; 1e11150f2a 2014-02-26 kinaba: int _ = 331988732; 1e11150f2a 2014-02-26 kinaba: END 1e11150f2a 2014-02-26 kinaba: /* 1e11150f2a 2014-02-26 kinaba: CASE(4) 1e11150f2a 2014-02-26 kinaba: int K = ; 1e11150f2a 2014-02-26 kinaba: int A = ; 1e11150f2a 2014-02-26 kinaba: int B = ; 1e11150f2a 2014-02-26 kinaba: int C = ; 1e11150f2a 2014-02-26 kinaba: int D = ; 1e11150f2a 2014-02-26 kinaba: int _ = ; 1e11150f2a 2014-02-26 kinaba: END 1e11150f2a 2014-02-26 kinaba: CASE(5) 1e11150f2a 2014-02-26 kinaba: int K = ; 1e11150f2a 2014-02-26 kinaba: int A = ; 1e11150f2a 2014-02-26 kinaba: int B = ; 1e11150f2a 2014-02-26 kinaba: int C = ; 1e11150f2a 2014-02-26 kinaba: int D = ; 1e11150f2a 2014-02-26 kinaba: int _ = ; 1e11150f2a 2014-02-26 kinaba: END 1e11150f2a 2014-02-26 kinaba: */ 1e11150f2a 2014-02-26 kinaba: } 1e11150f2a 2014-02-26 kinaba: // END CUT HERE