商品比價 (APCS 2026-11 中級)

小美要買齊 \(n\) 項商品，附近共有 \(m\) 家店。店家編號 \(1\)～\(m\)，商品編號 \(1\)～\(n\)。

每家店對每項商品各有一個標價，不過有些店沒有賣某些商品：第 \(i\) 家店第 \(j\) 項商品的標價是 \(p_{i,j}\)，\(p_{i,j} = -1\) 表示這家店沒有賣這項商品。

每家店都有一個固定的折扣，全店商品都適用。第 \(i\) 家店的折扣是 \(d_i\)，表示全店商品打 \(d_i\)% off，也就是售價是標價乘以 \((100 - d_i) / 100\)。例如折扣是 \(20\)、\(30\)、\(50\) 的店，售價分別是標價乘以 \(0.8\)、\(0.7\)、\(0.5\)。

每一項商品，小美都會到售價最便宜的店購買；如果有好幾家店的售價一樣便宜，就選編號最小的那一家。請算出每一項商品要到哪一家店購買，以及買齊 \(n\) 項商品的最低總價。

舉例來說，有 \(3\) 家店、\(4\) 項商品，三家店的折扣依序是 \(20\)、\(30\)、\(50\)，標價如下表（\(-1\) 表示沒賣）：

打折後的售價如下表，每項商品最便宜的售價用粗體標示：

商品 1 在店 2 最便宜（\(70\)），商品 2 在店 1 最便宜（\(160\)），商品 3 在店 2 最便宜（\(140\)），商品 4 在店 3 最便宜（\(200\)）。所以四項商品依序到店 \(2\)、\(1\)、\(2\)、\(3\) 購買，總價是 \(70 + 160 + 140 + 200 = 570\)。

輸入格式

第一行有兩個整數 \(m\) 與 \(n\)，代表店家數與商品數。

接下來有 \(m\) 行，第 \(i\) 行有 \(n\) 個整數 \(p_{i,1}, p_{i,2}, \ldots, p_{i,n}\)，依序是第 \(i\) 家店第 \(1\)～\(n\) 項商品的標價。

最後一行有 \(m\) 個整數 \(d_1, d_2, \ldots, d_m\)，依序是每家店的折扣。

同一行的數字之間以一個空白隔開。

限制

• \(1 \le m, n \le 50\)
• \(p_{i,j} = -1\)，或是 \(0 \le p_{i,j} \le 50000\) 且 \(p_{i,j}\) 是 \(100\) 的倍數。
• 每一項商品都至少有一家店有賣。
• \(0 \le d_i \le 100\)

輸出格式

輸出兩行。第一行有 \(n\) 個整數，第 \(j\) 個整數是第 \(j\) 項商品要到哪一家店購買，數字之間以一個空白隔開。第二行有一個整數，是買齊 \(n\) 項商品的最低總價。

評分說明

每一筆測試資料的執行時間限制均為 \(2\) 秒，依正確通過的測試資料筆數給分。

範例輸入 1

3 4
100 200 -1 300
100 300 200 -1
200 -1 300 400
20 30 50

範例輸出 1

2 1 2 3
570

範例解釋 1

就是題目敘述中的例子：四項商品依序到店 \(2\)、\(1\)、\(2\)、\(3\) 購買，總價 \(570\)。

範例輸入 2

2 3
100 400 -1
200 800 300
0 50

範例輸出 2

1 1 2
650

範例解釋 2

店 1 的折扣是 \(0\)，售價就是標價；店 2 的折扣是 \(50\)，售價是標價的一半。

商品 1、商品 2 在兩家店的售價一樣，選編號較小的店 1；商品 3 只有店 2 有賣。總價是 \(100 + 400 + 150 = 650\)。

題目來源

APCS 2026 年 11 月中級實作題第 1 題。

官方未公布題本，題敘依考生考後回憶整理（豌豆 APCS 提供），細節可能與正式試題有出入。