fork download
copy 
  1. // Parasparopagraho Jīvānām
  2.  
  3. #pragma GCC optimize ("O3")
  4. #pragma GCC target ("sse4")
  5.  
  6. #include <bits/stdc++.h>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. #include <ext/pb_ds/assoc_container.hpp>
  9. #include <ext/rope>
  10.  
  11. using namespace  __gnu_pbds ;
  12. using namespace __gnu_cxx ;
  13. using namespace std ; 
  14.  
  15. typedef long long ll ;
  16. typedef long double ldb ;
  17.  
  18. typedef pair<int, int> pii ;
  19. typedef pair<int, ll> pil ;
  20. typedef pair<ll,ll> pll ;
  21.  
  22. typedef vector<int> vi ;
  23. typedef vector<ll> vll ;
  24. typedef vector<pii> vpi ;
  25. typedef vector<pll> vpl ;
  26. typedef vector<pair<ll,int> > vpli ; 
  27. typedef vector<int,pil> edges ;
  28. typedef vector<vi> matrix ; 
  29. typedef priority_queue<int> pqu ; 
  30.  
  31. template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ;
  32.  
  33. #define rep(i,a,b) for (int i = (a); i <= (b); i++)
  34. #define per(i,b,a) for (int i = (b); i >= (a); i--)
  35.  
  36. #define mp make_pair
  37. #define eb emplace_back
  38. #define pb push_back
  39. #define pob pop_back 
  40. #define fi first
  41. #define se second
  42. #define ins insert 
  43. #define bk back
  44. #define con continue 
  45. #define lbd lower_bound 
  46. #define ubd upper_bound 
  47.  
  48. #define sz(x) (int)x.size()
  49. #define all(x) begin(x), end(x)
  50.  
  51. #define pr cout << // I don't like this but my laptop's 'O' key is not functioning well
  52.  
  53. /* Careful when using long long
  54. __builtin_clz(int x) {} //: the number of zeros at the beginning of the number
  55. __builtin_ctz(int x) {} //: the number of zeros at the end of the number
  56. __builtin_popcount(int x) {} //: the number of ones in the number
  57. __builtin_parity(int x) {} //: the parity (even or odd) of the number of ones */
  58.  
  59. const int mod1 = 1000000007 ;
  60. const int mod2 = 998244353 ;
  61. const ll  infl = 4e18 ;
  62. const int infi = 2e9 ;
  63. const int maxn = 5e5 + 5 ;
  64. const int block = 500 ;
  65. const int logn = 60 ;
  66. const int alpha = 27 ;
  67. const ldb pi = acos(-1) ;
  68.  
  69. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) ;
  70. int rng_lr(int a, int b)
  71. {
  72.     int ret ;
  73.     ret = uniform_int_distribution<int>(a, b)(rng) ;
  74.     return ret ;
  75.     // For shuffling use shuffle(all, rng) ; 
  76. }
  77.  
  78. ll modpow(ll a, ll b, int MOD) { ll res = 1 ; while(b) { if(b&1) { res = res*a ; res %= MOD ; } a *= a ; a %= MOD ; b >>= 1 ; } return res%MOD ; }
  79. void upmin(int &a, int b) { if(a < b) { a = b ; } }
  80. void relax(int &a, int b) { if(a > b) { a = b ; } }
  81. ll add(ll a, ll b, int MOD) { a += b ; if(a >= MOD) { a -= MOD ; } return  a ; }
  82. ll sub(ll a, ll b, int MOD) { a -= b ; if(a < 0) { a += MOD ; } return a ; }
  83. ll mul(ll a, ll b, int MOD) { b %= MOD ; a *= b ; a %= MOD ; return a ; }
  84. ll inverse(ll a, ll MOD) { a = modpow(a, MOD - 2, MOD) ; return a ; }
  85. ll lcm(ll a, ll b) { ll ret ; ll g = __gcd(a, b) ; ret = a/g ; ret = ret*b ; return ret ; }
  86. int icast(char ch) { return int(ch-'a') ; }
  87. void hyn(int a, int b) { if(a == b) cout << "YES\n" ; else cout << "NO\n" ; } 
  88. void pyd(int a, int b) { if(a == b) cout << "First\n" ; else cout << "Second\n" ; } 
  89.  
  90. // Check constraints + overflows + types in typedef 
  91. ldb ev ;
  92. void sol() {
  93. 	ldb dp[61][61][61] ; 
  94. 	rep(i,0,60) {
  95. 	    rep(j,0,60) {
  96. 	        rep(k,0,60) {
  97. 	            dp[i][k][k] = (ldb)0 ; 
  98. 	        }
  99. 	    }
  100. 	}
  101. 	int w, d ; 
  102. 	cin >> w >> d ; 
  103. 	ldb win = (ldb)w ; 
  104. 	ldb dra = (ldb)d ; 
  105. 	ldb den_3 = (ldb)3 ; 
  106. 	dp[1][0][0] = (win + dra)/den_3 ;
  107. 	dp[0][1][0] = (win + dra)/den_3 ;
  108. 	dp[0][0][1] = (win + dra)/den_3 ;
  109. 	int par[60][60][60] ; 
  110. 	par[1][0][0] = 0 ; 
  111. 	par[0][1][0] = 1 ; 
  112. 	par[0][0][1] = 2 ; 
  113. 	rep(i,0,60) {
  114. 		rep(j,0,60-i) {
  115. 			rep(k,0,60-i-j) {
  116. 				if(i == 0 && j == 0 && k == 0) con ; 
  117. 				if(i + j + k > 60) con ; 
  118. 				if(i + j + k == 1) con ; 
  119. 				int t = i + j + k - 1 ;  
  120. 				if(i > 0) {
  121. 					ldb pbr, pbp, pbs ; 
  122. 					pbr = ((ldb)(k))/(ldb)t ; 
  123. 					pbp = ((ldb)(i-1))/(ldb)t ;
  124. 					pbs = ((ldb)(j))/(ldb)t ; 
  125. 					ldb exp_val = pbs*win + pbr*dra + dp[i-1][j][k] ;
  126. 				    if(dp[i][j][k] < exp_val) {
  127. 				    	dp[i][j][k] = exp_val ; 
  128. 				    	par[i][j][k] = 0 ; 
  129. 				    } 
  130. 				}
  131. 				if(j > 0) {
  132. 					ldb pbr, pbp, pbs ; 
  133. 					pbr = ((ldb)(k))/(ldb)t ; 
  134. 					pbp = ((ldb)(i))/(ldb)t ;
  135. 					pbs = ((ldb)(j-1))/(ldb)t ; 
  136. 					ldb exp_val = pbr*win + pbp*dra +dp[i][j-1][k] ;
  137. 				    if(dp[i][j][k] < exp_val) {
  138. 				    	dp[i][j][k] = exp_val ; 
  139. 				    	par[i][j][k] = 1 ; 
  140. 				    } 
  141. 				}
  142. 				if(k > 0) {
  143. 					ldb pbr, pbp, pbs ; 
  144. 					pbr = ((ldb)(k-1))/(ldb)t ; 
  145. 					pbp = ((ldb)(i))/(ldb)t ;
  146. 					pbs = ((ldb)(j))/(ldb)t ; 
  147. 					ldb exp_val = pbp*win + pbs*dra + dp[i][j][k-1] ;
  148. 				    if(dp[i][j][k] < exp_val) {
  149. 				    	dp[i][j][k] = exp_val ; 
  150. 				    	par[i][j][k] = 2 ; 
  151. 				    } 
  152. 				}
  153. 			}
  154. 		}
  155. 	}
  156. 	int ni, nj, nk ; 
  157. 	ldb mx = (ldb)0 ; 
  158. 	rep(i,0,60) {
  159. 		rep(j,0,60-i) {
  160. 			rep(k,0,60-i-j) {
  161. 				if(i + j + k == 60) {
  162. 					if(dp[i][j][k] > mx) {
  163. 						mx = dp[i][j][k] ; 
  164. 						ni = i ; 
  165. 						nj = j ; 
  166. 						nk = k ; 
  167. 					}
  168. 				}
  169. 			}
  170. 		}
  171. 	}
  172.         ev = ev + dp[ni][nj][nk] ;
  173. 	string res ; 
  174. //	pr ni << " " << nj << " " << nk << endl ; 
  175. 	while(sz(res) < 60) {
  176. 		if(par[ni][nj][nk] == 0) {
  177. 			ni-- ; 
  178. 			res.pb('R') ; 
  179. 		}
  180. 		if(par[ni][nj][nk] == 1) {
  181. 			nj-- ; 
  182. 			res.pb('P') ; 
  183. 		}
  184. 		if(par[ni][nj][nk] == 2) {
  185. 			nk-- ; 
  186. 			res.pb('S') ; 
  187. 		}
  188. 	}
  189.         pr res << "\n" ; 
  190. }
  191. int main() 
  192. {
  193.     ios::sync_with_stdio(false) ;
  194.     cin.tie(NULL) ;
  195.     int tc ; 
  196.     cin >> tc ; 
  197.     int rev ; 
  198.     cin >> rev ; 
  199.     ev = (ldb)0 ; 
  200.     rep(i,1,tc) {
  201.     	pr "Case #" << i << ": " ; 
  202.     	sol() ;  
  203.     }
  204.    // pr ev << "\n" ; 
  205.  
  206.  
  207.     return 0 ; 
  208. }
Success #stdin #stdout 0s 5596KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iedIGo
language:
C++14 (gcc 8.3)
created:
2 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!