Universal Cup Judging System

Universal Cup

시간 제한: 2.0 s 메모리 제한: 256 MB 총점: 100 해킹 가능 ✓
통계

Lýsing

Þú ert að spila ævintýraleik. Sem galdramaður þarftu að nota galdra til að ráða niðurlögum nokkurra óvina fyrir framan þig. Hver óvinur hefur stig, sem er heiltala á bilinu $1$ til $n$. Óvinur á stigi $i$ hefur $2^{i-1}$ lífstig.

Þú getur notað tvær tegundir galdra:

  • Sálartenging (Soul Link): eyðir $m$ galdraorku (mana) og leggur áhrifin „Sálartenging“ á einn óvin. Þessi áhrif vara þar til sá óvinur deyr.
  • Árás (Attack): eyðir $1$ galdraorku og veldur $1$ í skaða á alla óvini sem eru með áhrifin „Sálartenging“, þ.e.a.s. lækkar lífstig þeirra um $1$. Um leið og lífstig einhvers óvinar fer niður í $0$ deyr sá óvinur og þú færð $m$ galdraorku í verðlaun.

Meðal óvinanna fyrir framan þig eru $a_i$ óvinir á stigi $i$. Þú mátt nota galdrana tvo hversu oft sem er, en á engum tímapunkti má galdraorkan þín vera minni en $0$. Hver er lágmarks upphafsgaldraorka sem þú þarft til að sigra alla óvinina?

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 500$), sem táknar fjölda prófunartilfella.

Fyrir hvert prófunartilfelli inniheldur fyrsta línan tvær heiltölur $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$), sem tákna hámarksstig óvina og galdraorkukostnað Sálartengingar, í sömu röð.

Önnur línan inniheldur $n$ jákvæðar heiltölur. $i$-ta heiltalan $a_i$ táknar fjölda óvina á stigi $i$.

Fyrir hvert prófunartilfelli er tryggt að $0 \le a_i \le 10^9$ og $\sum_{i=1}^n a_i > 0$.

Úttak

Fyrir hvert prófunartilfelli skal prenta eina línu sem inniheldur heiltölu sem táknar lágmarks upphafsgaldraorku sem þarf til að sigra alla óvinina.

Dæmi

Inntak 1

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

Úttak 1

34
48

Athugasemd

Skýring á fyrsta prófunartilfellinu:

Í upphafi eru 14 óvinir með lífstigin 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16.

Með 34 galdraorku í upphafi er Sálartenging fyrst lögð á óvinina með lífstig 1, 1, 1, 1, og þá eru 6 galdraorka eftir.

Gerðu árás einu sinni, og lífstig óvinanna verða 0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16. Fjórir óvinir deyja, og 33 galdraorka er eftir.

Leggðu Sálartengingu á óvinina með lífstig 1, 2, 2, 4, og þá eru 5 galdraorka eftir.

Gerðu árás einu sinni, og lífstig óvinanna verða 0, 1, 1, 3, 4, 4, 4, 8, 16, 16. Einn óvinur deyr, og 11 galdraorka er eftir.

Leggðu Sálartengingu á óvininn með lífstig 4, og þá eru 4 galdraorka eftir.

Gerðu árás einu sinni, og lífstig óvinanna verða 0, 0, 2, 3, 4, 4, 8, 16, 16. Tveir óvinir deyja, og 17 galdraorka er eftir.

Leggðu Sálartengingu á óvinina með lífstig 4, 16, og þá eru 3 galdraorka eftir.

Gerðu árás tvisvar, og lífstig óvinanna verða 0, 1, 2, 4, 8, 14, 16. Einn óvinur deyr, og 8 galdraorka er eftir.

Leggðu Sálartengingu á óvininn með lífstig 8, og þá er 1 galdraorka eftir.

Gerðu árás einu sinni, og lífstig óvinanna verða 0, 1, 4, 7, 13, 16. Einn óvinur deyr, og 7 galdraorka er eftir.

Gerðu árás einu sinni, og lífstig óvinanna verða 0, 4, 6, 12, 16. Einn óvinur deyr, og 13 galdraorka er eftir.

Leggðu Sálartengingu á óvininn með lífstig 4, og þá eru 6 galdraorka eftir.

Gerðu árás fjórum sinnum, og lífstig óvinanna verða 0, 2, 8, 16. Einn óvinur deyr, og 9 galdraorka er eftir.

Leggðu Sálartengingu á óvininn með lífstig 16, og þá eru 2 galdraorka eftir.

Gerðu árás tvisvar, og lífstig óvinanna verða 0, 6, 14. Einn óvinur deyr, og 7 galdraorka er eftir.

Gerðu árás sex sinnum, og lífstig óvinanna verða 0, 8. Einn óvinur deyr, og 8 galdraorka er eftir.

Gerðu árás átta sinnum, og allir óvinir deyja, og 0 galdraorka er eftir.

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.