作者utomaya (乌托马雅)
看板puzzle
标题[中译] PuzzleUp 2009 (10) Coins
时间Wed Sep 23 21:48:15 2009
首页：
http://www.puzzleup.com/2009/?home
时限：2009/09/17（四）19:00～09/22（二）18:59
答案可上传５次，但每改１次扣２０分（基本分为１００分）
在比赛期间内可随时回答，但只有在时限内回答者有额外加分
◆Coins
某个国家中，只要
最多2枚硬币，就可以表达出1至50元的数值(1和50皆包含在内)
在这个国家中，所有种类的硬币币值，其总和的最小可能值为何？
假设题目要求的是可以表达1~8元的数值
硬币最小总和为8元，分别是1元, 3元, 和4元
1元 = 1个1元硬币
2元 = 2个1元硬币
3元 = 1个3元硬币
4元 = 1个4元硬币
5元 = 1个1元硬币 + 1个4元硬币
6元 = 2个3元硬币
7元 = 1个3元硬币 + 1个4元硬币
8元 = 2个4元硬币
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 219.70.180.112
※ 编辑: utomaya 来自: 219.70.180.112 (09/23 22:21)
1F：推 EIORU:1.3.9.27? 09/24 09:51
2F：推 puzzlez:楼上在说答案？0.0" 不过那不可能是正解 因为最多是36元 09/24 10:02
3F：推 puzzlez:哦 不对 最多是 54元......凑不出50.... 09/24 10:09
4F：推 chung6hc:3的平方数列, 5块就要超过2枚了... 09/24 10:32
5F：推 turing:联想到「所有的偶数都是两质数的和」的「猜想」。 09/24 10:46
6F：推 puzzlez:反正可以肯定答案小於200...(废话)...( ￣ c￣)y▂ξ 09/24 10:46
7F：推 puzzlez:turing的猜想，可惜奇数没有照顾到:-(如果是三枚就好了 09/24 10:47
8F：推 puzzlez:啊，突然想到一件事@@" 来验算看看... 09/24 10:50
9F：推 turing:这不是「turing的猜想」，这是数论界急於证明的事情。 09/24 10:53
10F：→ turing:在数学界尚未证明及未找到反证前都称之为「猜想」。 09/24 10:54
11F：推 puzzlez:我是指你说的猜想啦=.=" 不过真的让我灵光一闪.... 09/24 10:55
12F：→ turing:费马最後的定理在Andrew Wiles证明之前其实应称为「猜想」 09/24 10:57
13F：推 puzzlez:可惜...用「50之前的质数」还是太多了.... 09/24 10:59
14F：→ pikacha:我可以说直觉猜的答案吗?感觉这写个程式就能解出来?! 09/24 16:01
15F：推 puzzlez:还是不要吧...因为我靠直觉之後...後来的答案都比它大@@" 09/24 16:02
16F：推 puzzlez:所以搞不好那个直觉...真的是对的@@"...有那麽简单吗？ 09/24 16:03
17F：推 tp:---- 09/24 16:55
不好意思，为了竞赛的乐趣，请不要写出答案，不管你的答案是错或是对
帮你mark掉，请不要介意
18F：推 stimim:在小一点 09/24 18:33
※ 编辑: utomaya 来自: 219.70.180.112 (09/24 18:53)
19F：→ utomaya:我提供一个想法，假设有n种币值的硬币 09/24 19:48
20F：→ utomaya:那麽 一个硬币的值有n种，2个硬币的值最多有n^2种 09/24 19:50
21F：→ utomaya:假设他们都刚好不重覆，那麽最多可形成n+n^2个值 09/24 19:51
22F：→ utomaya:n+n^2 ≧50, n的最小值为7，小於7种币值的，根本不用考虑 09/24 19:53
23F：推 stimim:还要再除二，因为可以交换 09/24 20:29
24F：→ utomaya:喔 对喔! 那应该是n+n^2/2 ≧ 50, n的最小值是9 09/24 21:02
25F：→ utomaya:写错...是n的最小值是10才对 10+10^2/2=60≧50 09/24 21:04
26F：推 Poggle: C(n,2) + n + n ≧ 50 09/24 21:37
27F：→ Poggle:两枚不重覆、两枚相同、只有一枚 => n≧9 应该这样?! 09/24 21:37
28F：推 puzzlez:9个点一共只能连45条线，所以n不会等於9，至少是10.... 09/24 23:17
29F：→ utomaya:P大写得才是对的 我刚才也发现自己少考虑了一种 09/25 00:04
30F：→ utomaya:所以应该是(n^2+3n)/2 ≧ 50 n最小是9 09/25 00:06
31F：推 LPH66:不过 n=9 时一共只有54种拿法 要选到不重覆有点难... 09/25 01:26
32F：推 puzzlez:嗯Poggle说的没错，如果有N种币值，则3种组合方式为： 09/25 14:14
33F：推 puzzlez:1.只付一枚：N种 2.付两枚相同币值：N种 3.付两枚不同币 09/25 14:15
34F：推 puzzlez:N(N+1)/2种 所以一共有N+N+N(N+1)/2 种=N(2+(N+1)/2) 09/25 14:18
35F：推 puzzlez:当N=8时，共有8(2+4.5)=52 就已经超过50了.... 09/25 14:20
36F：推 puzzlez:=.= 我打错公式了 是 N(N-1)/2...... 09/25 14:26
37F：推 puzzlez:N(2+(N-1)/2)种 所以N=9时, 9(2+4)=54...是9没错... 09/25 14:27
38F：推 puzzlez:我猜答案不会超过15种吧.... 09/25 14:30
39F：推 turing:题目问的是总和最少，而不是数量最少 09/25 16:24
40F：推 puzzlez:15种的最小组合是120 离 150 很接近 猜15种左右很合理 09/25 17:25
41F：推 Poggle:其实量多不一定是不好 (如果能让其他硬币运用更有效率的话) 09/25 21:52
42F：→ Poggle:也许数列上你舍弃了某个数，会让之後一个更大的数产生需求 09/25 21:52
43F：→ Poggle:而一个25可是输给三个8的，尽可能减少大数才是正途 :) 09/25 21:52
44F：推 puzzlez:最简单的方法就已经不超过150了，15种的最小答案是120... 09/25 22:08
45F：推 puzzlez:就算想取超过15种也很难吧...难道你们目前的答案有超过吗 09/25 22:08
46F：→ utomaya:有耶 我超过120了 09/25 22:12
47F：→ utomaya:你有验算吗? 最多2枚硬币可以组成1到50 一一验算之 09/25 22:13
48F：推 puzzlez:=.=" 超过120很正常啊...我是说难道你们都超过15种？ 09/25 22:14
49F：推 puzzlez:120基本上一定会超过的吧 那是取1~15的总和... 09/25 22:15
50F：→ utomaya:没超过15种 09/25 22:15
51F：推 puzzlez:取15种最小的方式是取1~15（当然这不可能是答案）总和120 09/25 22:16
52F：推 puzzlez:所以你取15种的话 基本上总和一定会超过120 09/25 22:17
53F：推 puzzlez:已知最笨的方法 其总和为 145 所以总和绝不能超过它 09/25 22:19
54F：→ utomaya:我有一个直觉的方法 14种 但总和是193...超大的值 09/25 22:22
55F：推 puzzlez:咦？我以为145的答案还满直觉的耶...真的很难想另一种 09/25 22:25
56F：推 turing:我写了一个程式，目前已经跑了半天了，还跑不出来。 09/26 00:38
57F：→ turing:不过我也想到了p大的145的解答。 09/26 00:40
58F：→ turing:经过一番推导和stimim的提醒找到了比tp大「少一点」的答案 09/26 00:42
59F：→ turing:赶在第一天的期限到之前上传答案... 09/26 00:43
60F：推 ars1an:刚写了个程式跑完了，找出比之前上传还少2的答案…orz 09/26 04:36
61F：推 puzzlez:这题的难度还真高啊.....:-( 09/26 06:59
62F：→ utomaya:我忽然发觉这题的意义了 这题其实是第2题运水问题的延伸 09/26 10:06
63F：→ utomaya:一样有2个中继点 要把水运到终点(50) 09/26 11:31
64F：推 werul:好难@@ 09/26 21:24
65F：推 EIORU:我想到---- 09/26 22:17
66F：→ EIORU:再---- 09/26 22:19
sorry，帮你把答案mark掉
67F：→ FACE90006:大家都好厉害唷 我都没想法Q.Q 09/26 22:31
※ 编辑: utomaya 来自: 219.70.180.112 (09/26 23:29)
68F：推 tp:我大概知道"少一点"是少哪里了 09/27 16:01