4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <sstream>
4fd800b3a8 2011-02-23        kinaba: #include <iomanip>
4fd800b3a8 2011-02-23        kinaba: #include <vector>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <map>
4fd800b3a8 2011-02-23        kinaba: #include <set>
4fd800b3a8 2011-02-23        kinaba: #include <algorithm>
4fd800b3a8 2011-02-23        kinaba: #include <numeric>
4fd800b3a8 2011-02-23        kinaba: #include <iterator>
4fd800b3a8 2011-02-23        kinaba: #include <functional>
4fd800b3a8 2011-02-23        kinaba: #include <complex>
4fd800b3a8 2011-02-23        kinaba: #include <queue>
4fd800b3a8 2011-02-23        kinaba: #include <stack>
4fd800b3a8 2011-02-23        kinaba: #include <cmath>
4fd800b3a8 2011-02-23        kinaba: #include <cassert>
4fd800b3a8 2011-02-23        kinaba: #include <cstring>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: typedef long long LL;
4fd800b3a8 2011-02-23        kinaba: typedef complex<double> CMP;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: template<typename T>
4fd800b3a8 2011-02-23        kinaba: struct DP3x
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	int N1, N2, N3;
4fd800b3a8 2011-02-23        kinaba: 	vector<T> data;
4fd800b3a8 2011-02-23        kinaba: 	DP3x(int, int N2, int N3, const T& t = T())
4fd800b3a8 2011-02-23        kinaba: 		: N1(2), N2(N2), N3(N3), data(N1*N2*N3, t) { assert(data.size()*sizeof(T) < (1<<26)); }
4fd800b3a8 2011-02-23        kinaba: 	T& operator()(int i1, int i2, int i3)
4fd800b3a8 2011-02-23        kinaba: 		{ i1&=1; return data[ ((i1*N2)+i2)*N3+i3 ]; }
4fd800b3a8 2011-02-23        kinaba: 	void swap(DP3x& rhs)
4fd800b3a8 2011-02-23        kinaba: 		{ data.swap(rhs.data); }
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: static const LL inf = (1LL << 60);
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: class RoadOrFlightHard { public:
4fd800b3a8 2011-02-23        kinaba: 	long long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		// input
4fd800b3a8 2011-02-23        kinaba: 		vector<LL> rt(N), ft(N);
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			rt[0] = roadFirst % roadMod;
4fd800b3a8 2011-02-23        kinaba: 			for(int i=1; i<N; ++i)
4fd800b3a8 2011-02-23        kinaba: 				rt[i] = (LL(rt[i-1])*roadProd + roadAdd) % roadMod;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		{
4fd800b3a8 2011-02-23        kinaba: 			ft[0] = flightFirst % flightMod;
4fd800b3a8 2011-02-23        kinaba: 			for(int i=1; i<N; ++i)
4fd800b3a8 2011-02-23        kinaba: 				ft[i] = (LL(ft[i-1])*flightProd + flightAdd) % flightMod;
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		DP3x<LL> dp(N+1, K+1, 2);
4fd800b3a8 2011-02-23        kinaba: 		for(int n=0; n<=N; ++n)
4fd800b3a8 2011-02-23        kinaba: 		for(int k=0; k<=K; ++k)
4fd800b3a8 2011-02-23        kinaba: 			if( n == 0 ) {
4fd800b3a8 2011-02-23        kinaba: 				dp(n,k,0) = 0;
4fd800b3a8 2011-02-23        kinaba: 				dp(n,k,1) = inf;
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 			else {
4fd800b3a8 2011-02-23        kinaba: 				dp(n,k,0) = min(dp(n-1,k,0), dp(n-1,k,1)) + rt[n-1];
4fd800b3a8 2011-02-23        kinaba: 				if( k == 0 )
4fd800b3a8 2011-02-23        kinaba: 					dp(n,k,1) = inf;
4fd800b3a8 2011-02-23        kinaba: 				else
4fd800b3a8 2011-02-23        kinaba: 					dp(n,k,1) = min(dp(n-1,k,1), dp(n-1,k-1,0)) + ft[n-1];
4fd800b3a8 2011-02-23        kinaba: 			}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		LL ans = inf;
4fd800b3a8 2011-02-23        kinaba: 		for(int k=0; k<=K; ++k)
4fd800b3a8 2011-02-23        kinaba: 			ans = min(ans, min(dp(N,k,0), dp(N,k,1)));
4fd800b3a8 2011-02-23        kinaba: 		return ans;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: // BEGIN CUT HERE
4fd800b3a8 2011-02-23        kinaba: #include <ctime>
4fd800b3a8 2011-02-23        kinaba: double start_time; string timer()
4fd800b3a8 2011-02-23        kinaba:  { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
4fd800b3a8 2011-02-23        kinaba: template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
4fd800b3a8 2011-02-23        kinaba:  { os << "{ ";
4fd800b3a8 2011-02-23        kinaba:    for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
4fd800b3a8 2011-02-23        kinaba:    os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
4fd800b3a8 2011-02-23        kinaba: void verify_case(const long long& Expected, const long long& Received) {
4fd800b3a8 2011-02-23        kinaba:  bool ok = (Expected == Received);
4fd800b3a8 2011-02-23        kinaba:  if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
4fd800b3a8 2011-02-23        kinaba:  cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
4fd800b3a8 2011-02-23        kinaba: #define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
4fd800b3a8 2011-02-23        kinaba: #define END	 verify_case(_, RoadOrFlightHard().minTime(N, roadFirst, roadProd, roadAdd, roadMod, flightFirst, flightProd, flightAdd, flightMod, K));}
4fd800b3a8 2011-02-23        kinaba: int main(){
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: CASE(0)
4fd800b3a8 2011-02-23        kinaba: 	int N = 3;
4fd800b3a8 2011-02-23        kinaba: 	int roadFirst = 14;
4fd800b3a8 2011-02-23        kinaba: 	int roadProd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int roadAdd = 2;
4fd800b3a8 2011-02-23        kinaba: 	int roadMod = 10;
4fd800b3a8 2011-02-23        kinaba: 	int flightFirst = 18;
4fd800b3a8 2011-02-23        kinaba: 	int flightProd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int flightAdd = 10;
4fd800b3a8 2011-02-23        kinaba: 	int flightMod = 17;
4fd800b3a8 2011-02-23        kinaba: 	int K = 1;
4fd800b3a8 2011-02-23        kinaba: 	long long _ = 14LL;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(1)
4fd800b3a8 2011-02-23        kinaba: 	int N = 3;
4fd800b3a8 2011-02-23        kinaba: 	int roadFirst = 4;
4fd800b3a8 2011-02-23        kinaba: 	int roadProd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int roadAdd = 2;
4fd800b3a8 2011-02-23        kinaba: 	int roadMod = 10;
4fd800b3a8 2011-02-23        kinaba: 	int flightFirst = 1;
4fd800b3a8 2011-02-23        kinaba: 	int flightProd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int flightAdd = 10;
4fd800b3a8 2011-02-23        kinaba: 	int flightMod = 17;
4fd800b3a8 2011-02-23        kinaba: 	int K = 2;
4fd800b3a8 2011-02-23        kinaba: 	long long _ = 11LL;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(2)
4fd800b3a8 2011-02-23        kinaba: 	int N = 3;
4fd800b3a8 2011-02-23        kinaba: 	int roadFirst = 4;
4fd800b3a8 2011-02-23        kinaba: 	int roadProd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int roadAdd = 2;
4fd800b3a8 2011-02-23        kinaba: 	int roadMod = 10;
4fd800b3a8 2011-02-23        kinaba: 	int flightFirst = 1;
4fd800b3a8 2011-02-23        kinaba: 	int flightProd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int flightAdd = 6;
4fd800b3a8 2011-02-23        kinaba: 	int flightMod = 9;
4fd800b3a8 2011-02-23        kinaba: 	int K = 1;
4fd800b3a8 2011-02-23        kinaba: 	long long _ = 12LL;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(3)
4fd800b3a8 2011-02-23        kinaba: 	int N = 5;
4fd800b3a8 2011-02-23        kinaba: 	int roadFirst = 85739;
4fd800b3a8 2011-02-23        kinaba: 	int roadProd = 94847;
4fd800b3a8 2011-02-23        kinaba: 	int roadAdd = 93893;
4fd800b3a8 2011-02-23        kinaba: 	int roadMod = 98392;
4fd800b3a8 2011-02-23        kinaba: 	int flightFirst = 92840;
4fd800b3a8 2011-02-23        kinaba: 	int flightProd = 93802;
4fd800b3a8 2011-02-23        kinaba: 	int flightAdd = 93830;
4fd800b3a8 2011-02-23        kinaba: 	int flightMod = 92790;
4fd800b3a8 2011-02-23        kinaba: 	int K = 3;
4fd800b3a8 2011-02-23        kinaba: 	long long _ = 122365LL;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(4)
4fd800b3a8 2011-02-23        kinaba: 	int N = 1;
4fd800b3a8 2011-02-23        kinaba: 	int roadFirst = 2;
4fd800b3a8 2011-02-23        kinaba: 	int roadProd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int roadAdd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int roadMod = 100;
4fd800b3a8 2011-02-23        kinaba: 	int flightFirst = 1;
4fd800b3a8 2011-02-23        kinaba: 	int flightProd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int flightAdd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int flightMod = 2;
4fd800b3a8 2011-02-23        kinaba: 	int K = 0;
4fd800b3a8 2011-02-23        kinaba: 	long long _ = 2LL;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(4)
4fd800b3a8 2011-02-23        kinaba: 	int N = 1;
4fd800b3a8 2011-02-23        kinaba: 	int roadFirst = 2;
4fd800b3a8 2011-02-23        kinaba: 	int roadProd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int roadAdd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int roadMod = 100;
4fd800b3a8 2011-02-23        kinaba: 	int flightFirst = 1;
4fd800b3a8 2011-02-23        kinaba: 	int flightProd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int flightAdd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int flightMod = 2;
4fd800b3a8 2011-02-23        kinaba: 	int K = 1;
4fd800b3a8 2011-02-23        kinaba: 	long long _ = 1LL;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(5)
4fd800b3a8 2011-02-23        kinaba: 	int N = 1;
4fd800b3a8 2011-02-23        kinaba: 	int roadFirst = 0;
4fd800b3a8 2011-02-23        kinaba: 	int roadProd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int roadAdd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int roadMod = 100;
4fd800b3a8 2011-02-23        kinaba: 	int flightFirst = 0;
4fd800b3a8 2011-02-23        kinaba: 	int flightProd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int flightAdd = 1;
4fd800b3a8 2011-02-23        kinaba: 	int flightMod = 1;
4fd800b3a8 2011-02-23        kinaba: 	int K = 1;
4fd800b3a8 2011-02-23        kinaba: 	long long _ = 0LL;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: CASE(6)
4fd800b3a8 2011-02-23        kinaba: 	int N = 400000;
4fd800b3a8 2011-02-23        kinaba: 	int roadFirst = 1234;
4fd800b3a8 2011-02-23        kinaba: 	int roadProd = 56789;
4fd800b3a8 2011-02-23        kinaba: 	int roadAdd = 32323;
4fd800b3a8 2011-02-23        kinaba: 	int roadMod = 99999;
4fd800b3a8 2011-02-23        kinaba: 	int flightFirst = 9876;
4fd800b3a8 2011-02-23        kinaba: 	int flightProd = 44344;
4fd800b3a8 2011-02-23        kinaba: 	int flightAdd = 7865;
4fd800b3a8 2011-02-23        kinaba: 	int flightMod = 99999;
4fd800b3a8 2011-02-23        kinaba: 	int K = 40;
4fd800b3a8 2011-02-23        kinaba: 	long long _ = -1LL;
4fd800b3a8 2011-02-23        kinaba: END
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: // END CUT HERE