Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 27
(x-c)/a. Из этого очевидно, что x мог бы иметь значения начиная с величины с и дальше с шагом a.
Мне не очевидно: (0-3)/3;(1-3)/2, где здесь начало с величины с?
Дальнейшие рассуждения понял очень смутно, особенно в части округлений. На грани интуиции: у вас есть два периодических ряда, с чего вы решили, что они где-то перескутся именно в узловых точках, а не будут постоянно пересекаться в дробных? То есть, что уравнение вообще имеет решение в целых числах: иррациональные числа тоже можно очень долго приближать делением, но процесс этот не закончится.
где здесь начало с величины с?при x<c значение дроби будет отрицательным, условие задачи предполагает все числа целыми и положителньными: помимо a<b<c<x я хотел было добавить a,b,c,x Є N, но подумал, что это уже чересчур.
Согласен, в общем виде отрицательные значения можно предусмотреть, но сам подход с линейной y3 от этого не изменится, и, повторюсь, я хотел показать метод на конкретном примере, поскольку от учёта всех возможных вариантов, повествование стало бы ещё запутанней.
То есть, что уравнение вообще имеет решение в целых числахэту возможность я как-то упустил; как проверю, допишу в UPD (спасибо за подсказку)
с чего вы решили, что они где-то перескутся именно в узловых точках
как проверю, допишу в UPDДа нет же, чего это я?.. Из условия же видно, что y1=x проходит, через все целые значения. Величины a, b и c — тоже целые, а следовательно, и все значения функции y2. Откуда взяться дробным решениям, если обе функции принимают лишь целые значения? (Вы ведь их имели в виду под «узловыми точками»?)
А зачем так сложно? Графики, формулы. Сложно все это.
Все же гораздо проще делается.
Алгоритм словами:
Цена полной бутылка full
Цена пустой empty
У нас на последний день есть N денег.
Чтобы получить минимальное количество денег требуемое в предыдущий день максимизируем сдачу. Т.к. сдача переходит на новый день полностью, а деньги от бутылок уменьшаются. У нас цена пустой меньше цены полной бутылки.
Исходя из этого максимизируем сдачу.
Максимально возможная сдача full-1.
Реальная сдача должна быть такой, чтобы бюджет-реальная сдача была кратна цене пустой бутылки. Ну или перефразируя остаток от деления на цену пустой бутылки был 0.
сдача_которую_мы_не_можем_взять = (бюджет_этого_дня — максимально_возможная_сдача) % empty
Если 0, то реальная сдача = максимальной возможной сдаче, иначе реальная сдача = максимально возможная сдача минус (цена пустой минус это число).
деньги полученные от сдачи бутылок = бюджет — реальная сдача.
в предыдущий день выпито = деньги полученные от сдачи бутылок/empty*full
в предыдущий день было = в предыдущий день выпито + реальная сдача.
Или тоже самое на java:
Код сделан на коленке, так чтобы максимально просто читать его было.
PS: Расчет реально возможной сдачи можно попроще сделать, но лень уже.
Все же гораздо проще делается.
Алгоритм словами:
Цена полной бутылка full
Цена пустой empty
У нас на последний день есть N денег.
Чтобы получить минимальное количество денег требуемое в предыдущий день максимизируем сдачу. Т.к. сдача переходит на новый день полностью, а деньги от бутылок уменьшаются. У нас цена пустой меньше цены полной бутылки.
Исходя из этого максимизируем сдачу.
Максимально возможная сдача full-1.
Реальная сдача должна быть такой, чтобы бюджет-реальная сдача была кратна цене пустой бутылки. Ну или перефразируя остаток от деления на цену пустой бутылки был 0.
сдача_которую_мы_не_можем_взять = (бюджет_этого_дня — максимально_возможная_сдача) % empty
Если 0, то реальная сдача = максимальной возможной сдаче, иначе реальная сдача = максимально возможная сдача минус (цена пустой минус это число).
деньги полученные от сдачи бутылок = бюджет — реальная сдача.
в предыдущий день выпито = деньги полученные от сдачи бутылок/empty*full
в предыдущий день было = в предыдущий день выпито + реальная сдача.
Или тоже самое на java:
private int minPrevDayBudget(int full, int empty, int curDayBudget) {
int maxPossibleChange = full-1;
int extraChange = (curDayBudget-maxPossibleChange)%empty;
int realChange;
if(extraChange == 0) {
realChange = maxPossibleChange;
} else {
realChange = maxPossibleChange - (empty - extraChange);
}
int bottlesPrevDay = (curDayBudget - realChange) / empty;
int moneyPrevDay = bottlesPrevDay * full + realChange;
return moneyPrevDay;
}
Код сделан на коленке, так чтобы максимально просто читать его было.
PS: Расчет реально возможной сдачи можно попроще сделать, но лень уже.
Если уж говорить о минимуме, то бутылка изначально всего одна, т.е. бюджет превышает стоимость одной, но не дотягивает до двух. И если я не ошибаюсь, то начальный бюджет можно вычислить по формуле:
Б = цена_полной_бутылки + ( цена_полной_бутылки — цена_пустой_бутылки ) * ( номер_последнего_дня — 1 )
Т.е. если, например, цена_полной_бутылки = 50, цена_пустой_бутылки = 45, то начальный бюджет Б = 50 + (50 — 45)*(5 -1) = 70.
Я, конечно, числа с потолка взял, но у меня смутное ощущение, что и цены бутылок тоже можно свести к паре простых формул. Приеду домой — ещё подумаю.
Б = цена_полной_бутылки + ( цена_полной_бутылки — цена_пустой_бутылки ) * ( номер_последнего_дня — 1 )
Т.е. если, например, цена_полной_бутылки = 50, цена_пустой_бутылки = 45, то начальный бюджет Б = 50 + (50 — 45)*(5 -1) = 70.
Я, конечно, числа с потолка взял, но у меня смутное ощущение, что и цены бутылок тоже можно свести к паре простых формул. Приеду домой — ещё подумаю.
Мой расчет имеет сложность O(n) где n — количество дней пьянки.
Как сделать о(1) я не придумал.
Как сделать о(1) я не придумал.
По Вашей схеме, d_ilyich, похоже, что упор идёт на то, что в день покупается только одна (может, я и ошибся).
Попробуйте взять меньшую цену пустой бутылки (к примеру 10), тогда по Вашей фрормуле бюджет первого дня составит 50+(50-10)*(5-1) = 210; в ПН хватает на 4 бут., а во ВТ — лишь на одну; в СР, ЧТ, ПТ же — сидим с пустыми руками.
Попробуйте взять меньшую цену пустой бутылки (к примеру 10), тогда по Вашей фрормуле бюджет первого дня составит 50+(50-10)*(5-1) = 210; в ПН хватает на 4 бут., а во ВТ — лишь на одну; в СР, ЧТ, ПТ же — сидим с пустыми руками.
Я же говорю, что взял числа с потолка, просто для примера. И да, у меня упор на 1 бутылку, что не противоречит условию задачи. Вообще, в этом случае формула начального бюджета сводится к B = 2N — 1. Правда, я не могу это строго математически доказать. Но ход рассуждений примерно таков.
Бутылка одна. Стоимость пустой меньше стоимости полной. Т.е. только сдача уменьшается. Идеальное (и, возможно, единственно верное) решение получается, когда цена новой бутылки == N, а цена пустой == (N — 1).
Бутылка одна. Стоимость пустой меньше стоимости полной. Т.е. только сдача уменьшается. Идеальное (и, возможно, единственно верное) решение получается, когда цена новой бутылки == N, а цена пустой == (N — 1).
упор на 1 бутылку, что не противоречит условию задачиверно, не противоречит, но и не исчерпывает: может быть и большее бутылок в день
Идеальное (и, возможно, единственно верное) решение получается, когда...Я всё же стронник тезиса, что если решение не работает с какими-то данными, то это не данные плохие, а решение неуниверсальное ;)
А я сторонник не домысливать задания, особенно когда нет возможности уточнить у того, кто выдал задание. В задании не сказано, что решение должно быть универсальным, при этом единственное ограничение — отсутствие перебора.
И, кстати, раз уж речь зашла об универсальности. Мне самому нравятся универсальные решения, особенно когда они красивые и изящные. Но в данном случае такое решение должно включать мой случай как частный. А в моём случае минимальный бюджет равен 9, тогда как в Вашем — 12.
Убеждаемся, что мой ответ верный. Начальный бюджет 9, цена полной 5, цена пустой 4.
ПН. Б = 9
ВТ. Б = 9 — 5 + 4 = 8
СР. Б = 8 — 5 + 4 = 7
ЧТ. Б = 7 — 5 + 4 = 6
ПТ. Б = 6 — 5 + 4 = 5
И, кстати, раз уж речь зашла об универсальности. Мне самому нравятся универсальные решения, особенно когда они красивые и изящные. Но в данном случае такое решение должно включать мой случай как частный. А в моём случае минимальный бюджет равен 9, тогда как в Вашем — 12.
Убеждаемся, что мой ответ верный. Начальный бюджет 9, цена полной 5, цена пустой 4.
ПН. Б = 9
ВТ. Б = 9 — 5 + 4 = 8
СР. Б = 8 — 5 + 4 = 7
ЧТ. Б = 7 — 5 + 4 = 6
ПТ. Б = 6 — 5 + 4 = 5
В задании не сказано, что решение должно быть универсальнымВерно, такого там и правда нет.
Тут Вы правы
Если я правильно понял, это ирония? Только, думаю, она не совсем уместна.
Поставлена задача минимизации. И если уж говорить об универсальном решении, то оно должно само находить подходящие цены в зависимости от исходных условий, которыми могут являться количество дней и начальное количество бутылок. А в Вашем решении, насколько я понимаю, цены задаются жёстко. Более того, поместив Ваш код в онлайн-Python, я получил ответ 31 для Python v3 и 7 для Python v2 (пробовал на разных ресурсах).
Выходит, Ваш код неуниверсален по следующим причинам.
1) Ответ не [всегда] соответствует условию задания, т.к. у Вас цены являются входными условиями, но, как я показал, может оказаться, что существуют более подходящие значения. Т.е. для соответствия условию задания (минимальному бюджету) необходимо самому угадать цены.
2) В разных версиях Python получаются разные ответы при одинаковых входных данных.
P.S.
Поставлена задача минимизации. И если уж говорить об универсальном решении, то оно должно само находить подходящие цены в зависимости от исходных условий, которыми могут являться количество дней и начальное количество бутылок. А в Вашем решении, насколько я понимаю, цены задаются жёстко. Более того, поместив Ваш код в онлайн-Python, я получил ответ 31 для Python v3 и 7 для Python v2 (пробовал на разных ресурсах).
Выходит, Ваш код неуниверсален по следующим причинам.
1) Ответ не [всегда] соответствует условию задания, т.к. у Вас цены являются входными условиями, но, как я показал, может оказаться, что существуют более подходящие значения. Т.е. для соответствия условию задания (минимальному бюджету) необходимо самому угадать цены.
2) В разных версиях Python получаются разные ответы при одинаковых входных данных.
P.S.
Мой ответ, когда начальное количество бутылок == 2
цена_полной = 5, цена_пустой = 4.
ПТ. Б = 6 — 1*5 +1*4 = 5
ЧТ. Б = 7 — 1*5 +1*4 = 6
СР. Б = 8 — 1*5 +1*4 = 7
ВТ. Б = 10 — 2*5 + 2*4 = 8
ПН. Б = 10
Общая формула: B = 2N
ПТ. Б = 6 — 1*5 +1*4 = 5
ЧТ. Б = 7 — 1*5 +1*4 = 6
СР. Б = 8 — 1*5 +1*4 = 7
ВТ. Б = 10 — 2*5 + 2*4 = 8
ПН. Б = 10
Общая формула: B = 2N
Мой ответ, когда начальное количество бутылок == 3
цена_полной = 3, цена_пустой = 2.
ПТ. Б = 4 — 1*3 +1*2 = 3
ЧТ. Б = 6 — 2*3 +2*2 = 4
СР. Б = 8 — 2*3 +2*2 = 6
ВТ. Б = 11 — 3*3 + 3*2 = 8
ПН. Б = 11
Общая формула: не нашёл.
ПТ. Б = 4 — 1*3 +1*2 = 3
ЧТ. Б = 6 — 2*3 +2*2 = 4
СР. Б = 8 — 2*3 +2*2 = 6
ВТ. Б = 11 — 3*3 + 3*2 = 8
ПН. Б = 11
Общая формула: не нашёл.
подходящие цены в зависимости от исходных условий, которыми могут являться количество дней и начальное количество бутылокисходными условиями являются к-во дней (равное 5), цены на пиво и тару (это тоже условие) и то, что в последний день остаётся денег ровно на одну бутылку. В задаче спрашивается одно — исходная сумма; про поиск подходящих цен — там ни слова. Очевидно, Вы искали решение для другой задачи. Более того, задачу я привёл лишь для примера — основонй целью статьи (см.название) было отыскание метода рашнения уравнений, с целочисленным делением. И по моему скромному мнению Cashey и BugM предложили подходы, позволяющие решать уравнения вида x = a(x//b)+c без перебора. Может быть и Ваш метод позволяет его решить для произвольных a,b,c,x Є N, где a<b<c<x?
В посте пример написан на Python3 и лишь для илюстрации моего хода мысли, не более.
1. Дело в том, что задание допускает разные трактовки. Ваша трактовка:
Моя трактовка:
Т.е. я был не совсем прав, назвав Ваше решение неуниверсальным. Оно универсально, но для Вашей трактовки. А для моей неуниверсально.
2. ИМХО в данном случае всеобъемлющее != универсальное. Поясню.
Всеобъемлющим был бы вариант, позволяющий свободно манипулировать всеми входными данными, т.е. задавать допустимые интервалы значений для всех параметров. Однако, думаю, в таком варианте могли бы возникать случаи, не имеющие решения. Т.е. дело бы свелось к перебору.
3. Моя слабость в том, что, в отличие от птицы говоруна, я не отличаюсь [особым] умом и сообразительностью :) Мне кажется, что для моей трактовки можно найти общее решение в виде формулы (или нескольких). Просто моих знаний и способностей не хватает для выявления общей закономерности и доказательства.
Найти минимальное значение бюджета при ценах, которые программисты вспомнили
Моя трактовка:
Найти минимальное теоретически возможное значение бюджета при ценах, которые программисты теоретически могли бы вспомнить.
Т.е. я был не совсем прав, назвав Ваше решение неуниверсальным. Оно универсально, но для Вашей трактовки. А для моей неуниверсально.
2. ИМХО в данном случае всеобъемлющее != универсальное. Поясню.
Всеобъемлющим был бы вариант, позволяющий свободно манипулировать всеми входными данными, т.е. задавать допустимые интервалы значений для всех параметров. Однако, думаю, в таком варианте могли бы возникать случаи, не имеющие решения. Т.е. дело бы свелось к перебору.
3. Моя слабость в том, что, в отличие от птицы говоруна, я не отличаюсь [особым] умом и сообразительностью :) Мне кажется, что для моей трактовки можно найти общее решение в виде формулы (или нескольких). Просто моих знаний и способностей не хватает для выявления общей закономерности и доказательства.
1. Теперь согласен. Вы же можете для своей трактовки написать отдельный пост, чтоб не вносить путаницу стороенней задачей тем, кто зайдёт почитать, «а что же там в комментариях пишут?» и заблудится в двух разных «трактовках».
2. Я говорил не про всеобъемлющее, а исчерпывающее решение: т.е. то, которое подразумевает наличие ответа при всех комбинациях заданных параметров, принимающих значения в пределах, установленных условиями. А вообще, мне жаль, что большинство в обсуждении останавливается на «задачке» и забывает про суть поста: решение абстрагированного уравнения x = a(x//b) + c. Так мы постепенно скатываемся в оффотоп.
3. Я обратил внимание, что Вы преимущественно мыслите инткитивно. Что ж, тут каждому своё: порой за деревьями и леса не видишь, если мыслишь чересчур конкретно… Но это уже патетика — предлагаю остановиться или хотябы перевести дальнейший диалог в личку.
2. Я говорил не про всеобъемлющее, а исчерпывающее решение: т.е. то, которое подразумевает наличие ответа при всех комбинациях заданных параметров, принимающих значения в пределах, установленных условиями. А вообще, мне жаль, что большинство в обсуждении останавливается на «задачке» и забывает про суть поста: решение абстрагированного уравнения x = a(x//b) + c. Так мы постепенно скатываемся в оффотоп.
3. Я обратил внимание, что Вы преимущественно мыслите инткитивно. Что ж, тут каждому своё: порой за деревьями и леса не видишь, если мыслишь чересчур конкретно… Но это уже патетика — предлагаю остановиться или хотябы перевести дальнейший диалог в личку.
Ваш подход, BugM, тоже работает. Как и у Cashey (из этого комментария), он основан на максимальной сдаче. Что же касается
А вообще, спасибо за ответ и решение!
В свою орчередь спрошу: сможете ли Вы распространнить свой метод на решение уравнений с целочисленным делением указанного вида или он применим только для данной задачи?
Графики, формулы. Сложно все этоони в статье для упрощения восприятия информации: я вот, не понял с первого раза почему «реальная сдача = максимально возможная сдача минус (цена пустой минус это число)».
А вообще, спасибо за ответ и решение!
В свою орчередь спрошу: сможете ли Вы распространнить свой метод на решение уравнений с целочисленным делением указанного вида или он применим только для данной задачи?
На счет решения самого уравнения… Оно решается без графиков
x = a(x//b) + c
просто умножить обратно на b:
bx = a(x-r)+bc, где r это остаток х при делении на b
перенося х в одну сторону получаем
x(b-a) = -ar + bc= r(b-a) + b(c-r)
предполагая что b!=a (иначе решение очевидно)
x = r + b * (c-r)/(b-a)
т.е. r это любое число от 0 до b вида
r = c mod (b-a) + k(b-a)
а само число х:
x = (bc — ar) / (b-a)
Чтоб выбрать минимальное х нужно просто взять максимальное r, т.е. максимальное k
x = a(x//b) + c
просто умножить обратно на b:
bx = a(x-r)+bc, где r это остаток х при делении на b
перенося х в одну сторону получаем
x(b-a) = -ar + bc= r(b-a) + b(c-r)
предполагая что b!=a (иначе решение очевидно)
x = r + b * (c-r)/(b-a)
т.е. r это любое число от 0 до b вида
r = c mod (b-a) + k(b-a)
а само число х:
x = (bc — ar) / (b-a)
Чтоб выбрать минимальное х нужно просто взять максимальное r, т.е. максимальное k
Оно решается без графиковУ меня тоже решается без графиков — график для пояснения, как я пришёл к такому решению.
Ваш способ я разобрал (не без труда, конечно) — спасибо, мне он мне понравился. Я тоже пытался через сдачу, но не додумал, что её можно ваыразить через «c mod (b-a) + k(b-a)».
Это Ваш экспромт или подход, где-то вычитанный ранее?
А я в excel сделал
Начнем с пятницы и пойдем к понедельнику
В пятницу было денег на 1 бутылку, следовательно:
— в четверг купили: бюджет_пятницы // цена_тары
— с четверга осталась сдача: бюджет_пятницы % цена_тары
— бюджет четверга: в_четверг_купили * цена_пива + сдача_четверга
И так далее до понедельника — считаем сколько купили и сколько было сдачи в текущий день из бюджета последующего дня.
Excel тут
Начнем с пятницы и пойдем к понедельнику
В пятницу было денег на 1 бутылку, следовательно:
— в четверг купили: бюджет_пятницы // цена_тары
— с четверга осталась сдача: бюджет_пятницы % цена_тары
— бюджет четверга: в_четверг_купили * цена_пива + сдача_четверга
И так далее до понедельника — считаем сколько купили и сколько было сдачи в текущий день из бюджета последующего дня.
Excel тут
У Вас очень удачно подобрано соотношение цен пиво/тара — как раз тот случай, когда вчераняя сдача может ва разы превышать выучку от возврата тары…
Полагаю, Вы в своём рассуждении не дооценили роль сдачи ;)
в четверг купили: бюджет_пятницы // цена_тарыа что, если я предположу, что в ЧТ хватило лишь на одну бутылку и осталось сдачи столько, что добавив к ней в ПТ деньги от возврата единственной тары, хватило как раз на последнее пиво? Т.е. сдачи в ЧТ было аж 50-13=37. И следовательно, бюджет ЧТ составлял каких-то 50+37=87, а не 161, как у Вас. И что в ПН при таком раскладе было 2344 — почти в четверо меньше.
Полагаю, Вы в своём рассуждении не дооценили роль сдачи ;)
А… я похоже позаботился, чтоб программисты больше пива выпили :-)
Для уменьшения потребления пива и максимизации сдачи надо поправить:
— в четверг купили: (бюджет_пятницы — цена_пива + цена_тары) // цена_тары
новый Excel
Для уменьшения потребления пива и максимизации сдачи надо поправить:
— в четверг купили: (бюджет_пятницы — цена_пива + цена_тары) // цена_тары
новый Excel
Полагаю, Ваш уточнённый метод теперь также можно оформить в виде кода или алгоритма и тогда он послужит тем, кто позже нагуглит этот пост с обсуждениями, стремясь разобраться с решением уравнений, содержащих целочисленное деление без перебора.
Надеюсь, мне хватит усердия оформить Ваш подход в виде набора формул с условными a,b,c,x — и добавить его (в составе ещё двух предложенных здесь в комментариях) в UPD: в конце поста. Буду благодарен, если Вы, как автор идеи, поможете мне в этом (можно сюда или лучше в личку).
А пока — мой третий положительный голос ответу! +1 Спасибо :)
Надеюсь, мне хватит усердия оформить Ваш подход в виде набора формул с условными a,b,c,x — и добавить его (в составе ещё двух предложенных здесь в комментариях) в UPD: в конце поста. Буду благодарен, если Вы, как автор идеи, поможете мне в этом (можно сюда или лучше в личку).
А пока — мой третий положительный голос ответу! +1 Спасибо :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Решение уравнения с целочисленным делением без перебора