Universal Cup Judging System

Universal Cup

実行時間制限: 2.0 s メモリ制限: 256 MB 満点: 100 ハック可能 ✓
統計

Beskrivelse

Du spiller et eventyrspill. Som magiker må du bruke magi for å håndtere flere fiender foran deg. Hver fiende har et nivå, som er et heltall mellom $1$ og $n$. En fiende på nivå $i$ har $2^{i-1}$ helsepoeng.

Du kan bruke to typer trylleformler:

  • Sjelebånd (Soul Link): bruker $m$ mana og påfører effekten «Sjelebånd» på én fiende. Denne effekten varer til fienden dør.
  • Angrep (Attack): bruker $1$ mana og gjør $1$ skade på alle fiender med effekten «Sjelebånd», dvs. reduserer helsen deres med $1$. Så snart en fiendes helse faller til $0$, dør fienden, og du får $m$ mana som belønning.

Blant fiendene foran deg er det $a_i$ fiender på nivå $i$. Du kan bruke de to trylleformlene så mange ganger du vil, men manaen din kan ikke på noe tidspunkt være mindre enn $0$. Hva er den minimale startmanaen du trenger for å beseire alle fiendene?

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 500$), som angir antallet testtilfeller.

For hvert testtilfelle inneholder den første linjen to heltall $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$), som representerer henholdsvis det maksimale fiendenivået og manakostnaden for Sjelebånd.

Den andre linjen inneholder $n$ positive heltall. Det $i$-te heltallet $a_i$ angir antallet fiender på nivå $i$.

For hvert testtilfelle garanteres det at $0 \le a_i \le 10^9$ og $\sum_{i=1}^n a_i > 0$.

Utdata

For hvert testtilfelle skal du skrive ut én linje som inneholder et heltall som angir den minimale startmanaen som kreves for å beseire alle fiendene.

Eksempler

Inndata 1

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

Utdata 1

34
48

Merk

Forklaring til det første testtilfellet:

Til å begynne med er det 14 fiender med helseverdiene 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16.

Med 34 mana til å begynne med, bruk først Sjelebånd på fiendene med helse 1, 1, 1, 1, slik at det gjenstår 6 mana.

Angrip én gang, så blir fiendenes helse 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16. Fire fiender dør, og det gjenstår 33 mana.

Bruk Sjelebånd på fiendene med helse 1, 2, 2, 4, slik at det gjenstår 5 mana.

Angrip én gang, så blir fiendenes helse 0, 1, 1, 3, 4, 4, 4, 8, 16, 16. Én fiende dør, og det gjenstår 11 mana.

Bruk Sjelebånd på fienden med helse 4, slik at det gjenstår 4 mana.

Angrip én gang, så blir fiendenes helse 0, 0, 2, 3, 4, 4, 8, 16, 16. To fiender dør, og det gjenstår 17 mana.

Bruk Sjelebånd på fiendene med helse 4, 16, slik at det gjenstår 3 mana.

Angrip to ganger, så blir fiendenes helse 0, 1, 2, 4, 8, 14, 16. Én fiende dør, og det gjenstår 8 mana.

Bruk Sjelebånd på fienden med helse 8, slik at det gjenstår 1 mana.

Angrip én gang, så blir fiendenes helse 0, 1, 4, 7, 13, 16. Én fiende dør, og det gjenstår 7 mana.

Angrip én gang, så blir fiendenes helse 0, 4, 6, 12, 16. Én fiende dør, og det gjenstår 13 mana.

Bruk Sjelebånd på fienden med helse 4, slik at det gjenstår 6 mana.

Angrip fire ganger, så blir fiendenes helse 0, 2, 8, 16. Én fiende dør, og det gjenstår 9 mana.

Bruk Sjelebånd på fienden med helse 16, slik at det gjenstår 2 mana.

Angrip to ganger, så blir fiendenes helse 0, 6, 14. Én fiende dør, og det gjenstår 7 mana.

Angrip seks ganger, så blir fiendenes helse 0, 8. Én fiende dør, og det gjenstår 8 mana.

Angrip åtte ganger, så dør alle fiendene, og det gjenstår 0 mana.

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.