a327. TOI 2022/03 潛力組：射擊遊戲

題目描述

發射裝置固定在平面原點 (0, 0)，起初有 R 次發射機會，射程為 D0。平面上共有 N 個寶物，第 i 個寶物位於 (xi, yi)，並帶有兩個數值 ci、bi。

當射程為 D 時，一次射擊可以選擇一個到原點的歐氏距離不超過 D 的寶物。每個寶物只能命中一次；命中第 i 個寶物後，射程增加 ci，並額外獲得 bi 次發射機會。若發射機會耗盡，或目前射程內沒有寶物，遊戲結束。原題以結束時的射程作為得分，要求找出能得到的最高分。

輸入格式

第一行為 N、R、D0。接下來 N 行，第 i 行依序提供 xi、yi、ci、bi，數字間以空白分隔。

• 1 ≤ N ≤ 2×10^5
• 1 ≤ R ≤ 2×10^5
• 1 ≤ D0 ≤ 10^8
• |xi|、|yi| ≤ 10^9
• 0 ≤ ci ≤ 4×10^3
• 0 ≤ bi ≤ 1
• 所有寶物皆不在原點，且任兩個寶物的座標不同。

原題將每筆資料稱為「4 個非負整數」，但其座標限制使用絕對值，範例也有負座標。此處保留數值限制及全部範例，正負號文字衝突列於下方待釐清事項。

原題分組：30 分滿足 N ≤ 10；30 分滿足 N ≤ 500；40 分無額外限制。

輸出格式

輸出一個非負整數，表示可取得的最高得分。依原題文字，得分是遊戲結束時的射程。

官方資料校對說明

本稿僅供待審，尚未建立完整隱藏測資。

• 原題 PDF 將範例 4 輸出印為 3；官方解題投影片第 4 頁已列為 5，且官方參考程式輸出最終射程。因此以下採用官方投影片的 5，並保留此更正紀錄。
• PDF 的「四個非負整數」與負座標範例矛盾；依絕對值限制、官方範例及參考程式，座標可為負數，ci、bi 則非負。
• 官方參考程式將每個寶物從可選目標中取出一次，確認每個寶物不可重複命中。

範例 1

輸入：

3 1 1
0 -1 1 1
1 0 5 0
2 3 1 0

輸出：

7

範例 2

輸入：

3 2 5
5 0 9 0
6 6 3 0
4 7 5 0

輸出：

19

範例 3

輸入：

1 2 1
2 0 5 1

輸出：

1

範例 4

輸入：

3 2 5
3 4 0 0
4 3 0 1
-4 -3 0 0

輸出：

5

範例說明

範例 1 可先命中 (0, -1)，射程由 1 增至 2，並補回一次發射；再命中 (1, 0)，射程增至 7，發射次數耗盡。

範例 2 可先命中 (5, 0)，再命中 (4, 7)，射程依序變成 14、19。

範例 3 唯一的寶物在射程外，因此維持初始射程。

來源

TOI 2022/03 練習賽潛力組〈射擊遊戲（Shooting）〉。本稿依官方 PDF 自行整理文字，保留原題未釐清處及全部官方範例。

原題連結：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202203/Shooting.pdf

官方解題投影片：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202203/Shooting.odp 官方參考程式：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202203/Shooting.zip