Задачка

(бесконечность)

в наличии у него имеется ровно по одной купюре каждого достоинства

Пусть купит ресторан и не сношает людям мозги.

k стремится к бесконечности

Как уже говорил static_lab, представляете стоимость в троичной системе, затем пробегаетесь по разрядам, начиная с младшего, и, если находите цифру «2», обнуляете этот и все младшие разряды, добавляя соответственно 1 к старшему разряду.

Не совсем понял условия задачи. Официанта устроят чаевые в размере 1 трита если сумма всего счета составляет 37 тритов?

да.

Хм. Я неправильно посчитал, но. кажется, начинаю улавливать суть задачи. Если сумма счета составила 37 тритов, то заплатив 27+9+3 трита официанту достанется 2 трита чаевых. Это его не устроит, так?

Если сумма будет 37 тритов, переведя эту цифру в троичную систему, получим: 37 = 1101₃, т.е. чтобы и официанту сдача осталась, и самому не пролететь, надо заполнить самый младший нулик единицей. Получим 1111₃ = 27+9+3+1 = 40 тритов. Официанту достанется сдача - 3 трита.

так

Хм. Я обдумывал идею с многочленами, но ваша идея нагляднее и проще =)

Там, кстати, с чаевыми небольшая проблемка. Допустим, надо заплатить 43 чатла, в троичной системе это 1121₃. Видим двоечку в первом разряде и начинаем потихоньку сносить (как мною предложено в первый раз), в итоге получаем 10000₃, т.е. аж 3⁴=81 чатл. Официант нагло заберет 81-43 = 38 чатлов (1102₃), а ему такая сумма не нравится, т.е. ему, опять-таки, «округляем» сдачу и получаем 1110₃ = 39 чатлов.

И тут мы впадаем в рекурсию, т.к. нам придется отдать официанту еще одну купюру в 3 чатла, плюс еще 1 чатл официант заберет со сдачи, но останется 1 чатл - непонятно куда его девать…

Тогда утром попробую свою идею довести до ума. Если раньше никто решение не предложит. Хотя там тоже не предвидится легких путей.

Первое, что приходит на ум, это решать через диофантовы уравнения. Эта идея просто напрашивается, но они же страшные, как черти и вообще хреново решаются.

И тут мы впадаем в рекурсию

С этого места не понял — 10001 платим, 1110 забирает официант, кто недоволен?

http://en.wikipedia.org/wiki/Knapsack_problem

Тьфу ты, про размен я как-то не догадался :)

Чаевые обязательно меньше суммы?

нет

> Нужно так оплатить счет, чтобы угодить официанту.

⌈log₃ n⌉ уже предлагали? :)

если я правильно понял задачу:

s=100 # сумма к оплате

t=0
p=1
while [[ $s != 0 ]]; do
    case $(($s % 3)) in
        1) ((t += p)) ;;
        2) ((++s)) ;;
    esac
    ((p *= 3))
    ((s /= 3))
done

echo $t

;)

Что-то я не понял. Это какой язык? А $s % 3 это остаток от целочисленного деления? Почему тогда не рассматривается случай, когда остатка нет?

> Что-то я не понял. Это какой язык?

/bin/bash

я догадался уже. Спасибо. Bash под рукой не оказалось, так что переписал ваше решение на VB.Net. Не возражаете?

Приведу таблицу результатов для первых 100 чисел:
s: t
1: 1
2: 3
3: 3
4: 1
5: 9
6: 9
7: 1
8: 9
9: 9
10: 1
11: 3
12: 3
13: 1
14: 27
15: 27
16: 1
17: 27
18: 27
19: 1
20: 3
21: 3
22: 1
23: 27
24: 27
25: 1
26: 27
27: 27
28: 1
29: 3
30: 3
31: 1
32: 9
33: 9
34: 1
35: 9
36: 9
37: 1
38: 3
39: 3
40: 1
41: 81
42: 81
43: 1
44: 81
45: 81
46: 1
47: 3
48: 3
49: 1
50: 81
51: 81
52: 1
53: 81
54: 81
55: 1
56: 3
57: 3
58: 1
59: 9
60: 9
61: 1
62: 9
63: 9
64: 1
65: 3
66: 3
67: 1
68: 81
69: 81
70: 1
71: 81
72: 81
73: 1
74: 3
75: 3
76: 1
77: 81
78: 81
79: 1
80: 81
81: 81
82: 1
83: 3
84: 3
85: 1
86: 9
87: 9
88: 1
89: 9
90: 9
91: 1
92: 3
93: 3
94: 1
95: 27
96: 27
97: 1
98: 27
99: 27
100: 1

Всю таблицу лень анализировать, но для s=27 результат явно плохой.

> переписал ваше решение на VB.Net. Не возражаете?

Facepalm.Net ....

1 1
2 3
3 3
4 4
5 9
6 9
7 10
8 9
9 9
10 10
...

Задача для дебилов.

Запишем n в троичной системе, где есть только {0,+,-}. Её нужно дополнить числом, содержащим лишь {0,+}, чтобы получить число вида {0,+}.

В чем проблема-то? Есть +0++---0-0+, чаевые получаем, ставя везде на место - +, а на место остальных цифр нули. 0000+++0+00. Итого к оплате +0++000000+.

И правда, веселый VB.Net. Стоило только понадеяться на его благоразумие и опустить объявление типов, как он сразу же подложил мне свинью. Как только указал, что работать надо с Integer все исправилось. Однако, суть претензий не изменилась:

2:3
3:3
4:4
5:9
6:9
7:10
8:9
9:9
10:10
11:12
12:12
13:13
14:27
15:27
16:28
17:27
18:27
19:28
20:30
21:30
22:31
23:27
24:27
25:28
26:27
27:27
28:28
29:30
30:30
31:31
32:36
33:36
34:37
35:36
36:36
37:37
38:39
39:39
40:40
41:81
42:81
43:82
44:81
45:81
46:82
47:84
48:84
49:85
50:81
51:81
52:82
53:81
54:81
55:82
56:84
57:84
58:85
59:90
60:90
61:91
62:90
63:90
64:91
65:93
66:93
67:94
68:81
69:81
70:82
71:81
72:81
73:82
74:84
75:84
76:85
77:81
78:81
79:82
80:81
81:81
82:82
83:84
84:84
85:85
86:90
87:90
88:91
89:90
90:90
91:91
92:93
93:93
94:94
95:108
96:108
97:109
98:108
99:108
100:109

На s=27 все еще осечка.

Неверно же. Занулять надо долги ресторана по каждому разряду, делая их чаевыми.

Очень хорошо. Возьмем число +000, каким числом его нужно дополнить по вашему правилу, чтобы получить правильный ответ?

>>Knapsack_problem

Вообще никаким боком это тут.

Существует минимум аж 7 вариантов дополнить его до числа вида {0,+}. Тебе их перечислить, или ты на VB.NET опять писать собрался?

Я и без тебя могу дополнить до правильного решения. Я прошу описать общее правило, которое можно было бы использовать для любой суммы счета.

Занулять надо долги ресторана по каждому разряду, делая их чаевыми.

Не распарсил.

> > (бесконечность)

> в наличии у него имеется ровно по одной купюре каждого достоинства

Пусть купит ресторан и не сношает людям мозги.

Плюсую.

Хотя вообще по сути это одно и то же. С - нагляднее просто, чем с {0, 1, 2}.

Не сказал бы. Нагляднее представить число как число, а не как набор непонятных значков. У вас же не 60-тиричная система, а троичная. Цифр хватает.

В троичной-то системе как раз нагляднее некуда. Минус это долг.

В олимпиадных задачах на взвешивание это признак груза на другом плече весов.

> На s=27 все еще осечка.

чего? о_О

зы: s — сумма за жрачку + минимальные чаевые. т.е. сумма, которою необходимо пофиксить, чтобы отвечала требованиям.

ззы: чтобы получить минимальную сумму, там ещё t нужно в 0 сбрасывать при инкременте s…

Это просто количество купюр данного номинала. Скажем, 121₃ - это 1 купюра в один чатл, 2 купюры в 3 чатла и одна купюра в 9 чатлов.

А в вашей записи получается +-+, т.е. да - действительно, второй купюры в 3 чатла нам не хватает, но как-то оно выглядит не очень.

Хотя, конечно, после «округления» получаем: 1) 200₃ или -00, 2) 1000₃ или +000

По-моему, все-таки, с цифрами удобнее: по крайней мере, для перевода числа в троичную систему.

злой ты, совсем официанта без чаевых оставляешь

#include <stdio.h>
int main() {
	int bill;
	printf("bill = ");
	scanf("%d", & bill);
	int tip = 0;
	int tipsize;
	printf("payment =");
	for (int i = 0; !(!bill && tip); i++) {
		if ((!(bill % 3)) && (!tip)) {
			tip = 1; tipsize = i;
			printf(" 3^%d", i); if (bill / 3) printf(" +");
		}
		else if (bill % 3) { printf(" 3^%d", i); if (bill / 3) printf(" +"); }
		bill /= 3;
	}
	printf("\ntipsize = 3^%d\n", tipsize);
	return 0;
}

Пойдет или где-то ошибся?

Тогда я вообще не понимаю, какую задачу решает ваш алгоритм. Я то думал, что s - это сумма счета, t - сумма чаевых, которые нужно дать официанту. Именно так ведь звучат условия задачи. На входе имеем сумму счета, на выходе сдачу официанту, удовлетворяющую условиям задачи.

>>121 А в вашей записи получается +-+

получается +--+, и не нам ее не хватает, а ресторан нам их должен в виде сдачи после оплаты суммы +00+

не тормози же

bill = 63
payment = 3^0 + 3^2 + 3^3
tipsize = 3^0

Что-то не так.

> Тогда я вообще не понимаю, какую задачу решает ваш алгоритм.

смотри, объясняю на пальцах… тебе выставили счёт, к нему нужно прибавить минимальные чаевые и отдать это всё официантке. но официантка вредная, если сумма (общая) её не понравится, может в следующий раз и таракана в борщ подкинуть. поэтому сумму нужно пофиксить так, чтобы официантке она понравилась. вот этим мой алгоритм и занимается — ищет суму, которая нравится официантке (t). ферштейн?

если тебе нужно получить список монет, переведи результат в троичную систему счисления, и если в таком числе i-й разряд равен единице, добавляешь монету достоинства 3^i.

Есть +0++---0-0+, чаевые получаем, ставя везде на место - +, а на место остальных цифр нули. 0000+++0+00. Итого к оплате +0++000000+.

По этому алгоритму получим для суммы {+-} (5) сумму чаевых {0+} (1), а к оплате - {-0} (6), что неверно.

Значит, погорячился. Двойку в остатке не разобрал.

Замечательно. А теперь огласи, какой результат выдает твоя программа для s=27 и что он означает?

очевидно же, выдаст 27. эта сумма официантке понравится, ведь её можно составить с монет так, чтобы не было монет одинакового номинала. а именно — одна единственна монета в 27 тритов.

Хм.

Там, кстати, с чаевыми небольшая проблемка. Допустим, надо заплатить 43 чатла, в троичной системе это 1121₃. Видим двоечку в первом разряде и начинаем потихоньку сносить (как мною предложено в первый раз), в итоге получаем 10000₃, т.е. аж 3⁴=81 чатл. Официант нагло заберет 81-43 = 38 чатлов (1102₃), а ему такая сумма не нравится, т.е. ему, опять-таки, «округляем» сдачу и получаем 1110₃ = 39 чатлов.

Тут не совсем верно. Я пришел к такому преобразованию: Пусть счет на сумму 43 трита. В троичной системе счисления имеем 1121. Наша задача состоит в том, чтобы набрать эту сумму использовав монеты каждого достоинства только один раз. Начинаем преобразования: 1121 -> 1201 -> 2001 -> 10001. Если последнее число переведем в десятичную систему счисления, то получим 82, что на 39 тритов больше, чем сумма счета и полностью устраивает официанта.

То есть общее правило такое: переводим сумму счета в троичную систему счисления. Начинаем двигаться по разрядам от младших к старшим. Если по пути встречаем 2, то прибавляем к числу 3^n, где n - разряд, в котором мы встретили двойку. Продолжаем уже с новым числом (рассматривать младшие разряды при этом уже не нужно), пока не избавимся от всех двоек. Теперь ищем первый ноль. Если находим его, то мы уже получили ответ и его осталось только привести к десятичной системе счисления. Если же ноль не встретился и мы имеем число вида 111111...1111, то единственный минимальный способ удовлетворить официанта - прибавить 1 справа (то есть дать ему чистую монету достоинством большем, чем стоил весь обед). Пример: на входе имеем сумму 40 тритов. Это 1111 в троичной системе -> ответ будет 11111 -> 121 трит, из которых 40 пойдет на оплату счета, а одна монета достоинством 81 трит пойдет на чаевые. Так что я не всегда официанта обижаю.

А сколько же тогда будет стоить обед? Если всю сумму вы собираетесь отдать официантке?

5 это +--, чудо. Осиль уже balanced ternary system.