c295. APCS-2016-1029-2最大和
Tags : APCS
Accepted rate : 4511人/4945人 ( 91% ) [非即時]
評分方式:
Strictly

最近更新 : 2021-07-22 20:43

Content

 

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

 

  

原題pdf檔(第2頁)

 

Input

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

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

Output

第一行輸出最大總和 S。

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

 

Sample Input #1
3 2
1 5
6 4
1 1
Sample Output #1
12
6 1
Sample Input #2
4 3
6 3 2
2 7 9
4 7 1
9 5 3
Sample Output #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
Hint :

(範例一說明) 挑選的數字依序是 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 。

 

Tags:
APCS
出處:
2016年10月APCS [管理者: p3a_owhj(阿普二信) ]


ID User Problem Subject Hit Post Date
34885 190050@mlsh....(104 15彭彥傑) c295
python解答
135 2023-04-23 22:57
34532 114125(凱凱) c295
c++解答(簡單版)
223 2023-03-27 20:15
34521 willy633526@...(ByTech) c295
python 題解
172 2023-03-26 22:33
33838 asnewchien@g...(david) c295
Python 解題影片
79 2023-02-06 20:22
33334 wwumin0137@g...(齧齒) c295
我的解法
220 2022-12-26 20:56