[中譯] Puzzleup 2019 (03) COUNTERFEIT GOLD

作者: buffalobill (水牛比爾)   2019-08-08 09:23:45
題目網址: http://www.puzzleup.com/2019/
http://www.puzzleup.com/2019/puzzle/?03
答題時限: 08月08日7PM-比賽結束
加分時限: 08月08日7PM-08月14日6:59PM
答對可得基本分100分。答案可上傳5次,每改1次答案從基本分扣20分。 
比賽期間內可隨時上傳答案,加分時限內答對第n天加(6-n)分       
另依題目的難易有額外加分(如有80%的人這題答錯,答對者加80分)  
◆COUNTERFEIT GOLD
You are given 100 gold coins and told that one of them is counterfeit.
In order to detect the counterfeit one, you decide to get support of an
expert goldsmith. You will group the coins as you wish and ask whether
the counterfeit coin is in that group or not. For every "yes" answer you
will pay 3 $, and for every "no" answer you will pay 2 $.
What is the minimum amount you have to pay to guarantee that you find the
counterfeit coin?
你得到100枚金幣,並被告知其中有一枚是假幣。為了找出假幣,你決定委託一位專
業金匠。你可以將任意數量的金幣分成一組,拿去問金匠該組金幣中是否混有假幣。
每次回答「有」你就得付3元,每次回答「沒有」你就要付2元。
問你最少得準備多少錢,才能保證可找出假幣?
作者: buffalobill (水牛比爾)   2019-08-08 09:24:00
裝死三個禮拜還是沒人要翻譯Orz...是說到現在這三題沒一題是程式題
作者: ACGfans (菜心)   2019-08-08 14:57:00
這題我有用程式跑耶 感覺需要遞迴 手算要怎麼算呀?
作者: buffalobill (水牛比爾)   2019-08-08 17:42:00
2枚的話最少要準備3元,3~4枚要準備6元小於等於2^n枚數的要準備3n枚不是嗎?
作者: ACGfans (菜心)   2019-08-08 18:00:00
3枚只要5元喔 挑一個鑑定 若為no 則2元+剩下兩枚3元=5元
作者: buffalobill (水牛比爾)   2019-08-08 19:08:00
!!感謝提醒,立刻去寫程式
作者: RealJeremi (R34LJ3R3M1)   2019-08-09 12:57:00
Dynamic Programming

Links booklink

Contact Us: admin [ a t ] ucptt.com