Brainteaser

[Ned]

На работе у меня внутренняя газета есть, так вот в ней запостили головоломку:

"I'm walking to the CoinStar machine with 32 quarters (0.25$) , 80 dimes (0.1$), 160 nickels (0.05$) and 800 pennis (0.01$). Quarters weight 5.7 grams, nickels weight 5 grams, pennies weigh 2.5 grams, and dimes weigh 2.3 grams. On my way, I stop to buy a burito for $7.89 . How many different ways can I pay for the burrito if I want to give the cashier coins only, exact change, and make sure the total weight of the coins is no more that 300 grams? "

Я уже свой ответ отправил, (там типа если правильно ответишь, то первые 2 получат $50 starbucks gift card). Мы тут с китайцами и тайванцами решили совмесными трудами.
Решил запостить сюда для подъема утренней производительности и расторможения.

[Triz]

2320 вариантов

самый "легкий" вариант:
31 quarters, 1 dime, 4 pennis = 189 грамм
31*0,25+1*0,1+4*0,01 = 7,75 + 0,1 + 0,04 = $7,89

самый "тяжелый" вариант:
1 quarter, 64 dimes, 22 nickels , 14 pennis = 297,9 грамм
0,25 + 64*0,1 + 22*0,05 + 4*0,01 = 0,25 + 6,4 + 1,1 + 0,14 = $7,89

[Lonely Wolf]

Неужели решил? Поделись. Я даже не представляю, с какой стороны подойти к этой задаче. По-быстрому склепанная программа на Бейсике выдала результат 2326 вариантов. А самые тяжелые (их несколько) весят ровно 300г:
Q - 12__24__16
D - 42__9___31
N - 5___14__8
P - 44__29__39

[Ned]

Неужели решил? Поделись. Я даже не представляю, с какой стороны подойти к этой задаче. По-быстрому склепанная программа на Бейсике выдала результат 2326 вариантов. А самые тяжелые (их несколько) весят ровно 300г:
Q - 12__24__16
D - 42__9___31
N - 5___14__8
P - 44__29__39

У нас ответ получился тоже 2326, узнаю правильный или нет когда получу ответ.

[Triz]

я тоже не знаю как решить )
решал с помощью Excel + макрос на VBA. тупо перебор всех комбинаций

согласен, твои варианты "тяжелее" - 300 грамм

[Ned]

я тоже не знаю как решить )
решал с помощью Excel + макрос на VBA. тупо перебор всех комбинаций

согласен, твои варианты "тяжелее" - 300 грамм

По скольку у нас решающий фактор был -время, то мы нашли python программу без учета веса, импортировали ее содержимое в openoffice spreadsheet и втупую подститали вес каждой возможной вариации, ну а потом просто фильтр применили на <= 300.

Макс, на сколько я помню мелкософтовский эксель поддерживает 64000 с копейками, вот где ты потерял 6 значений. Всего возможных путей создать 7.89 - 74000 с копейками, (без учета веса).


=====
cents = 789
denominations = [25, 10, 5, 1]
names = {25: "quarter(s)", 10: "dime(s)", 5 : "nickel(s)", 1 : "pennies"}

def count_combs(left, i, comb, add):
if add: comb.append(add)
if left == 0 or (i+1) == len(denominations):
if (i+1) == len(denominations) and left > 0:
comb.append( (left, denominations) )
i += 1
while i < len(denominations):
comb.append( (0, denominations) )
i += 1
print " ".join("%d %s" % (n,names[c]) for (n,c) in comb)
return 1
cur = denominations
return sum(count_combs(left-x*cur, i+1, comb[:], (x,cur)) for x in range(0, int(left/cur)+1))

print count_combs(cents, 0, [], None)
==============

[Lonely Wolf]

Все-таки есть какая-то закономерность в числах. Вот, например, 5 вариантов по 300г:

Q - _8___12___16___20___24___+4
D - 53___42___31___20___9____-11
N - _2____5____8___11___14___+3
P - 49___44___39___34___29___-5

Вот только куда все это пристегнуть - непонятно, поэтому решал так:

Q1 = 25
D1 = 10
N1 = 5
Q2 = 5.7
D2 = 2.3
N2 = 5
P2 = 2.5
Q = 31
10 D = 0
20 N = 0
30 P = 789 - Q1 * Q - D1 * D - N1 * N
IF P < 4 THEN GOTO 70
W = Q2 * Q + D2 * D + N2 * N + P2 * P
IF W > 300 THEN GOTO 60
K = K + 1
60 N = N + 1
GOTO 30
70 D = D + 1
S = Q1 * Q + D1 * D
IF S < 789 THEN GOTO 20
Q = Q - 1
IF Q >= 0 THEN GOTO 10
PRINT K
END

[Ned]

Сегодня получил ответ, 2326 - верно. Так что good job guys.

[Krutila]

Сегодня получил ответ, 2326 - верно. Так что good job guys.

Где ж тут good job? Решения то нет.. даже попыток.
Или это задача по информатике для младших классов?:)

[BelK]

Где ж тут good job? Решения то нет.. даже попыток.
Или это задача по информатике для младших классов?:)

Это высшая математика, конкретнее - комбинаторика, и логика. Вполне решабельна при наличии головы, карандаша и бумаги.
Меня подвёл карандаш