f998: 外星人幽話
Tags : aliens
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Special

最近更新 : 2022-04-15 20:18

Content

有一天肯肯肯走在路上,看到一個奇怪的飛行物體飄著,他走上前看,結果突然有一道光發射出來,把他吸走了。

到了飛行物體裡,他看到兩個奇怪的東西在講話:

╰$℅┐:「》▅﹉﹉$,》$▼   ╪╠▅   ┐$℃」

【▅﹌€$﹌:「╓℅   ★╓﹌▅   ╰》╪﹌㊣   ┐$℃」

他們講的語言肯肯肯完全聽不懂,因為他們感覺就是外星人,就暫且把這種語言叫做外星人幽話吧!

╰$℅┐ 和 【▅﹌€$﹌ 發現了肯肯肯的存在,對肯肯肯說:「你好肯肯肯,歡迎你來我們的飛船,因為我們沒什麼東西可以招待你的,所以這一根雞腿就給你啃啃吧!」

肯肯肯啃啃完雞腿後,發現雞腿上有很多坑坑,於是肯肯肯啃啃坑坑,發出鏗鏗鏗的聲音,所以肯肯肯啃啃坑坑鏗鏗鏗。但其實這根雞腿是 ╰$℅┐ 和 【▅﹌€$﹌ 故意給肯肯肯吃的,如果肯肯肯吃完這根雞腿,就要幫外星人做事,所以外星人在坑坑肯肯肯,╰$℅┐ 和 【▅﹌€$﹌ 坑坑肯肯肯啃啃坑坑鏗鏗鏗。

外星人說:「我們這個飛船其實叫『銀河捷運』,採用的是模 $\color{black}{M}\ $ 運算,且每一條路線都可以用一個方程式 $\color{black}{y = x^3 + ax + b}\ $ 和一質數 $\color{black}{M}\ $ 來表示 ...」

肯肯肯:「我知道這些有什麼用,你們到底想做什麼?」

外星人:「我們其實是想找人測試銀河捷運的舒適度,我們現在正要開往月球的資料儲存中心,我們現在距離那裡 $\color{black}{x}\ $ 公里,要 $\color{black}{O (log(x))}\ $ 的時間才能到,但實務上 $\color{black}{O(1)}\ $ 就可以了,因為在我們捷運界根本不會有這麼大的 $\color{black}{x}\ $。」

肯肯肯:「好吧,既然你們都請我吃雞腿了,我就幫你們測試一下吧!喔對了,之前有人幫你們測試過嗎?」

外星人:「你可以來一下看這個的心得:『大家好,我是 Waimai,今天要跟大家分享我搭捷運的心得。這個捷運真的是太舒適了,總共有六條線可以搭,而且捷運在進站前還會有音樂可以聽,捷運上不能吃東西,以維持捷運的整潔度 ...』,所以來我們這家銀河捷運,只要 $\color{black}{64\ bit}\ $ 的 $\color{black}{coin}\ $,就可以享受愉快的旅程。」

肯肯肯:「我剛剛沒有聽到音樂啊,而且我剛剛在捷運上為什麼可以吃雞腿,他不是說捷運上不可以吃東西嗎?」

外星人:「我又沒有說他搭的是我們的捷運,我只是看他心得寫的很好,想拿來分享。」

肯肯肯:「你怎麼可以拿一個根本沒搭過你們捷運的人當廣告呢?」

外星人:「你怎麼這樣憑空汙人清白,分享的事,能算是當廣告嗎?況且 ╰$℅┐ 可是留學過獵戶座社區大學的,你要相信他的專業啊。沒想到你的教養還真不錯!都跑來嗆聲我,難怪地球會如此情況,真有榮幸遇見你,多多指教。」

然後肯肯肯就被丟到地球上了,肯肯肯現在離地表的高度為 $\color{black}{h}\ $,因為飛船還沒有飛的太高,重力加速度接近 $\color{black}{g}\ $,那 $\color{black}{\frac{1}{2}gt^2 = h}\ $,$\color{black}{t = \sqrt{\frac{2h}{g}}}\ $,肯肯肯要花 $\color{black}{O(\sqrt{h})}\ $ 的時間才會掉到地面上,不過因為 $\color{black}{h}\ $ 在業界沒有到很大,所以肯肯肯以 $\color{black}{O(1)}\ $ 的時間掉到地上後,就跑去學習時間複雜度的課程,在那裡他學到了如何規劃考試作答時間,之後考試都考 $\color{black}{100}\ $ 分。

現在要講的是,肯肯肯在丟球時遇到的事:肯肯肯在丟球時常常丟到人,如果丟到人會讓他很開心。他有很多種球,像是紙球、鉛球、保齡球。操場上總共有 $\color{black}{n}\ $ 個人,每個人被不同種球丟到的機率都不太相同,像是可能有人都不會被鉛球砸到,卻會被紙球打到頭破血流,$\color{black}{n}\ $ 個人被同一種球打到的機率都各不相同。為了方便描述,就假設肯肯肯現在有 $\color{black}{k}\ $ 種球好了,每種球的數量分別為 $\color{black}{a_1 \sim a_k}\ $,$\color{black}{n}\ $ 個人裡第 $\color{black}{i}\ $ 個人被第 $\color{black}{j}\ $ 種球砸到的機率為 $\color{black}{p_{i,j}}\ $,肯肯肯一次可以對同一個人丟很多種球,但每種球最多只能丟一個,且 $\color{black}{n}\ $ 個人累積下來,第 $\color{black}{i}\ $ 種球不能丟超過 $\color{black}{a_i}\ $ 顆。那如果肯肯肯向對方丟兩種以上的球,對方被砸到的機率要怎麼算呢?這邊舉一個例子,假設對方被鉛球丟中的機率為 $\color{black}{0.49}\ $,被紙球丟中的機率為 $\color{black}{0.87}\ $,那最後被球丟中的機率為 $\color{black}{1 - (1 - 0.49)\times (1 - 0.87)}\ $,也就是用 $\color{black}{1}\ $ 減掉沒被鉛球丟中的機率乘以沒被紙球丟中的機率。

肯肯肯如果丟到人,就會很開心的說:「我是電神,我穩了吧!」為了讓自己很穩,肯肯肯想最大化打到總人數的期望值,請你幫他算算看!

Input

第一行輸入 $\color{black}{n, k}\ $,代表操場上的人數和球的種類數。

第二行輸入 $\color{black}{a_1\sim a_k}\ $,代表第 $\color{black}{i}\ $ 種球的數量有 $\color{black}{a_i}\ $ 個。

接著輸入 $\color{black}{n}\ $ 行,每行有 $\color{black}{k}\ $ 個六位小數 $\color{black}{p_{i,1} \sim p_{i,k}}\ $,代表第 $\color{black}{i}\ $ 個人被第 $\color{black}{j}\ $ 種球丟到的機率有 $\color{black}{p_{i,j}}\ $。

  • $\color{black}{1≤n,k≤10^6}\ $
  • $\color{black}{1≤a_i≤n}\ $
  • $\color{black}{0≤p_{i,j}<1}\ $,且若 $\color{black}{x≠y}\ $,$\color{black}{p_{x,j}≠p_{y,j}}\ $。

因為如果最大的 $\color{black}{n}\ $ 和最大的 $\color{black}{k}\ $ 相乘有 $\color{black}{10^{12}}\ $ 這麼大,肯肯肯雖然很喜歡超級常數優化,但是他也受不了這麼多的輸入,所以有一個限制,當 $\color{black}{k}\ $ 很大時會讓 $\color{black}{n}\ $ 變很小,當 $\color{black}{n}\ $ 很大時讓 $\color{black}{k}\ $ 變很小。

  • $\color{black}{n≤max(1, \frac{10^8}{100^k})}\ $
Output

輸出一個小數,代表最大丟到總人數的期望值。

假設你的輸出是 $\color{black}{output}\ $,正確答案是 $\color{black}{ans}\ $,那只要 $\color{black}{\frac{|output-ans|}{max(1,ans)}≤10^{-4}}\ $ 就可以 $\color{black}{\text{AC}}\ $。

Sample Input #1
10 1
7
0.133391
0.505187
0.448532
0.987843
0.561229
0.385274
0.162160
0.626533
0.352424
0.133695
Sample Output #1
3.867022
Sample Input #2
1 3
1 1 1
0.132266 0.209247 0.551256
Sample Output #2
0.69208835
Sample Input #3
6 2
2 5
0.042975 0.507933
0.998576 0.741719
0.993119 0.595970
0.032752 0.408874
0.882920 0.356527
0.800763 0.287047
Sample Output #3
3.9953693831
Sample Input #4
5 3
3 4 4
0.414797 0.307388 0.756785
0.781208 0.920415 0.820914
0.688991 0.818737 0.095950
0.986956 0.304158 0.689808
0.778338 0.211103 0.252634
Sample Output #4
4.62618248
測資資訊:
記憶體限制: 128 MB
公開 測資點#0 (8%): 2.0s , <1K
公開 測資點#1 (8%): 2.0s , <1K
公開 測資點#2 (9%): 2.0s , <10M
公開 測資點#3 (8%): 2.0s , <1K
公開 測資點#4 (9%): 2.0s , <1K
公開 測資點#5 (9%): 2.0s , <50M
公開 測資點#6 (4%): 2.0s , <1K
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 2.0s , <1M
公開 測資點#9 (5%): 2.0s , <1M
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1K
公開 測資點#12 (5%): 2.0s , <1K
公開 測資點#13 (5%): 2.0s , <1K
公開 測資點#14 (5%): 2.0s , <1M
公開 測資點#15 (5%): 2.0s , <1M
Hint :

$\color{black}{25\%:k = 1}\ $

$\color{black}{26\%:n = 1}\ $

$\color{black}{49\%:無特別限制}\ $

Tags:
aliens
出處:
Caido [管理者:
becaido (Caido)
]


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