[Solution] Good Key, Bad Key Codeforces Solution

[Solution] Good Key, Bad Key Codeforces Solution | Solution Codeforces

Good Key, Bad Key solution codeforces – There are 𝑛n chests. The 𝑖i-th chest contains 𝑎𝑖ai coins. You need to open all 𝑛n chests in order from chest 11 to chest 𝑛n.

[Solution] Good Key, Bad Key solution codeforces

There are two types of keys you can use to open a chest:

a good key, which costs 𝑘k coins to use;

a bad key, which does not cost any coins, but will halve all the coins in each unopened chest, including the chest it is about to open. The halving operation will round down to the nearest integer for each chest halved. In other words using a bad key to open chest 𝑖i will do 𝑎𝑖=⌊𝑎𝑖2⌋ai=⌊ai2⌋, 𝑎𝑖+1=⌊𝑎𝑖+12⌋,…,𝑎𝑛=⌊𝑎𝑛2⌋ai+1=⌊ai+12⌋,…,an=⌊an2⌋;

any key (both good and bad) breaks after a usage, that is, it is a one-time use.

You need to use in total 𝑛n keys, one for each chest. Initially, you have no coins and no keys. If you want to use a good key, then you need to buy it.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

During the process, you are allowed to go into debt; for example, if you have 11 coin, you are allowed to buy a good key worth 𝑘=3k=3 coins and your balance will become −2−2 coins.

Find the maximum number of coins you can have after opening all 𝑛n chests in order from chest 11 to chest 𝑛n.

[Solution] Good Key, Bad Key solution codeforces

The first line contains a single integer 𝑡t (1≤𝑡≤1041≤t≤104) — the number of test cases.

YES or YES? Codeforces Solution

ICPC Balloons Codeforces Solution

Cypher Codeforces Solution

Double Strings CodeForces Solution

Mirror Grid Codeforces Solution

Yet Another Problem About Pairs Satisfying an Inequality Codeforces Solution

Good Key, Bad Key Codeforces Solution

The first line of each test case contains two integers 𝑛n and 𝑘k (1≤𝑛≤1051≤n≤105; 0≤𝑘≤1090≤k≤109) — the number of chests and the cost of a good key respectively.

The second line of each test case contains 𝑛n integers 𝑎𝑖ai (0≤𝑎𝑖≤1090≤ai≤109)  — the amount of coins in each chest.

The sum of 𝑛n over all test cases does not exceed 105105.

Output

For each test case output a single integer  — the maximum number of coins you can obtain after opening the chests in order from chest 11 to chest 𝑛n.

Please note, that the answer for some test cases won’t fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

[Solution] Good Key, Bad Key solution codeforces

Example

input

Copy

5

4 5

10 10 3 1

1 2

1

3 12

10 10 29

12 51

5 74 89 45 18 69 67 67 11 96 23 59

2 57

85 60

output

Copy

11

0

13

60

58

[Solution] Good Key, Bad Key solution codeforces

In the first test case, one possible strategy is as follows:

Buy a good key for 55 coins, and open chest 11, recieving 1010 coins. Your current balance is 0+10−5=50+10−5=5 coins.

Buy a good key for 55 coins, and open chest 22, recieving 1010 coins. Your current balance is 5+10−5=105+10−5=10 coins.

Use a bad key and open chest 33. As a result of using a bad key, the number of coins in chest 33 becomes ⌊32⌋=1⌊32⌋=1, and the number of coins in chest 44 becomes ⌊12⌋=0⌊12⌋=0. Your current balance is 10+1=1110+1=11.

Use a bad key and open chest 44. As a result of using a bad key, the number of coins in chest 44 becomes ⌊02⌋=0⌊02⌋=0. Your current balance is 11+0=1111+0=11.

At the end of the process, you have 1111 coins, which can be proven to be maximal.