e290: PB. 園藝農夫
Tags :
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

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

Content

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

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

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

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

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

Input

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

$1 \leq T \leq 100$

$1 \leq n \leq 10^3$

$1\leq x \leq n$

$1 \leq w_i \leq i$

$1 \leq H_i \leq 7*10^5$

$1 \leq q \leq 10^5$,$30%$的測資$1 \leq q \leq 10^3$
每個query都是獨立的。

Output

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

Sample Input
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
Sample Output
3 5 2
6 3 1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 3.0s , <50M
Hint :

第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}

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


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」