Rock Paper Scissors Solution Google Kickstart 2021
Problem
You and your friend like to play Rock Paper Scissors. Each day you play exactly 6060 rounds and at the end of each day, you tally up the score from these 6060 rounds.
During each round, without any knowledge of the other person’s choice, you each make your choice. Then, you both reveal the choice you made and determine your score. Rock wins over Scissors, Scissors wins over Paper, and Paper wins over Rock. Let R represent Rock, P represent Paper, and S represent Scissors. Every day you both agree on values WW and EE. If your choice wins, you get WW points. If you and your friend both pick the same choice, you get EE points. If your choice loses, you get nothing.
By accident, you see your friend’s strategy written in an open notebook on a desk one day. Your friend keeps track of how many times you have chosen R, P, and S so far during one day. Let AiAi be your choice of R, P, or S on round ii, while BiBi is your friend’s choice on the same round. Let riri be the number of times Aj=Aj= R for 1≤j≤(i−1)1≤j≤(i−1). Similarly, let pipi and sisi be the total number of times you have chosen P and S, respectively, prior to round ii.
On round 11 of each day, i=1i=1 and r1=s1=p1=0r1=s1=p1=0, and your friend plays randomly due to the lack of information (i.e. your friend chooses each option with probablity 1/31/3). On every subsequent round, your friend decides BiBi by choosing R with probability Pr[Pr[R]=si/(i−1)]=si/(i−1), P with probability Pr[Pr[P]=ri/(i−1)]=ri/(i−1), and S with probability Pr[Pr[S]=pi/(i−1)]=pi/(i−1). This strategy is adaptive and tough to beat!
You are going on vacation for the next TT days. You must leave your assistant with instructions on what choice to pick each round each day. Let integer XX be the average reward you are aiming for in this game after TT days. Given WW and EE (different values for different days), provide your instructions as a string of 6060 characters, ordered from round 11 to round 6060. Each character represents your choice for the corresponding round. Your goal is to choose your set of instructions so that the average expected value of the reward across all the days of your gameplay is at least XX. Note that you can choose different instructions for different values of WW and EE.
Input
The first line of the input gives the number of days, TT. The second line contains an integer XX, your targeted average reward after these TT days. Then the description of TT days follows. Each day is described as two integers WW and EE. WW is how much you get if your choice wins for each round that day. EE is how much you get for each round when your choice is the same as your friend’s choice.
All the tests (except the sample test below) are generated as follows. We choose 5050 different values GG between 55 and 9595 (with uniform distribution). Then for each of these values, there will be 44 days, with WW equal to 10×G10×G and EE equal to W,W2,W10W,W2,W10, and 00. Do not assume anything about the order of these days.
Output
For each day, output one line containing Case #xx: A1A2…A60A1A2…A60, where xx is the day number (starting from 1) and AiAi is your choice of R, P, or S on the ii-th round of the game. There should be no spaces between the choices.
The list of choices should result in an expected value that is greater than or equal to XX on average after TT days. There may be multiple solutions for a test case. If so, you may output any one of them. It is guaranteed that for given XX a solution exists.
Limits
Time limit: 40 seconds.
Memory limit: 1 GB.
T=200T=200 (for all tests except the sample where T=2T=2).
50≤W≤95050≤W≤950.
0≤E≤W0≤E≤W and EE is one of W,W2,W10W,W2,W10, or 00.
Each day you play exactly 60 rounds.
Test Set 1
X=14600X=14600.
Test Set 2
X=15500X=15500.
Test Set 3
X=16400X=16400.
Sample
Sample Input
2 30 60 0 60 60
Sample Output
Case #1: RSRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR Case #2: PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
In this sample test our targeted (average) reward across all T=2T=2 days is 3030.
For the first day, since W=60W=60, you can reach the total target by winning at least once. One possible strategy is to just get to that single win.
- On round 11, you choose A1=A1=
R. You have an equal chance of a win, a tie, or a loss, giving you an expected value of 2020. - On round 22, r2=1r2=1 and p2=s2=0p2=s2=0. Your friend’s probability of choosing
Pis Pr[Pr[P]=r2/1=1]=r2/1=1, which guarantees your friend’s choice B2=B2=P. - If you choose A2=A2=
S, you are guaranteed a win, giving you a score of 6060 for round 22. - Regardless of what you choose for all following rounds in the game, your expected value after just two rounds is 20+60=8020+60=80, which is enough to reach our target.
Moreover, as we already will have the average across all 2 days at least 802=40≥X=30802=40≥X=30, for the second day we can use any strategy.
Note that this is not a unique solution. As long as the average expected score is ≥30≥30, other outputs would also be accepted.
Also Read:
- Binary Operator Solution Google Kickstart 2021
- Alien Generator Solution Google Kickstart 2021
- Smaller Strings Solution Google Kickstart 2021
Solution:
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<string>
#include<algorithm>
#include<iostream>
#include<bitset>
#include<functional>
#include<numeric>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<cmath>
#include<iomanip>
#include<random>
#include<ctime>
#include<complex>
using namespace std;
typedef long long LL;
typedef double D;
#define all(v) (v).begin(), (v).end()
mt19937 gene(233);
typedef complex<double> Complex;
#define fi first
#define se second
#define ins insert
#define pb push_back
inline char GET_CHAR(){
const int maxn = 131072;
static char buf[maxn],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,maxn,stdin),p1==p2)?EOF:*p1++;
}
inline int getInt() {
int res(0);
char c = getchar();
while(c < '0') c = getchar();
while(c >= '0') {
res = res * 10 + (c - '0');
c = getchar();
}
return res;
}
inline LL fastpo(LL x, LL n, LL mod) {
LL res(1);
while(n) {
if(n & 1) {
res = res * (LL)x % mod;
}
x = x * (LL) x % mod;
n /= 2;
}
return res;
}
LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
inline string itoa(int x, int width = 0) {
string res;
if(x == 0) res.push_back('0');
while(x) {
res.push_back('0' + x % 10);
x /= 10;
}
while((int)res.size() < width) res.push_back('0');
reverse(res.begin(), res.end());
return res;
}
const int _B = 131072;
char buf[_B];
int _bl = 0;
inline void flush() {
fwrite(buf, 1, _bl, stdout);
_bl = 0;
}
__inline void _putchar(char c) {
if(_bl == _B) flush();
buf[_bl++] = c;
}
inline void print(LL x, char c) {
static char tmp[20];
int l = 0;
if(!x) tmp[l++] = '0';
else {
while(x) {
tmp[l++] = x % 10 + '0';
x /= 10;
}
}
for(int i = l - 1; i >= 0; i--) _putchar(tmp[i]);
_putchar(c);
}
struct P {
D x, y;
};
int w, e;
const int N = 300033;
const int LOG = 20;
const int mod = 1e9 + 7;
const int inf = 1e9 + 7;
int n, m;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
D dp[63][63][63];
int u[63][63][63];
int main() {
int t, x;
scanf("%d%d", &t, &x);
D sum = 0;
for(int qq = 1; qq <= t; qq++) {
scanf("%d%d", &w, &e);
/*w = v[(qq - 1) / 4] * 10;
sv += w / 10;
cout << (qq - 1) / 4 << endl;
e = qq % 4 == 1 ? w : qq % 4 == 2 ? w/ 2 : qq % 4 == 3 ? w / 10 : 0;*/
int c[3];
for(int sum = 60; sum >= 0; sum--) {
for(c[0] = 0; c[0] <= sum; c[0]++) {
for(c[1] = 0; c[0] + c[1] <= sum; c[1]++) {
c[2] = sum - c[0] - c[1];
if(sum == 60) {
dp[c[0]][c[1]][c[2]] = 0;
continue;
}
if(sum == 0) {
dp[0][0][0] = dp[1][0][0] + w / 3. + e / 3.;
u[0][0][0] = 0;
continue;
}
D mx = -1;
int mxd = -1;
for(int d = 0; d < 3; d++) {
D tmp = 0;
for(int f = 0; f < 3; f++) {
if((d + 1) % 3 == f) {
tmp += (c[(f + 1) % 3]) / (D)sum * w;
}else if(d == f) {
tmp += (c[(f + 1) % 3]) / (D)sum * e;
}
}
int nwc[3];
memcpy(nwc, c, sizeof(c));
nwc[d]++;
tmp += dp[nwc[0]][nwc[1]][nwc[2]];
if(tmp > mx) {
mx = tmp;
mxd = d;
}
}
dp[c[0]][c[1]][c[2]] = mx;
u[c[0]][c[1]][c[2]] = mxd;
}
}
}
memset(c, 0, sizeof(c));
printf("Case #%d: ", qq);
for(int i = 1; i <= 60; i++) {
printf("%c", u[c[0]][c[1]][c[2]] == 0 ? 'R' : u[c[0]][c[1]][c[2]] == 1 ? 'S' : 'P');
c[u[c[0]][c[1]][c[2]]]++;
}
sum += dp[0][0][0];
printf("\n");
}
/*printf("%f\n", sum / 200.);
printf("%f\n", sv / 200.);
printf("%f\n", sum / 200 / (sv / 200) * 50);*/
}Rock Paper Scissors Solution Google Kickstart 2021
