w****0 发帖数: 803 | 1 Suppose that you want to build a wall with bricks. The store that sells
bricks
sells them in packs of 3, 6 or 20 bricks. Suppose that you have infinite
amount of money and the store has infinite amount of bricks of each of
these packs.
You want to build the wall so that when you are finished, you want an
excess of 1 or 2 bricks.For instance, a wall of 4 bricks is a preferable one
, since you can buy a
pack of 6 bricks and has an excess of 2 bricks. Similarly, a wall with 5
bricks
is also preferable.
However, you also want the amount of bricks in your wall not to be a
combination of 3, 6 or 20 bricks. For instance, although you can build a
wall
of 40 bricks and have an excess of 1 brick by buying 7 packs of 3 bricks
and 1 pack of 20 bricks, the amount 40 bricks in your wall can be obtained
by 2 packs of 20 bricks.
With this given information you want to build a wall which has the maximum
number of bricks. What is this maximum number? | h*******t 发帖数: 2679 | 2 就是做除法啊。
int x;
x/20
x/6
x/3 | h*******n 发帖数: 357 | 3 我觉得就是找一个数,除3,6,20都除不尽,但是这样的数可以无穷大吧。
比如1111,11111,1111111 等等都满足条件啊,还是我理解的有问题? | c*******2 发帖数: 60 | 4 就是找到不能表示成 3x + 6y + 20z 的最大正整数吧. 6y可以去掉 | x*********n 发帖数: 46 | 5 这结果不是可以要多大有多大吗?
只要不是 3x + 6y + 20z. | c*******2 发帖数: 60 | 6 这有个上限的, 比如大于40以后肯定都可以表示了,
40 = 20*2
41 = 3*7 + 20
42 = 3*14
43 = 40 + 3
【在 x*********n 的大作中提到】 : 这结果不是可以要多大有多大吗? : 只要不是 3x + 6y + 20z.
| b***e 发帖数: 1419 | 7 37
one
【在 w****0 的大作中提到】 : Suppose that you want to build a wall with bricks. The store that sells : bricks : sells them in packs of 3, 6 or 20 bricks. Suppose that you have infinite : amount of money and the store has infinite amount of bricks of each of : these packs. : You want to build the wall so that when you are finished, you want an : excess of 1 or 2 bricks.For instance, a wall of 4 bricks is a preferable one : , since you can buy a : pack of 6 bricks and has an excess of 2 bricks. Similarly, a wall with 5 : bricks
| w****0 发帖数: 803 | 8 怎么得到的?
【在 b***e 的大作中提到】 : 37 : : one
| w****0 发帖数: 803 | 9 how to get this
【在 b***e 的大作中提到】 : 37 : : one
| b***e 发帖数: 1419 | 10 First, 37 is preferred: 37 = 20 + 3 * 5 + 2, and there is no i and j where
37 = 20 * i + 3 * j, apparently.
Then prove anything greater or equal to 38 can be represented as 20 * i + 3
* j, for some positive integer i and j. This is by induction:
Base: 38 = 20 + 3 * 6.
Induction: Assume n = 20 * i + 3 * j, for some non-negative integer i and j.
There are two cases:
(1) If i is not 0, then
n + 1 = 20 * (i-1) + 3 * (j+7)
(2) If i is 0, then j >= 13, given that n >= 38, so
n + 1 = 20 * (i+2) + 3 * (j-13)
【在 b***e 的大作中提到】 : 37 : : one
| y**********a 发帖数: 824 | 11
3
j.
well done.
【在 b***e 的大作中提到】 : First, 37 is preferred: 37 = 20 + 3 * 5 + 2, and there is no i and j where : 37 = 20 * i + 3 * j, apparently. : Then prove anything greater or equal to 38 can be represented as 20 * i + 3 : * j, for some positive integer i and j. This is by induction: : Base: 38 = 20 + 3 * 6. : Induction: Assume n = 20 * i + 3 * j, for some non-negative integer i and j. : There are two cases: : (1) If i is not 0, then : n + 1 = 20 * (i-1) + 3 * (j+7) : (2) If i is 0, then j >= 13, given that n >= 38, so
| w******e 发帖数: 1621 | 12 能说一下先猜37的步骤么
我现在能想到的是用dp找 3,6,20能盖的墙,最先出现的一个a,使得a,a+1,a+2都可
以,a-1就是答案。
找最先出现的3个连续都可以的int比如
3
j.
【在 b***e 的大作中提到】 : First, 37 is preferred: 37 = 20 + 3 * 5 + 2, and there is no i and j where : 37 = 20 * i + 3 * j, apparently. : Then prove anything greater or equal to 38 can be represented as 20 * i + 3 : * j, for some positive integer i and j. This is by induction: : Base: 38 = 20 + 3 * 6. : Induction: Assume n = 20 * i + 3 * j, for some non-negative integer i and j. : There are two cases: : (1) If i is not 0, then : n + 1 = 20 * (i-1) + 3 * (j+7) : (2) If i is 0, then j >= 13, given that n >= 38, so
| a***s 发帖数: 616 | 13 可以证明40开始的都不可以。6其实没啥用,6k = 2*3k。20除以3余2。
任何一个数除以3的余数为0, 1, 或2。所以当一个数a大于等于40时,
1.余0 =〉a = 3k;
2.余1 => a-2*20 = 3k;
3.余2 => a-20 = 3k。
所以从39开始倒着考虑。
39 = 3*13 + 0
38 = 3*12 + 2 = 20 + 3*6
37 = 3*12 + 1 = 20*2 + (-1)*3 不合法
所以最大数是37
one
【在 w****0 的大作中提到】 : Suppose that you want to build a wall with bricks. The store that sells : bricks : sells them in packs of 3, 6 or 20 bricks. Suppose that you have infinite : amount of money and the store has infinite amount of bricks of each of : these packs. : You want to build the wall so that when you are finished, you want an : excess of 1 or 2 bricks.For instance, a wall of 4 bricks is a preferable one : , since you can buy a : pack of 6 bricks and has an excess of 2 bricks. Similarly, a wall with 5 : bricks
|
|