c295. APCS-2016-1029-2最大和 - 高中生程式解題系統

內容

給定N群數字，每群都恰有M個正整數。若從每群數字中各選擇一個數字 (假設第 i群所選出數字為ti)，將所選出的N個數字加總即可得和 S = t1+t2+…+ +…+ tN。請寫程式計算 S的最大值 (最大總和 )，並判斷各群所選出的數字是否可以整除 S。

原題pdf檔(第2頁)

輸入說明

第一行有二個正整數 N和 M， 1≦ N ≦ 20 ，1≦ M ≦ 20 。

接下來的N行，每一行各有M個正整數 xi ，代表一群整數，數字與數字間有一個空格，且 1≦ i ≦M，以及 1≦ xi ≦256 。

輸出說明

第一行輸出最大總和 S。

第二行按照被選擇數字所屬群的順序，輸出可以整除S的被選擇數字，數字與數字間以一個空格隔開，最後一個數字後無空白；若 N個被選擇數字都不能整除S，就輸出 -1。

範例輸入 #1

範例輸出 #1

12
6 1

範例輸入 #2

範例輸出 #2

31
-1

測資資訊：

記憶體限制： 256 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

提示：

（範例一說明）挑選的數字依序是 5, 6, 1，總和S=12。而此三數中可整除S的是 6與 1，6在第二群，1在第3群所以先輸出6再輸出1。注意，1雖然也出現在第一群，但她不是第一群中挑出的數字，所以順序是先 6後 1。

（範例二說明）挑選的數字依序是6,9,7,9，總和 S= 31 。而此四數中沒有可整除 S的，所以第二行輸出 -1。

評分說明

輸入包含若干筆測試資料，每一的執行時間限制 (time limit)均為 1秒，依正確通過測資筆數給分。其中：

第 1子題組 20 分： 1≦ N ≦ 20 ，M = 1。

第 2子題組 30 分： 1≦ N ≦ 20 ，M = 2。

第 3子題組 50 分： 1≦ N ≦ 20 ，1≦ M ≦ 20 。

標籤:

APCS

出處:

2016年 10月 APCS [管理者： p3a_owhj (阿普二信) ]

編號	身分	題目	主題	人氣	發表日期
38705	tony20070530 ... (梁允同)	c295	C++ 解法 ( 有心想學好再點 )	306	2023-12-18 07:27
39222	louisvivov11 (louisvivo)	c295	C++ 解題參考	170	2024-01-24 15:10
38780	linyohan3@gm ... (林宥安)	c295	C++解答	241	2023-12-22 23:41
38375	wubaie (小億)	c295	官網原始題目檔連結如下：	187	2023-11-16 12:19
37933	zhoudaniel02 ... (周孝倫)	c295	方法	291	2023-10-19 13:31