problem.txt (1555B)
1 - Alice and Bob are playing the Rock, Scissors, Paper game. 2 3 - It is given that the game consists of exactly x+y+z 4 - rounds. Also, Bob knows that Alice will play Rock exactly x 5 - times, Scissors exactly y 6 - times, and Paper exactly z 7 - times. However, Bob does not know the order of Alice's outcomes. 8 - 9 - Before the game starts, Bob must choose all of his outcomes in advance. Help him find an optimal sequence of x+y+z 10 - outcomes such that, regardless of the order of Alice's outcomes, the number of rounds won by Bob is at least the number of rounds won by Alice. 11 - 12 - It is guaranteed that such a sequence always exists. 13 14 --- 15 16 - given the distribution of plays x,y,z find the optimal approach 17 18 0 0 3 19 20 x,y,z 21 r,p,s 22 23 just play 24 r,r,r 25 26 1 1 2 27 28 r,r,r,r 29 30 because rock beats scisosrs twice (two wins) 31 and then it ties and loses the others. 32 33 1 1 1 34 35 at most 300 steps 36 at most 1000 test cases 37 38 dp? 39 40 we only care about the worst case. basically, we want to match their moves with ours 41 as an example: 42 43 if they have 1,1,1 44 then we want to match their scissors with our paper, their rock with our scissors, etc. 45 46 can we just increase our numbers? 47 48 how? 49 - should we just match on their most common one then? 50 - like we fight against that? 51 - seem no because ties matter in some cases 52 - ? 53 - yes, that's it actually 54 - proof: 55 - contradition: assume they win by matching on their best. this means the antagonist of ours is larger than what we fought. that's not right.