TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

60.0% (3/5)

Submission's AC Ratio

20.0% (3/15)

Description

殿壬是個天才兒童,他在一個月大的時候就學會數數、六個月大的時候就學會乘法跟除法、一歲時學會寫程式。不過因為關於殿壬的故事實在是太多了,導致很多事情沒有辦法被記載下來。所以現在要講的,是殿壬不知何時靈光一閃想到的問題,同時也是殿壬靈光一閃秒掉的問題。

題目非常簡單。給定 $N$ 個數字,問是否存在一個 $N$ 邊形,使得這個 $N$ 邊形的每個邊長形成的多重集合與題目給定的 $N$ 個數字所形成的多重集合相等?

Input Format

輸入的第一行是一個整數 $T$,代表測試資料的筆數。
接下來的每筆測試資料有兩行。第一行是一個整數 $N$,代表第二行會有 $N$ 個數字,代表給定的 $N$ 個數字。

  • $T \in \{1, 37\}$
  • $3 \leq N \leq 100000$
  • $0 < |$ 給定的數字 $| \leq 1000$

Hint 中還有一些關於輸入的規定。

Output Format

對於每一筆測試資料請輸出一行。如果輸出 Yes,代表不存在 $N$ 邊形滿足題目要求,或是 No,代表存在 $N$ 邊形滿足題目要求。

Sample Input

1
3
1 2 3

Sample Output

Yes

Hints

話說回來,以下是對這個問題的輸入的一個驗證程式。保證本題的輸入可以讓以下程式輸出 0 並結束。

#include <bits/stdc++.h>
using namespace std;

int main(){
    int t; cin >> t; assert(t == 1 || t == 37); while (t--) {
        int n; cin >> n; assert(3 <= n && n <= 100000);
        vector<int> v(n);
        for_each(v.begin(), v.end(), [](int x){ string s; cin >> s; assert(accumulate(s.begin(), s.end(), 0, [](int a, char c) -> int { return a + isdigit(c); }) <= 9);});
    }
    cout << 0 << endl;
}

Problem Source

Subtasks

No. Testdata Range Score
1 0 1

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 262144 262144 1