有個園藝農夫掌握著全世界最新的科技,能夠將植物種在⼀種溫室玻璃罩內使他快速⽣⻑
這個農夫總共有$n$個溫室玻璃罩,⾼度為$1$到$n$。⼀個植物若被種在⾼度為$i$的溫室玻璃罩內,其最⾼只能⽣⻑到⾼度為$i$。今天農夫在每⼀個溫室玻璃罩內播種,基於空間或是植物的基因關係,每⼀個植物都成功發芽並竭盡所能的⻑⾼,農夫並將這$n$個植物的⾼度分別為$w_1$, $w_2$, ...$w_n$ 紀錄下來。今天他收到了$q$個來⾃世界各地的訂單,第$i$筆訂單為希望能買到⾼度總和剛好為$H_i$的植物。由於農夫他想將他的利益最⼤化,因此他會⽤以下的策略來選擇他要給這筆訂單哪些植物。
溫室玻璃罩⾼度 | 1 | 2 | 3 | 4 | 5 | 6 |
植物⾼度 | 1 | 2 | 1 | 3 | 5 | 6 |
溫室玻璃罩⾼度 | 1 | 2 | 3 | 4 | 5 |
植物⾼度 | 1 | 2 | 1 | 2 | 2 |
過幾天剛好是農夫⽼婆的⽣⽇,他覺得溫室玻璃罩⾼度為$x$的那個植物最漂亮,想要當成他⽼婆的⽣⽇禮物。然⽽顧客⾄上且利益最⼤化乃是農夫的最⾼原則,若有訂單經過上述利益最⼤化的選法後⽽將溫室玻璃罩⾼度為$x$的植物售出,他將沒有⽣⽇禮物可以送給他⽼婆。
他花了好久的時間統計這$q$筆訂單,打算把他們分成三類。第⼀類為不能組合出顧客要求的植物⾼度總和有$A$個,第⼆類為可以滿⾜顧客要求的植物⾼度總和,但他⽼婆的禮物將會被賣出去的有$B$個,第三類為可以滿⾜顧客要求的植物⾼度總和,並且他⽼婆的禮物並沒有被賣出去的有$C$個。然⽽,隨著⽣意愈做愈⼤,愈來愈多的訂單如雪花般的飄來導致農夫無法應付,需要你幫他寫個程式來計算$A$,$B$,$C$分別是多少。
第$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都是獨立的。
每⼀筆測資輸出$3$個數字$A$, $B$, $C$,如題⽬所述。
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
3 5 2 6 3 1
第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}
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」
|