fork download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <cstdlib>
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <stack>
  12. #include <list>
  13. #include <cmath>
  14. #include <iomanip>
  15. #define dibs reserve
  16. #define OVER9000 1234567890
  17. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  18. #define tisic 47
  19. #define soclose 1e-6
  20. #define chocolate win
  21. // so much chocolate
  22. #define patkan 9
  23. #define ff first
  24. #define ss second
  25. #define abs(x) ((x < 0)?-(x):x)
  26. #define uint unsigned int
  27. using namespace std;
  28. // mylittledoge
  29.  
  30. struct info {
  31. 	int Q,P,K,H;
  32. 	info() {}
  33. 	info(int q, int p, int k, int h) {Q =q, P =p, K =k, H =h;}
  34.  
  35. 	bool operator<(const info &A) const {
  36. 		if(Q != A.Q) return Q < A.Q;
  37. 		if(H != A.H) return H < A.H;
  38. 		if(P != A.P) return P < A.P;
  39. 		return K < A.K;}
  40. 	};
  41.  
  42. map<info,bool> M;
  43. map<info,info> ako;
  44.  
  45. bool poss(int Q, int P, int K, int H) {
  46. 	if(Q < 0 || H <= 0) return false;
  47. 	int Qa =Q;
  48. 	for(int i =0; i < K; i++) {
  49. 		int I =int(round(Qa*(P/100.0)+soclose)+soclose);
  50. 		if(I >= H) break;
  51. 		Qa =max(-1,Qa+I-H);}
  52. 	if(Qa > 0) return false;
  53. 	Qa =Q;
  54. 	for(int i =0; i < K; i++) {
  55. 		int I =int(round(Qa*(P/100.0)+soclose)+soclose);
  56. 		if(I >= max(0,H-i)) break;
  57. 		Qa =max(-1,Qa+I-max(0,H-i));}
  58. 	if(Qa < 0) return false;
  59. 	if(M.find(info(Q,P,K,H)) != M.end()) {return M[info(Q,P,K,H)];}
  60. 	if(K == 0) {
  61. 		if(Q != 0) M[info(Q,P,K,H)] =false;
  62. 		else M[info(Q,P,K,H)] =true;
  63. 		return M[info(Q,P,K,H)];}
  64. 	int I =int(round(Q*(P/100.0)+soclose)+soclose);
  65. 	if(I >= H) {
  66. 		M[info(Q,P,K,H)] =false;
  67. 		return false;}
  68. //	if(M.size()%100 == 0) cout << Q << " " << K << " " << H << " " << M.size() << endl;
  69. 	if(poss(Q+I-H,P,K-1,H)) {
  70. 		ako[info(Q,P,K,H)] =info(Q+I-H,P,K-1,H);
  71. 		M[info(Q,P,K,H)] =true;
  72. 		return true;}
  73. 	if(poss(Q+I-H,P,K-1,H-1)) {
  74. 		ako[info(Q,P,K,H)] =info(Q+I-H,P,K-1,H-1);
  75. 		M[info(Q,P,K,H)] =true;
  76. 		return true;}
  77. 	M[info(Q,P,K,H)] =false;
  78. 	return false;}
  79.  
  80. int main() {
  81. 	cin.sync_with_stdio(0);
  82. 	cin.tie(0);
  83. 	double q;
  84. 	int P,K;
  85. 	cin >> q >> P >> K;
  86. 	int Q =int(q*100+soclose);
  87.  
  88. 	int hiA =0, hiB =2*Q+1;
  89. 	while(hiB-hiA > 1) {
  90. 		int Qa =Q, hi =(hiA+hiB)/2;
  91. 		for(int i =0; i < K; i++) {
  92. 			int I =int(round(Qa*(P/100.0)+soclose)+soclose);
  93. 			if(I > hi && Qa > 0) break;
  94. 			Qa +=I-hi;
  95. 			Qa =max(Qa,-1);}
  96. 		if(Qa <= 0) hiB =hi;
  97. 		else hiA =hi;}
  98.  
  99. 	int h =hiB+1000;
  100. 	for(int i =hiB+100; i >= max(0,hiB-100); i--) 
  101. 		if(poss(Q,P,K,i)) h =min(h,i);
  102. /*	for(int i =0; i < K; i++) {
  103. 		int a;
  104. 		cin >> a;
  105. 		int I =int(round(Q*(P/100.0)+soclose)+soclose);
  106. 		Q +=I-a;
  107. 		cout << a << " " << Q << "\n";}
  108. 	cout << poss(66524126,85,2,79887306) << "\n";
  109. */	if(h == hiB+1000) {cout << "Impossible\n"; return 0;}
  110. 	map<int,int> ans;
  111. 	for(int k =0; k < K; k++) {
  112. 		info I =ako[info(Q,P,K-k,h)];
  113. 		ans[h]++;
  114. 		h =I.H;
  115. 		Q =I.Q;}
  116. 	cout << fixed << setprecision(2);
  117. 	for(auto it =ans.rbegin(); it != ans.rend(); it++) {
  118. 		cout << "$" << it->ff/100 << ".";
  119. 		if((it->ff)%100 < 10) cout << "0";
  120. 		cout << it->ff%100;
  121. 		cout << " for " << it->ss << " year(s)\n";}
  122. 	return 0;}
  123.  
  124. // look at my code
  125. // my code is amazing
Success #stdin #stdout 0s 3440KB
comments (?)
stdin
copy 
939850.83 85 35
79887322
79887321
79887320
79887319
79887318
79887318
79887317
79887316
79887316
79887315
79887314
79887314
79887313
79887312
79887312
79887312
79887312
79887311
79887310
79887309
79887308
79887308
79887308
79887307
79887306
79887305
79887304
79887303
79887302
79887302
79887301
79887301
79887300
79887299
79887298


79887322
79887321
79887320
79887319
79887318
79887317
79887317
79887317
79887317
79887316
79887315
79887315
79887314
79887313
79887313
79887313
79887312
79887311
79887311
79887311
79887311
79887310
79887310
79887309
79887309
79887309
79887309
79887309
79887309
79887309
79887308
79887308
79887307
79887306
79887305
stdout
copy 
$798873.22 for 1 year(s)
$798873.21 for 1 year(s)
$798873.20 for 1 year(s)
$798873.19 for 1 year(s)
$798873.18 for 2 year(s)
$798873.17 for 1 year(s)
$798873.16 for 2 year(s)
$798873.15 for 1 year(s)
$798873.14 for 2 year(s)
$798873.13 for 1 year(s)
$798873.12 for 4 year(s)
$798873.11 for 1 year(s)
$798873.10 for 1 year(s)
$798873.09 for 1 year(s)
$798873.08 for 3 year(s)
$798873.07 for 1 year(s)
$798873.06 for 1 year(s)
$798873.05 for 1 year(s)
$798873.04 for 1 year(s)
$798873.03 for 1 year(s)
$798873.02 for 2 year(s)
$798873.01 for 2 year(s)
$798873.00 for 1 year(s)
$798872.99 for 1 year(s)
$798872.98 for 1 year(s)
https://ideone.com/nvucrj
CT S02E01 B
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!