[中译] 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