2106 . 殿壬與多邊形

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

66.7% (12/18)

Submission's AC Ratio

15.2% (14/92)

Tags

IOIcamp 2019-IOIcamp

Description

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

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

Input Format

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

  • T∈{1,37}
  • 3≤N≤100000
  • 0<| 給定的數字 |≤1000

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

Output Format

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

Sample Input 1

1
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 262144 1
Submit
Back to Top