a303. TOI 2019/04 潛力組：農田灌溉

題目描述

道路由 L 個單位區段組成，其中有些區段種有作物。你可以在道路上設置任意數量的灌溉裝置。所有裝置須採用相同的電力等級 k，k 可選 1、2、3、4、5。每台裝置能灌溉其所在位置及左右各 k−1 個單位，最多覆蓋連續 2k−1 個區段。每台裝置的電費是 1.32k+1.07。

請選擇等級與裝置位置，使所有有作物的區段都被灌溉，且總電費最小。若不同等級的最低總電費相同，選較大的等級。沒有作物時不需裝置。

輸入格式

第一行為 L，第二行是長度 L 的字串；0 表示有作物，1 表示沒有作物。

• 1 ≤ L ≤ 5000000

輸出格式

輸出最低總電費與選用的電力等級，以空白隔開。電費固定輸出小數點後兩位。

來源

TOI 2019 年 4 月潛力組〈農田灌溉〉。以自寫文字重述，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/201904/A1-FarmlandIrrigating(Q).pdf 題意核對：M_SQRT 所保存之原題 PDF。