比賽賽馬 - 拼圖

※ 引述《CEO (少點特寫多點空間)》之銘言：
: There is one race ground with 5 race tracks. Each race could only
: have one horse running on it when there is a horse race.. When there
: are 100 horses and the faster horse always run faster than the slower
: horse. if we have to find out the fastest 3 horses out of these 100
: horses, how many races we need to have in this race ground?
: 大家想看看嚕~ ：D

順著推文去追了一下這題的歷史。原先好像是Tech_Job板一題NVIDIA面試的考題
後來轉到Inference板，時間是去年。題目是100匹馬，一次只3匹同時跑，因為
餘數問題討論起來比這題複雜。但精神應該一樣的，而且可以講比較細，就先解
冷題一下

以下是closetou板友的解答的附注解囉嗦版(?) 結論是＜100匹/3匹/找前三＞需55次

EDIT: 訂正為54次, closetou原答案正確

方法的精神是聚焦在「全局的第一/二/三名可能在哪裡」為了避免搞混我把冠軍馬命
名為A，第二名= B，第三名= C，以和每一次比賽的1,2,3名區分。

*第一梯

┌ 33場 ┐+1 * 100= 33x3 +1 剩一匹
1 ..... ↓
2 ↓
3 ↓
↓
*第二梯 ↓
↓
┌ 11場 ┐+1 * 33 = 11x3,
1 .....
2 多的一匹混回來，試煉之。
3

*第三梯 * 11+1 = 4x3

┌ 4 場 ┐
1 1 1 1 不難驗證，四匹馬要完全排序起碼要比三次。
2 2 2 2 但，若只是要找四匹中的前兩名，只需要兩次。
3 3 3 3

因此 2 場後 可分出

*王者之梯次(=2場比賽)

1----------> 篤定是馬王A，此時要問，B可能在哪裡？B唯一會被打敗就是跟A分在
2 一組，換句話說A升上來的過程中，牠的下一名都有可能是籤運很衰
3/4 剛好被A幹掉的B。
3/4
另外，可能B從未遇到A，此情況下一路升到王者之梯次的第2名就是B。
這就是上面說只需要比兩次確定前兩名的原因。

可能的B有幾匹？ 若A恰好是第一梯多出來那匹，可能的B = 3匹。若A並不是該匹馬，
則由A一路「產生」出可能的B的"馬"選 = 4匹。

考慮最糟情況4匹 。由這4匹 恰好都曾被A打成第2名的馬 再比2場，以確定前兩名

*決定B之梯次 (=2場比賽)

1' ----------> 我是B
2'
3/4'
3/4'

那C可能在哪？ 結論是C可能是A或B一路升上來不小心幹掉的第2名，要是A曾經淘汰掉B
(在同一組)，C還可能極頂倒楣，剛好也在同一組，被擠到第3名。

依照A與B相遇的狀況，可能的C數量不同。可能的C 有:

>> B在遇到A之前的手下敗將第2名，可能0或1或2匹。

>> A與B相遇該梯次跟他們同組的第3名。

>> 以及上面的2'。2'洽好是A的手下敗將集合，而且在決定B一戰輸給B，故可能是C。

>> 若A跟B直到王者之梯次才遇到，王者戰中名次懸而未決的2匹馬3/4也都可能是C

這樣一共是6匹馬，考慮最差狀況，還需要3場才能決定其中最快的，即C。

總計 33 + 11 + 4 + 2 + 2 + 3 = 55
一梯 二梯 三梯 王戰 B戰 C戰


這答案我還蠻確定的。

EDIT: 藍底字錯了，>>號第二個與第四個重複計算，最差狀況是5匹馬。

從五匹馬中找最快者只需2場，因此總共是54場才對。


- - - - - - - - - - - - -

100匹/5匹因為除得盡，簡單很多

┌ 20 場 ┐
1 ....
2
3
4
5

┌ 4場 ┐
1 1 1 1
2 2 2 2
3 3 3 3
...

┌1場┐
1 ----------> A
2
3
4

可能的B有3匹，再一場 -----> 決定B

可能的C有2或3匹 (依AB相遇時機而定，參考上題) ，再一場 -----> 決定C

20+4+1+1+1一共27場即可

--