924 . 非負整數太多了！

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

蔡兆豐
大家好，我是蔡兆豐。我們今天要介紹的書是我兒佳比。這本書是在講述一個名叫科。克萊爾的傳奇故事。他本來居住在童話社區，每個人都被要求。要一樣。

User's AC Ratio

100.0% (12/12)

Submission's AC Ratio

83.3% (15/18)

Tags

ioicamp ioicamp-2025

Description

八奈見特石前陣子收到了一項奇特的生日禮物——$n$ 個非負整數。

雖然八奈見特石很喜歡吃非負整數(?)，但他家裡已經存放太多非負整數了，多到一整年能不愁吃穿，頂多只能再放一個非負整數，於是 他決定對這 $n$ 個非負整數進行操作。

在一次操作中，八奈見特石會從目前還剩的整數中，選擇吃掉其中一個整數 $x$，並將剩下的整數減掉 $x$。注意，操作後剩下的整數可以變成負的。舉例來說，如果還有 $3,8,8$ 這三個整數，那八奈見特石可以在一次操作中，選擇吃掉一個 $8$，並將剩下的兩個整 數變成 $3-8=-5$ 和 $8-8=0$。

經過 $n-1$ 次操作後，只會剩下一個整數，八奈見特石想知道最後這個整數最大能是多少？（畢竟都要存了，就要存盡量大。）不過如 果無論如何，最後剩下的整數一定會是負的，那麼八奈見特石就會很傷心，所以他也想提前知道會不會發生這種事。擅長寫程式的你能幫助八奈見特石算出來嗎？

Input Format

第一行輸入一個正整數 $T$，代表子測試資料個數。

接下來每個子測試資料會輸入兩行，其中第一行只輸入一個正整數 $n$，代表非負整數的個數，第二行則輸入 $n$ 個非負整數 $a_1,a_2,\ldots,a_n$，代表八奈見特石收到的禮物。

  • $1\le T\le 10000$
  • $1\le n\le 2\times 10^ 5$
  • $0\le a_i\le 10^ 9$
  • 保證 $n$ 的總和不會超過 $2\times 10^ 5$

Output Format

每個子測試資料輸出一行，如果最後剩下的整數一定會是負的，請輸出 Yamada lost again，否則輸出最後的整數的最大可能值。

Sample Input 1

3
1
998244353
2
2024 2025
3
8 1 7

Sample Output 1

998244353
1
7

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~11 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 1048576 65536 1 2
1 1000 1048576 65536 2
2 1000 1048576 65536 2
3 1000 1048576 65536 2
4 1000 1048576 65536 2
5 1000 1048576 65536 2
6 1000 1048576 65536 2
7 1000 1048576 65536 2
8 1000 1048576 65536 2
9 1000 1048576 65536 2
10 1000 1048576 65536 2
11 1000 1048576 65536 2
Submit
Back to Top