e290. PB. 園藝農夫
標籤 :
通過比率 : 1人/2人 ( 50% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-07-01 01:15

內容

有個園藝農夫掌握著全世界最新的科技,能夠將植物種在⼀種溫室玻璃罩內使他快速⽣⻑

這個農夫總共有n個溫室玻璃罩,⾼度為1n。⼀個植物若被種在⾼度為i的溫室玻璃罩內,其最⾼只能⽣⻑到⾼度為i。今天農夫在每⼀個溫室玻璃罩內播種,基於空間或是植物的基因關係,每⼀個植物都成功發芽並竭盡所能的⻑⾼,農夫並將這n個植物的⾼度分別為w1, w2, ...wn 紀錄下來。今天他收到了q個來⾃世界各地的訂單,第i筆訂單為希望能買到⾼度總和剛好為Hi的植物。由於農夫他想將他的利益最⼤化,因此他會⽤以下的策略來選擇他要給這筆訂單哪些植物。

  • 優先給愈⾼的植物愈好。例如農夫紀錄如下,今天有⼀筆訂單為8,農夫會傾向給這個客⼈植物⾼度為2, 6 ⽽不是3, 5,因為愈⾼的植物愈珍貴,能夠跟該客⼾談到更好的價錢。
    溫室玻璃罩⾼度123456
    植物⾼度121356
  • 若遇到多個相同的⾼度的植物優先選溫室玻璃罩⾼度⽐較⼩的。例如農夫的紀錄如下,今天有⼀筆訂單為3,農夫會選擇溫室玻璃照⾼度為1, 2 內的植物⽽不是其他溫室玻璃罩內的植物,因為其他溫室玻璃罩內的植物有更多⽣⻑空間,未來可以⽤基因改造技術使植物⻑更⾼以賣得更⾼的價錢。
    溫室玻璃罩⾼度12345
    植物⾼度12122

過幾天剛好是農夫⽼婆的⽣⽇,他覺得溫室玻璃罩⾼度為x的那個植物最漂亮,想要當成他⽼婆的⽣⽇禮物。然⽽顧客⾄上且利益最⼤化乃是農夫的最⾼原則,若有訂單經過上述利益最⼤化的選法後⽽將溫室玻璃罩⾼度為x的植物售出,他將沒有⽣⽇禮物可以送給他⽼婆。

他花了好久的時間統計這q筆訂單,打算把他們分成三類。第⼀類為不能組合出顧客要求的植物⾼度總和有A個,第⼆類為可以滿⾜顧客要求的植物⾼度總和,但他⽼婆的禮物將會被賣出去的有B個,第三類為可以滿⾜顧客要求的植物⾼度總和,並且他⽼婆的禮物並沒有被賣出去的有C個。然⽽,隨著⽣意愈做愈⼤,愈來愈多的訂單如雪花般的飄來導致農夫無法應付,需要你幫他寫個程式來計算ABC分別是多少。

輸入說明

1⾏有⼀個變數T代表有T筆測資,接下來每⼀筆測資的第⼀⾏有3個變數分別為n, q, x,接下來有n個數字,分別為wi代表⾼度為i的溫室玻璃罩內有⼀個⾼度為wi的植物。接下來有q筆訂單,每⼀筆包含⼀個正整數Hi

1T100

1n103

1xn

1wii

1Hi7105

1q10530的測資1q103
每個query都是獨立的。

輸出說明

每⼀筆測資輸出3個數字A, B, C,如題⽬所述。

範例輸入 #1
2
5 10 2
1 2 2 1 5
1 11 13 8 7 13 10 3 5 12
5 10 3
1 1 2 2 1
4 10 13 1 13 8 11 11 7 6
範例輸出 #1
3 5 2
6 3 1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <50M
提示 :

第1筆測資
A: {13, 13, 12}
B: {11, 8, 7, 10, 3}
C: {1, 5}

第2筆測資
A: {10, 13, 13, 8, 11, 11}
B: {4, 7, 6}
C: {1}

標籤:
出處:
2019 NCTU PCCA Winter [管理者: qqrainbow (愛蜜莉雅) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」