fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty