Alice and Bob are playing a board game.On their turn, a player must roll 𝑁N standard 66-sided dice, and their action will be determined by the sum of values on the top faces of the 𝑁N dice.On a certain turn of Alice, she rolls the dice and obtains the sequence of values 𝐴1,𝐴2,…,𝐴𝑁A 1 ,A 2 ,…,A N on the top faces.However, Bob isn't paying attention, allowing Alice to cheat a little!Alice can choose a die, and flip it - so the opposite face is upward.Note that these are standard 66-sided dice, so the sum of values on opposite faces is 77. That is:11 is opposite to 66.22 is opposite to 55.33 is opposite to 44.So as to not make Bob suspicious, Alice can perform this flipping operation at most 𝐾K times.What's the maximum score (i.e, sum of values of top faces of the dice) she can obtain?Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of two lines of input.The first line of each test case contains two space-separated integers 𝑁N and 𝐾K — the number of dice and the number of times Alice can flip dice.The second line contains 𝑁N space-separated integers 𝐴1,𝐴2,…,𝐴𝑁A 1 ,A 2 ,…,A N — the initial values of the dice.Output FormatFor each test case, output on a new line the maximum score Alice can obtain if she flips a die at most 𝐾K times.Constraints1≤𝑇≤1051≤T≤10 5 1≤𝑁≤2⋅1051≤N≤2⋅10 5 1≤𝐾≤𝑁1≤K≤N1≤𝐴𝑖≤61≤A i ≤6The sum of 𝑁N over all test cases won't exceed 2⋅1052⋅10 5 .Sample 1:InputOutput42 13 44 23 4 4 55 31 2 3 2 16 26 5 4 3 2 1
Question
Alice and Bob are playing a board game.On their turn, a player must roll 𝑁N standard 66-sided dice, and their action will be determined by the sum of values on the top faces of the 𝑁N dice.On a certain turn of Alice, she rolls the dice and obtains the sequence of values 𝐴1,𝐴2,…,𝐴𝑁A 1 ,A 2 ,…,A N on the top faces.However, Bob isn't paying attention, allowing Alice to cheat a little!Alice can choose a die, and flip it - so the opposite face is upward.Note that these are standard 66-sided dice, so the sum of values on opposite faces is 77. That is:11 is opposite to 66.22 is opposite to 55.33 is opposite to 44.So as to not make Bob suspicious, Alice can perform this flipping operation at most 𝐾K times.What's the maximum score (i.e, sum of values of top faces of the dice) she can obtain?Input FormatThe first line of input will contain a single integer 𝑇T, denoting the number of test cases.Each test case consists of two lines of input.The first line of each test case contains two space-separated integers 𝑁N and 𝐾K — the number of dice and the number of times Alice can flip dice.The second line contains 𝑁N space-separated integers 𝐴1,𝐴2,…,𝐴𝑁A 1 ,A 2 ,…,A N — the initial values of the dice.Output FormatFor each test case, output on a new line the maximum score Alice can obtain if she flips a die at most 𝐾K times.Constraints1≤𝑇≤1051≤T≤10 5 1≤𝑁≤2⋅1051≤N≤2⋅10 5 1≤𝐾≤𝑁1≤K≤N1≤𝐴𝑖≤61≤A i ≤6The sum of 𝑁N over all test cases won't exceed 2⋅1052⋅10 5 .Sample 1:InputOutput42 13 44 23 4 4 55 31 2 3 2 16 26 5 4 3 2 1
Solution
The problem is asking to find the maximum possible sum Alice can get by flipping the dice at most K times.
Here are the steps to solve this problem:
-
First, we need to understand that the maximum value we can get from a die is 6. So, if we have a die with a value less than 4, we can flip it to get a higher value. For example, if we have a die with a value of 1, we can flip it to get a value of 6.
-
We start by sorting the array of dice values in ascending order. This way, we can start flipping the dice with the lowest values first.
-
We then iterate through the array, and for each die, we check if we can flip it to get a higher value and if we still have flips left. If both conditions are met, we flip the die and subtract one from our remaining flips.
-
We continue this process until we have used all our flips or we have iterated through all the dice.
-
Finally, we calculate the sum of the dice values and return it as the maximum possible sum Alice can get.
This algorithm ensures that we always flip the dice with the lowest values first, maximizing the increase in the sum. It has a time complexity of O(N log N) due to the sorting, where N is the number of dice.
Similar Questions
Below is given a board game that Honey and Sunny are playing. They both start from the box showing 'start'. They throw a dice that can show a number from 1 to 6. On the basis of the number that has come on dice, the player who has thrown the dice moves that many steps in the direction as represented by arrows. The boxes on which a player reaches during the game, the numbers on those boxes are added together to get the score of that player. Player reaching box representing 'end' first wins the game. If none of them is able to reach the box representing 'end' in 6 turns, the game results in a draw. Honey has the first turn.If in his first three turns, Honey gets 2, 3 and 6 on the dice, respectively, then what would be his score after three turns?
A pair of dice is thrown once, and the sum of the numbers on the face of the dice is recorded. (Let X = sum of the two numbers). Below is a table with all the possible outcomes: 1;1 1;2 1;3 1;4 1;5 1;6 2;1 2;2 2;3 2;4 2;5 2;6 3;1 3;2 3;3 3;4 3;5 3;6 4;1 4;2 4;3 4;4 4;5 4;6 5;1 5;2 5;3 5;4 5;5 5;6 6;1 6;2 6;3 6;4 6;5 6;6 Calculate P (X =13) a. 35/36 b. 32/36 c. 4/36 d. 3/36 e. None of the above calculate P(X= 13), which of the above is correct?
A friend offers you a game in which you roll two 8-sided die.You get $10 if the sum of the die is 12. 48, 84, 57, 75, 66You get $6 if the sum of the die is 10. 28, 82, 37, 73, 46, 64, 55You get $3 if the sum of the die is 8. 17, 71, 26, 62, 35, 53, 44You get $1 if the sum of the die is 4. 13, 31, 22Otherwise, you pay your friend $2.Is it a fair game?
There are n𝑛 coins on the table forming a circle, and each coin is either facing up or facing down. Alice and Bob take turns to play the following game, and Alice goes first.In each operation, the player chooses a facing-up coin, removes the coin, and flips the two coins that are adjacent to it. If there are only two coins left, then one will be removed and the other won't be flipped (as it would be flipped twice). If there is only one coin left, no coins will be flipped. If there are no facing-up coins, the player loses.Decide who will win the game if they both play optimally. It can be proved that the game will end in a finite number of operations, and one of them will win.InputEach test contains multiple test cases. The first line contains the number of test cases t𝑡 (1≤t≤1001≤𝑡≤100). The description of the test cases follows.The first line of each test case contains only one positive integer n𝑛 (1≤n≤1001≤𝑛≤100), representing the number of the coins.A string s𝑠 of length n𝑛 follows on the second line of each test case, containing only "U" and "D", representing that each coin is facing up or facing down.OutputFor each test case, print "YES" if Alice will win the game, and "NO" otherwise.You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.ExampleinputCopy35UUDUD5UDDUD2UUoutputCopyYESNONO
If you roll a 6-sided die 6 times, what is the best prediction possible for the number of times you will roll an even number?
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.