Universal Cup Judging System

Universal Cup

Límite de tiempo: 2.0 s Límite de memoria: 256 MB Puntuación total: 100 Hackeable ✓
Estadísticas

Beskrivning

Du spelar ett äventyrsspel. Som magiker måste du använda magi för att hantera flera fiender framför dig. Varje fiende har en nivå, vilket är ett heltal mellan $1$ och $n$. En fiende på nivå $i$ har $2^{i-1}$ hälsopoäng.

Du kan använda två sorters trollformler:

  • Själsband (Soul Link): förbrukar $m$ mana och applicerar effekten "Själsband" på en fiende. Denna effekt varar tills fienden dör.
  • Attack (Attack): förbrukar $1$ mana och gör $1$ skada på alla fiender med effekten "Själsband", dvs. minskar deras hälsa med $1$. Så fort en fiendes hälsa sjunker till $0$ dör fienden, och du får $m$ mana som belöning.

Bland fienderna framför dig finns det $a_i$ fiender på nivå $i$. Du får använda de två trollformlerna hur många gånger som helst, men din mana får aldrig vara mindre än $0$. Vad är den minsta startmana du behöver för att besegra alla fiender?

Indata

Den första raden innehåller ett heltal $T$ ($1 \le T \le 500$), som anger antalet testfall.

För varje testfall innehåller den första raden två heltal $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$), som representerar den maximala fiendenivån respektive manakostnaden för Själsband.

Den andra raden innehåller $n$ positiva heltal. Det $i$-te heltalet $a_i$ anger antalet fiender på nivå $i$.

För varje testfall garanteras det att $0 \le a_i \le 10^9$ och $\sum_{i=1}^n a_i > 0$.

Utdata

För varje testfall, skriv ut en rad som innehåller ett heltal som anger den minsta startmana som krävs för att besegra alla fiender.

Exempel

Indata 1

2
5 7
5 2 4 1 2
6 4
1 1 4 5 1 4

Utdata 1

34
48

Anmärkning

Förklaring till det första testfallet:

Från början finns det 14 fiender med hälsovärdena 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16.

Med 34 mana från början, applicera först Själsband på fienderna med hälsa 1, 1, 1, 1, vilket lämnar 6 mana kvar.

Attackera en gång, så blir fiendernas hälsa 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16. Fyra fiender dör, vilket lämnar 33 mana kvar.

Applicera Själsband på fienderna med hälsa 1, 2, 2, 4, vilket lämnar 5 mana kvar.

Attackera en gång, så blir fiendernas hälsa 0, 1, 1, 3, 4, 4, 4, 8, 16, 16. En fiende dör, vilket lämnar 11 mana kvar.

Applicera Själsband på fienden med hälsa 4, vilket lämnar 4 mana kvar.

Attackera en gång, så blir fiendernas hälsa 0, 0, 2, 3, 4, 4, 8, 16, 16. Två fiender dör, vilket lämnar 17 mana kvar.

Applicera Själsband på fienderna med hälsa 4, 16, vilket lämnar 3 mana kvar.

Attackera två gånger, så blir fiendernas hälsa 0, 1, 2, 4, 8, 14, 16. En fiende dör, vilket lämnar 8 mana kvar.

Applicera Själsband på fienden med hälsa 8, vilket lämnar 1 mana kvar.

Attackera en gång, så blir fiendernas hälsa 0, 1, 4, 7, 13, 16. En fiende dör, vilket lämnar 7 mana kvar.

Attackera en gång, så blir fiendernas hälsa 0, 4, 6, 12, 16. En fiende dör, vilket lämnar 13 mana kvar.

Applicera Själsband på fienden med hälsa 4, vilket lämnar 6 mana kvar.

Attackera fyra gånger, så blir fiendernas hälsa 0, 2, 8, 16. En fiende dör, vilket lämnar 9 mana kvar.

Applicera Själsband på fienden med hälsa 16, vilket lämnar 2 mana kvar.

Attackera två gånger, så blir fiendernas hälsa 0, 6, 14. En fiende dör, vilket lämnar 7 mana kvar.

Attackera sex gånger, så blir fiendernas hälsa 0, 8. En fiende dör, vilket lämnar 8 mana kvar.

Attackera åtta gånger, så dör alla fiender, vilket lämnar 0 mana kvar.

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.