f168. m4a2-分配寶物(Treasure) - 高中生程式解題系統

內容

TOI練習賽 2020m4a2-分配寶物(Treasure) 原題連結

問題敘述
Alice、Bob 和 Cindy 對於古物很有興趣，於是他們組成一支尋寶探險隊。有
一天他們在深山的洞穴裡發現了 N 個寶物。他們將寶物清點之後用自身的經驗
對它們進行估價，編號第 i 個寶物價值 Vi 元。他們想要分配寶物，初步討論的
分配規則如下：
1. 他們三個希望所有寶物都要帶走，所有寶物一定會被分配給其中一人。
2. 寶物是不可分割的，也就是說一個寶物只能分配給一個人。
3. 每個人可以擁有寶物的數量沒有限制，但是他們希望[每個人被分配到寶
物價值的總和都要一樣]，如果無解，再行討論。

例如：有 4 個寶物，他們的價值分別是 1、2、3、3，如果 Alice 拿第 1 和第
2 個寶物，Bob 拿第 3 個寶物，Cindy 拿第 4 個寶物，即符合規則。但是情況若
改成 3 個寶物，價值分別是 1、2、3，則無解。

請寫一個程式幫忙計算是否有解。

評分說明
此題目測資分成兩組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。

第一組 (20 分)：N = 4
第二組 (80 分)：3 <= N <= 16

輸入說明

第一行有一個正整數 N (3 <= N <= 16) 代表寶物的數量。第二行有 N 個正整
數，兩個數之間以一個空白隔開，分別表示寶物的價值 V1到 Vn (1<=Vi<=10^7,
1<=i<=N)。

輸出說明

請輸出一行字串，如果寶物可以被平分給三個人，輸出 YES，否則輸出 NO。

範例輸入 #1

3
1 2 3

範例輸出 #1

NO

範例輸入 #2

4
1 2 3 3

範例輸出 #2

YES

範例輸入 #3

10
12 53 34 23 29 26 19 10 1 6

範例輸出 #3

YES

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <1K
公開測資點#10 (5%): 1.0s , <1K
公開測資點#11 (5%): 1.0s , <1K
公開測資點#12 (5%): 1.0s , <1K
公開測資點#13 (5%): 1.0s , <1K
公開測資點#14 (5%): 1.0s , <1K
公開測資點#15 (5%): 1.0s , <1K
公開測資點#16 (5%): 1.0s , <1K
公開測資點#17 (5%): 1.0s , <1K
公開測資點#18 (5%): 1.0s , <1K
公開測資點#19 (5%): 1.0s , <1K

提示：

標籤:

遞迴

出處:

TOI練習賽 2020年 4月潛力組 [管理者： p3a_owhj (阿普二信) ]

編號	身分	題目	主題	人氣	發表日期
35729	wubaie (小億)	f168	原題連結：	229	2023-06-15 10:51
34200	elephant6107 ... (yee elephant)	f168	參考想法	463	2023-03-05 19:40
29264	bubble60324@ ... (賢仔)	f168	新手的解題想法	845	2022-02-09 23:57