f168: m4a2-分配寶物(Treasure)
Tags : 遞迴
Accepted rate : 18人/21人 ( 86% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-08-06 23:08

Content

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

Input

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

Output

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

Sample Input #1
3
1 2 3
Sample Output #1
NO
Sample Input #2
4
1 2 3 3
Sample Output #2
YES
Sample Input #3
10
12 53 34 23 29 26 19 10 1 6
Sample Output #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
Hint :
Tags:
遞迴
出處:
TOI練習賽2020年4月潛力組 [管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」