2106 . 殿壬與多邊形
TopCoder
Tags
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
1
3
1 2 3
3
1 2 3
Sample Output 1
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 |