Universal Cup Judging System

Universal Cup

Limite de temps : 2.0 s Limite de mémoire : 256 MB Points totaux : 100 Hackable ✓
Statistiques

תיאור

אתם משחקים במשחק הרפתקאות. בתור קוסמים, עליכם להשתמש בקסם כדי להתמודד עם מספר אויבים שמולכם. לכל אויב יש רמה, שהיא מספר שלם בין $1$ ל-$n$. לאויב ברמה $i$ יש $2^{i-1}$ נקודות חיים.

באפשרותכם להשתמש בשני סוגי לחשים:

  • קשר נשמה (Soul Link): צורך $m$ מאנה ומפעיל את אפקט "קשר נשמה" על אויב אחד. אפקט זה נמשך עד שאותו אויב מת.
  • תקיפה (Attack): צורכת $1$ מאנה וגורמת $1$ נזק לכל האויבים שעליהם פועל אפקט "קשר נשמה", כלומר מפחיתה את נקודות החיים שלהם ב-$1$. ברגע שנקודות החיים של אויב כלשהו יורדות ל-$0$, אותו אויב מת, ואתם מקבלים $m$ מאנה כפרס.

בין האויבים שמולכם, ישנם $a_i$ אויבים ברמה $i$. אתם רשאים להשתמש בשני הלחשים מספר כלשהו של פעמים, אך בשום שלב המאנה שלכם אינה יכולה להיות קטנה מ-$0$. מהי כמות המאנה ההתחלתית המינימלית הדרושה לכם כדי להביס את כל האויבים?

קלט

השורה הראשונה מכילה מספר שלם $T$ ($1 \le T \le 500$), המציין את מספר מקרי הבדיקה.

עבור כל מקרה בדיקה, השורה הראשונה מכילה שני מספרים שלמים $n, m$ ($1 \le n \le 30, 1 \le m \le 10^{18}$), המייצגים את הרמה המרבית של האויבים ואת עלות המאנה של קשר נשמה, בהתאמה.

השורה השנייה מכילה $n$ מספרים שלמים חיוביים. המספר השלם ה-$i$, $a_i$, מציין את מספר האויבים ברמה $i$.

עבור כל מקרה בדיקה, מובטח כי $0 \le a_i \le 10^9$ וכן $\sum_{i=1}^n a_i > 0$.

פלט

עבור כל מקרה בדיקה, הדפיסו שורה אחת המכילה מספר שלם, המציין את המאנה ההתחלתית המינימלית הדרושה כדי להביס את כל האויבים.

דוגמאות

קלט 1

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

פלט 1

34
48

הערה

הסבר למקרה הבדיקה הראשון:

בהתחלה יש 14 אויבים, עם ערכי חיים 1, 1, 1, 1, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16.

עם 34 מאנה בהתחלה, תחילה מפעילים קשר נשמה על האויבים עם חיים 1, 1, 1, 1, ונותרות 6 מאנה.

תוקפים פעם אחת, והחיים של האויבים הופכים ל-0, 0, 0, 0, 1, 2, 2, 4, 4, 4, 4, 8, 16, 16. ארבעה אויבים מתים, ונותרות 33 מאנה.

מפעילים קשר נשמה על האויבים עם חיים 1, 2, 2, 4, ונותרות 5 מאנה.

תוקפים פעם אחת, והחיים של האויבים הופכים ל-0, 1, 1, 3, 4, 4, 4, 8, 16, 16. אויב אחד מת, ונותרות 11 מאנה.

מפעילים קשר נשמה על האויב עם חיים 4, ונותרות 4 מאנה.

תוקפים פעם אחת, והחיים של האויבים הופכים ל-0, 0, 2, 3, 4, 4, 8, 16, 16. שני אויבים מתים, ונותרות 17 מאנה.

מפעילים קשר נשמה על האויבים עם חיים 4, 16, ונותרות 3 מאנה.

תוקפים פעמיים, והחיים של האויבים הופכים ל-0, 1, 2, 4, 8, 14, 16. אויב אחד מת, ונותרות 8 מאנה.

מפעילים קשר נשמה על האויב עם חיים 8, ונותרת 1 מאנה.

תוקפים פעם אחת, והחיים של האויבים הופכים ל-0, 1, 4, 7, 13, 16. אויב אחד מת, ונותרות 7 מאנה.

תוקפים פעם אחת, והחיים של האויבים הופכים ל-0, 4, 6, 12, 16. אויב אחד מת, ונותרות 13 מאנה.

מפעילים קשר נשמה על האויב עם חיים 4, ונותרות 6 מאנה.

תוקפים ארבע פעמים, והחיים של האויבים הופכים ל-0, 2, 8, 16. אויב אחד מת, ונותרות 9 מאנה.

מפעילים קשר נשמה על האויב עם חיים 16, ונותרות 2 מאנה.

תוקפים פעמיים, והחיים של האויבים הופכים ל-0, 6, 14. אויב אחד מת, ונותרות 7 מאנה.

תוקפים שש פעמים, והחיים של האויבים הופכים ל-0, 8. אויב אחד מת, ונותרות 8 מאנה.

תוקפים שמונה פעמים, וכל האויבים מתים, ונותרות 0 מאנה.

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.