712 . 分糖果
TopCoder
Tags
Description
本題改編自 2016 年 10 月 APCS 考古題。
玫瑰班的小孩們喜歡吃糖果，他們想比賽誰能從家裡帶來最大的糖果袋。一共有 $N$ 個小孩加入比賽，且每個小孩家裡都各有 $M$ 個容量不一的糖果袋。在第二天，這 $N$ 個小孩會從家裡選出最大的糖果袋裝滿糖果並帶來班上。此外還有一個特別規則，如果一個糖果袋容量整除現場總糖果數，那該糖果袋會被加冕為完美糖果袋。
請你求出帶來班上的一共有幾個糖果，並且有哪些糖果袋是完美糖果袋。
Input Format
輸入第一行是兩個空白分隔的數字 $N, M$，分別代表參戰人數和每人家中有多少糖果袋。
接著有 $N$ 行每行 $M$ 個空白分隔的數字 $a_{ij}$，第 $i$ 行代表第 $i$ 個人家中的所有糖果袋容量（$1 \leq i \leq N$、$1 \leq j \leq M$）。
對於 $20\%$ 的輸入保證 $1\le N\le 20$，$M = 1$。
對於 $30\%$ 的輸入保證 $1\le N\le 20$，$M = 2$。
對於全部輸入保證 $1\le N, M\le 20$，$1\le a_{ij}\le 256$。
Output Format
輸出第一行是一個整數代表帶來班上的總糖果數。
第二行是所有完美糖果袋的容量，如果有多個請依照將他帶來的人的編號順序排序，數字間以空白分隔。如果沒有任何完美糖果袋，請在該行輸出 $-1$。
Sample Input 1
3 1
1
2
3
1
2
3
Sample Output 1
6
1 2 3
1 2 3
Sample Input 2
4 2
6 2
1 3
7 5
3 3
6 2
1 3
7 5
3 3
Sample Output 2
19
-1
-1
Hints
Problem Source
APCS 歷屆
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 2~10 | $1\le N\le 20, M = 1$ | 20 |
| 3 | 11~22 | $1\le N\le 20, M = 2$ | 30 |
| 4 | 0~32 | 無額外限制 | 50 |