比例分割 (APCS 2026-03 中高級)

2.0s 256M

給定正整數序列 \(w\)。每次詢問指定 \(l,r,a,b\),請找出最小的索引 \(k\in[l,r]\),使 \(w_l+\cdots+w_k\) 至少是整段區間和的 \(a/(a+b)\)。索引從 \(1\) 開始。

輸入格式

第一行為 \(n,m\)。第二行為 \(n\) 個權重。接著 \(m\) 行各為 \(l,r,a,b\)。

限制

\(1\le n,m\le10^5\);\(1\le w_i\le10^4\);\(1\le l\le r\le n\);\(1\le a\le b\le10\)。

輸出格式

每個詢問輸出一行 \(k\)。

評分說明

每筆計分測資獨立計分,每筆 5 分,共 100 分;範例不計分。

  • 1: 40% — \(n,m\le1000\)
  • 2: 60% — 無額外限制。

範例輸入 1

6 1
2 2 6 3 1 5
1 6 1 1

範例輸出 1

3

範例輸入 2

12 3
1 4 2 3 6 7 1 9 9 8 10 6
4 10 1 6
1 6 1 10
3 11 6 8

範例輸出 2

5
2
8

題目來源

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

題敘參考 ZeroJudge s179「比例分割」 整理,細節可能與正式試題有出入。

題目頁說明

快速鍵

主要功能

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

限制

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