推 werul:好複雜@@ 居然出這麼南的題目阿 10/06 17:53
※ 編輯: kawaiiUsami 來自: 219.84.219.103 (10/06 17:57)
※ 引述《zzzlk (過程比名次美妙)》之銘言：
: http://homepage.ntu.edu.tw/~b93201031/FB052JapanNationalYo-YoContest2003-1.wmv
: 這就是我今天提到的影片~
: 大家看看吧~
這是 2003 日本大賽的剪輯
http://0rz.net/c00dC 完整的比賽在這裡
另外還有很多其他的影片，例如世界大賽，美國大賽等等
http://nctuyoyo.twbbs.org/~file/Contest/
--
嗯，不過這跟 puzzle 沒什麼關係～ 哈哈
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.76.250.17
> -------------------------------------------------------------------------- <
作者: kawaiiUsami (KU) 看板: puzzle
標題: Re: [中譯] PuzzleUp 2009 (11) Number Game
時間: Tue Oct 6 17:49:46 2009
※ 引述《puzzlez (渴望一份好工作)》之銘言：
: 首頁：http://www.puzzleup.com/2009/?home
: 時限：2009/10/01（四）19:00～10/06（二）18:59
: 答案可上傳５次，但每改１次扣２０分（基本分為１００分）
: 在比賽期間內可隨時回答，但只有在時限內回答者有額外加分
:
: ◆Number Game
: 你和你的朋友在玩一個遊戲。你的朋友先從1～9當中暗自選出三個不同的數字。接著你在
: 每回合中喊出四個不同的數字，然後你的朋友再說出這四個數字當中，和他原先所選相同
: 的數量是多少。
: 請問要經過幾回合的猜測，就能確保在任何的情況下，猜出你朋友所選的數字？
: 請注意：當你推測出對方所選數字並喊出時，不視為一回合。
為方便底下說明，先給個名詞好了，朋友選出的3個數字為真數，其他是假數。
一開始先猜1234
四種情況，猜中0個，猜中1個，猜中2個，猜中3個
1. 猜中0個的情況，第二回合猜5678，只有兩種情況：猜中2個或猜中3個，假設猜中2個，
則9必為真數，5678四個數字裡有2個真數，最多再3回合完成，此部份最多5回合完成。
若是第二回合猜中3個，5678裡有3個真數，第3回合猜1256，若猜中1個，則78必是真數
，56之中有一個真數，再一回合即可猜出，若第3回合猜中2個，則56必為真數，另外一
個在78兩者之一，再一回合即可猜出，此部份4回合猜出。
2. 猜中1個的情況，那麼1234中必有一真數，把1234拆成兩半，12跟34，去跟56搭配，
若56中有2真數，則1256跟3456兩者之中，必有一者含有3個真數，一者含有2個真數
若56中有1真數，則1256跟3456兩者之中，必有一者含有2個真數，一者含有1個真數
若56中有0真數，則1256跟3456兩者之中，必有一者含有1個真數，一者含有0個真數
所以可由1234拆成的兩半，去跟5,6搭配。形成第2及第3回合。
分別討論之：
(1). 1256跟3456兩者，有一者中3，另一者中2；則56皆為真數，猜中3個的那一回合去
掉56，剩下的2個數字，必有一真數，例如1256中3個，12中有1個真數，想要過濾
出12之中哪一個是真數？只要再一回合，我們已知在此情況之下，789不會是真數
，第4回合喊出1789，若中1，則1是真數，若1789中0，則2是真數，此部份4回合
完成。
(2). 1256跟3456兩者，有一者中2，另一者中1；則12或34中有一真數，56中有一真數
，第3個真數在789中，假設1256中1，3456中2，則12中沒有真數，34中有1真數；
反之，若1256中2，3456中1，12中有1真數，34中沒有真數，那麼沒有真數的不用
理他。接下來，兩個含有一真數的二數字，拆成一半去跟另一組搭配。
不過他們搭配的方式卻是這樣的，1跟6搭配，2跟5搭配(以下的情況皆假設是12
中含有一真數，34中沒有真數，反之的情況請自行代換)
1真數 1真數 1真數
︱ ︱ ︱
——— ——— ————
︱ ︱ ︱ ︱ ︱ ︱ ︱
１ ２ ５ ６ ７ ８ ９
↑ ↑ ↑ ↑
︱ ------- ︱
︱╴╴╴╴╴╴╴╴ ︱
第4回合及第5回合，分別喊出1678，及2578，若78有一真數，且真數集中在16回
25，則此兩回合會猜中3個及猜中1個，78中哪一個是真數？再一回合猜出，6回
合猜出。若78中無真數且真數集中在16或25，則則此兩回合會猜中2個及猜中0個
，猜中2個的那一回合，去掉78兩數即是真數，而78中無真數，故9是真數，5回
合完成，
若不幸這兩回合都猜中2個，則78有一真數， 16中有一真數，25中有一真數，
12中有一真數，56中有一真數，看起來很復雜，但事實上再一回合完成。
因為1256中，16中有一真數，25中有一真數，12中有一真數，56中有一真數，
所以1256中真數的分布只有2種(打ˇ者是真數)：
ˇ ˇ ˇ ˇ
１ ２ ５ ６ 或 １ ２ ５ ６
而78中有一真數，
ˇ ˇ
７ ８ 或 ７ ８
所以第6回合喊出1579，若中3，真數是157，中2，真數是158，中1是267，中0是
268，6回合完成。
若第4第5兩回合都猜中1個，則78中無真數，9為真數，
那麼，1256中真數的分布只有2種(打ˇ者是真數)：
ˇ ˇ ˇ ˇ
１ ２ ５ ６ 或 １ ２ ５ ６
第6回合喊出1578，可過濾出2個真數是位在15還是26？
6回合完成。
(3). 1256跟3456兩者，有一者中1，另一者中0，則我們可以知道56中沒有真數，
猜中一個那一回合，去掉56，有一個真數。
假設是1256猜中1個，則12中有一個真數，3456猜中0個，34中沒有真數
(以下的情況皆假設是12中含有一真數，34中沒有真數，反之的情況請自行代換)
1真數 0真數 2真數
︱ ︱ ︱
——— ——— ————
︱ ︱ ︱ ︱ ︱ ︱ ︱
１ ２ ５ ６ ７ ８ ９
12中有一真數，一回合可猜出，789有2真數，2回合可猜出。所以再3回合可猜出
，共6回合猜出。
3. 第一回合猜中2個的狀況，一樣把1234分成兩半，12跟34，去跟56搭配，第2及第3回合
喊出1256跟3456；由於1234已含有2個真數，56的情況只會有1個真數或沒有真數。
一樣有4種情況：
12或34中，一邊有兩個真數，另一邊沒有；56有一個真數，此兩回合猜中數為3跟1
12或34中，一邊有兩個真數，另一邊沒有；56中沒有真數，此兩回合猜中數為2跟0
12或34中，兩邊各有一個真數；56有一個真數，此兩回合猜中數為2跟2
12或34中，兩邊各有一個真數；56中沒有真數，此兩回合猜中數為1跟1
所以可以由第2回合跟第3回合的猜中數來斷定是哪一種情況
(1). 2,3兩回合猜中數為3跟1，意即12或34中，一邊有兩個真數，另一邊沒有。
猜中3個的那一回合，去掉5、6的二數，即是真數，另一個在5跟6兩者之中，
再一回合即可猜出，4回合完成。
(2). 2,3兩回合猜中數為2跟0，意即12或34中，一邊有兩個真數，另一邊沒有。
猜中3個的那一回合，去掉5、6的二數，即是真數。
且56中沒有真數，第3個在789之中，最多再2回合即可找出，5回合完畢。
(3). 2,3兩回合猜中數為2跟2，意即12或34中，一邊各有一個真數，且5、6中有一真
數，可用交叉檢測法篩檢出，第4跟第5回合喊出1478及2378。
1真數 1真數 1真數
︱ ︱ ︱
——— ——— ———
︱ ︱ ︱ ︱ ︱ ︱
１ ２ ３ ４ ５ ６
↑ ↑ ↑ ↑
︱ ------- ︱
︱╴╴╴╴╴╴╴╴ ︱
由於78中沒有真數，此兩回合的猜中數只可能為2,0或1,1
2,0的話，2個真數已被篩出，另一個在5,6之間，再一回合篩出，共6回合。
1,1的話，代表真數的分布只有2種可能(打ˇ者是真數)：
ˇ ˇ ˇ ˇ
１ ２ ３ ４ 或 １ ２ ３ ４
而56中有一真數，第6回合喊出1357，由猜中數可篩出3個真數的確切位置，
猜中三個，真數為1、3、5
猜中兩個，真數為1、3、6
猜中一個，真數為2、4、5
猜中零個，真數為2、4、6
(4). 2,3兩回合猜中數為1跟1，意即12或34中，一邊各有一個真數，且5、6中沒有真
數，可見第3個真數在7、8、9中
一樣可以用交叉檢測法篩出，第4跟第5回合喊出1478及2378。
1真數 1真數 1真數
︱ ︱ ︱
——— ——— ————
︱ ︱ ︱ ︱ ︱ ︱ ︱
１ ２ ３ ４ ７ ８ ９
↑ ↑ ↑ ↑
︱ ------- ︱
︱╴╴╴╴╴╴╴╴ ︱
若第4及第5回合的猜中數為3跟1，2個真數被篩出，另一個在7、8之中，再一回
合篩出，6回合完成。
若第4及第5回合的猜中數為2跟0，則2個真數被篩出，另一個真數是9，4回合完
成。
若第4及第5回合的猜中數為2跟2，則2、3中有一真數，1、4中有一真數。7、8
中有一真數。彷照(3).的作法，不再贅述，再一回合即可篩出，6回合完成。
若第4及第5回合的猜中數為1跟1，則2、3中有一真數，1、4中有一真數。第3個
真數為9。兩個真數為1、3還是2、4，再一回合篩出，總共6回合完成。
4. 第一回合就猜中3個的狀況，1234中有3個真數，用最笨的方法，一個一個去試，也只
要4回合，總共5回合完畢。
所以呢，總共要幾回合？自己慢慢看吧！
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.84.219.103