大眾運輸最省方案 (APCS 2026-06 初級)

1.0s 256M

學生丙會搭乘公車與捷運。若依單程計費,搭乘公車每趟需要 \(P_b\) 元,搭乘捷運每趟需要 \(P_m\) 元。同一天內,若連續兩趟分別是公車與捷運,或捷運與公車,則第二趟可享轉乘優惠,省下 \(D\) 元;若連續兩趟交通工具相同,則沒有轉乘優惠。

學生丙也可以選擇購買價格為 \(P_t\) 元的一日票。若某一天購買一日票,當天所有乘車費都不需要另外支付。

在 \(N\) 天中,第 \(i\) 天學生丙會搭乘 \(K_i\) 次大眾運輸。每天他都會在單程計費與一日票之間選擇花費較少的方案;若兩者金額相同,則選擇一日票。請求出 \(N\) 天內的最小總花費,以及在此情形下購買一日票的次數。

輸入格式

第一行有四個整數 \(P_b, P_m, D, P_t\)。

第二行有一個整數 \(N\)。

接下來對於每一天有兩行:

  • 第一行有一個整數 \(K_i\)。
  • 第二行有 \(K_i\) 個整數,依序表示當天搭乘的交通工具。\(1\) 代表公車,\(2\) 代表捷運。

限制

  • \(1 \le P_b, P_m, P_t \le 10000\)
  • \(0 \le D \le \min(P_b, P_m)\)
  • \(1 \le N \le 100\)
  • \(1 \le K_i \le 1000\)
  • \(\sum K_i \le 100000\)
  • 每個交通工具編號皆為 \(1\) 或 \(2\)

輸出格式

輸出一行,包含兩個整數:最小總花費與購買一日票的次數。

評分說明

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

  • 第 1 子題組(\(60\) 分):\(N = 1\) 且 \(K_1 = 5\)。
  • 第 2 子題組(\(40\) 分):無額外限制。

範例輸入 1

10 20 5 55
1
5
1 2 1 1 2

範例輸出 1

55 1

範例解釋 1

單程計費的總金額為 \(55\) 元,與一日票相同,因此依照題目規則選擇一日票。

範例輸入 2

12 18 4 40
3
3
1 1 2
2
2 1
4
1 2 1 2

範例輸出 2

104 1

題目來源

APCS 2026 年 6 月初級實作題第 3 題。

題目頁說明

快速鍵

主要功能

  • 範例測試 — 執行題目附帶的範例測資並自動比對預期輸出。
  • 自訂測試 — 自己貼 stdin 執行程式。可勾選「與預期輸出比對 (diff)」做行對行比對。
  • 模板 — 貼上你在個人資料設定的預設程式碼模板。
  • 協作 — 與其他同學共筆編輯這題的程式碼。
  • 自動草稿 — 編輯器內容每 1.5 秒自動存到瀏覽器(per 帳號 / 題目 / 語言)。
  • 提交 — 把程式碼交給 judge 評測,回傳 AC / WA / TLE 等結果。

限制

  • 程式碼最多 65,536 字元
  • 自訂測試 stdin 與預期輸出各最多 1 MB (約 100 萬字元)
  • 自訂測試每人約 3 秒 1 次 (範例測試 1 秒 1 次)
  • 自訂測試有 15 秒 牆鐘上限;範例測試和正式評測一樣,照題目的時間限制
  • 互動題不提供自訂測試(無法模擬與 judge 互動)。
  • 提交評測本身沒有 rate limit,但同題短時間內多次提交會被視為刷分。