你,身為一個蘿莉控,身邊當然會有許多蘿莉,其中恰有一個蘿莉是SS級的蘿莉。你原本不知情,直到農曆新年放鞭炮時,SS級的蘿莉因為被鞭炮嚇到而發出嬌柔的叫聲,你才發現他的存在。可惜當時你並沒有注意是哪隻蘿莉在叫,所以你為了要找出哪隻蘿莉是SS級的蘿莉而買了許多鞭炮。
為了省鞭炮,你將蘿莉們編號為當然,直接撲下去好像還不錯,不過請記住你現在的目標。 進入隔音間後,你就點燃鞭炮。如果SS級的蘿莉也在隔音間,你就會聽到那個令人精神振奮的叫聲;如果沒有,你就只會聽到鞭炮聲。你的目標是使用最少的鞭炮找出SS級的蘿莉。
另外,你其實早就調查了每個蘿莉是SS級的機率,並以陣列
(
第一行有一個正整數
接著第二行會有
子任務(測資) | 額外限制 | 分數 |
1 (0~4) | 9 | |
2 (5~9) | 13 | |
3 (10~14) | 15 | |
4 (15~19) | 無 | 63 |
為了方便,請輸出
4 1 1 2 3
13
註:
先把編號3的蘿莉帶到小房間獨處,
1. 如果聽到叫聲,就找到了。
2. 如果沒有,再把編號0跟1的蘿莉帶到小房間:
2-1. 如果聽到叫聲,把編號1的蘿莉趕出小房間再試一次,就知道到底是0號還是1號了。
2-2. 如果沒有,結果就是2號。
使用的鞭炮數的期望值是13/7。
Problem set / Description by Paupière
建國中學105學年度校隊選拔:初試pF
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 9 |
2 | 5~9 | 13 |
3 | 10~14 | 15 |
4 | 15~19 | 63 |