Что-то давно не решали задачки. Водолей
Тебя попросили школьнику какому-то решить ДЗ?
на сколько большие числа?
в первом приближении подойдет простейший обход в ширину по состояниям. в общем-то этим все сказано
в первом приближении подойдет простейший обход в ширину по состояниям. в общем-то этим все сказано
в первом приближении подойдет простейший обход в ширину по состояниямКак обосновать что по времени уложится? (как обосновать что для произвольного результирующего пути 10^5 площадь обхода будет меньше, чем 10^9)
~до 150, если учитывать условие.
N должно быть кратным НОД(a,b), или что-то из этой оперы.
N должно быть кратным НОД(a,b), или что-то из этой оперы.контрпример:
A: 3
B: 7
N: 4
лолчто?
последовательность команд >B, B>A даст в B - 4 литра
это не контрпример
Ну почти, я решил, но потом увидел код 5тиклассника. И офигел 
Что-то из этой оперы тут есть определенно, например, ясно, что на нод можно все сократить и задача вообще не изменится, даже последовательность переливаний та же ровно останется.
ну так наибольший общий делитель - 1.
4 кратно 1
4 кратно 1
Блин, лень вникать.
Надо представить НОД в виде d = x * A - y * B, или d = y * B - x * A (чтобы x и y были положительными). Ну и N, соответственно.
А потом как-то осуществить это вычисление, используя тот факт, что переливание - это сложение по модулю A или по модулю B.
Надо представить НОД в виде d = x * A - y * B, или d = y * B - x * A (чтобы x и y были положительными). Ну и N, соответственно.
А потом как-то осуществить это вычисление, используя тот факт, что переливание - это сложение по модулю A или по модулю B.
на сколько большие числа?Ну числа там любые инты могут быть, главное, что гарантируется, что есть решение не длиннее 10^5 (это в условии написано). Обход в ширину пройдет, конечно. Скажи только, как состояние будешь хранить.
в первом приближении подойдет простейший обход в ширину по состояниям. в общем-то этим все сказано
Ну да, я так и делал, решал линейное сравнение, но бля, задача для пятого класса 
состояние - это всего два числа. чего его хранить? проблема в том, чтобы очередь состояний хранить - ибо вдруг не хватит памяти. это уже да
ну вот я и говорю, может сможешь одним числом отделаться и битовую маску зафигачить, но все равно многовато так-то выходит.
Короче можно проще
Короче можно проще
пустой(null) массив AxB рекордов с указателем на родителя и операцию. Два сета с рекордами с полями a,b с текущей и следущей итерацией.
идём по текущей, проверяем на null шесть дочерних состояний в массиве. если null, то пишем в следущую итерацию, в массив пишем указатель на элемент и операцию.
кладём в текущий сет массив первый элемент 0,0 и null,null.
идём по текущей, проверяем на null шесть дочерних состояний в массиве. если null, то пишем в следущую итерацию, в массив пишем указатель на элемент и операцию.
кладём в текущий сет массив первый элемент 0,0 и null,null.
хэшсет можно заменить на массив. пятиклассник так бы наверно и сделал. (я привык просто что в яве массивы нельзя увеличивать)
нет, пятиклассник бы подумал о сути задачи и написал бы вообще без массивов, о том и тред
для пятиклассника, наверное, хорошее решение:
берем матричку 0..A x 0..B, заполняем ее пустыми строками
в клеточках [A, 0] и [0, B] пишем '>A' и '>B' соответственно
говорим, что у нас появилсь очередь для заполнения клеточек:
[A, 0]
[0. B]
для каждого элемент в очереди пишем в конец очереди всех его "соседей" — клеточки, куда можно попасть с помощью наших операций, при этом, если эта клеточка уже есть в списке выше или ниже (привет хеш), то не пишем ее второй раз. внося новый элемент в список, в матричку пишем программу, как попасть в эту клеточку (конкатенация программы из "соседа" и операции)
когда прошлись по всей очереди, знаем, что в ней перечислены все клеточки, куда можно попасть, а в матрице уже есть все программы.
после этого можно для любого N пройтись по кресту [N, i], [j, N] и сказать, есть ли программа.
берем матричку 0..A x 0..B, заполняем ее пустыми строками
в клеточках [A, 0] и [0, B] пишем '>A' и '>B' соответственно
говорим, что у нас появилсь очередь для заполнения клеточек:
[A, 0]
[0. B]
для каждого элемент в очереди пишем в конец очереди всех его "соседей" — клеточки, куда можно попасть с помощью наших операций, при этом, если эта клеточка уже есть в списке выше или ниже (привет хеш), то не пишем ее второй раз. внося новый элемент в список, в матричку пишем программу, как попасть в эту клеточку (конкатенация программы из "соседа" и операции)
когда прошлись по всей очереди, знаем, что в ней перечислены все клеточки, куда можно попасть, а в матрице уже есть все программы.
после этого можно для любого N пройтись по кресту [N, i], [j, N] и сказать, есть ли программа.
это все работает, но по памяти как-то жутковато выглядит пока, если честно, напомню, в качестве входных данных может выступать пара больших взаимнопростых A и B.
В общем есть много проще решение.
В общем есть много проще решение.
В общем есть много проще решение.да, я уже прочитал
но как до такого можно догадаться, пока не понял
а что прочитал? код?
нет, про бильярд.
Эх, молодость вспомнилась
Смех в том, что, как только мы начали что-то делать (скажем, сделали >A), то каждое следующее действие определяется однозначно.
Например, после первого действия, >A:
>A невозможно
A> глупо
>B будет глупо потом
B> невозможно, т.к. B еще пусто
B>A невозможно
A>B возможно
Далее два варианта событий после A>B, либо A пусто, либо B полно.
Если A пусто:
>A возможно
A> невозможно
>B невозможно
B> глупо, будут оба пустых
A>B невозможно
B>A глупо
Если B полно:
>A глупо, будет два полных
A> глупо, будет пустой A и полный B
>B невозможно
B> возможно
A>B невозможно
B>A глупо
И так далее. После >X или X> имеет смысл делать только переливание, и только одно.
После переливания делать второе переливание нет смысла, а среди остальных операций имеет смысл только одна: это или наполнение пустого сосуда, или опорожнение полного.
Рассмотрим следующий бесконечный алгоритм:
while(true)
{
если B полон, B>
иначе если A пуст, >A
иначе A>B
}
А также его зеркальное отражение, где A и B поменяны местами.
Запускаем оба алгоритма одновременно. Который из них первый придет к N - это и есть кратчайшее решение.
Можно решение не запоминать вовсе, так как генерация его занимает линейное время, и сгенерировать вторым проходом. Сложность по времени: O(E), где E - длина решения. Сложность по памяти: O(1).
Единственное, что надо добавить, это сразу проверку: если N не делится на НОД(A,B) или N>max(A,B), то решения нет.
Доказать, что в противном случае решение есть всегда, оставляю читателю. Я это сделал используя диофантово уравнение, приведенное .
Смех в том, что, как только мы начали что-то делать (скажем, сделали >A), то каждое следующее действие определяется однозначно.
Например, после первого действия, >A:
>A невозможно
A> глупо
>B будет глупо потом
B> невозможно, т.к. B еще пусто
B>A невозможно
A>B возможно
Далее два варианта событий после A>B, либо A пусто, либо B полно.
Если A пусто:
>A возможно
A> невозможно
>B невозможно
B> глупо, будут оба пустых
A>B невозможно
B>A глупо
Если B полно:
>A глупо, будет два полных
A> глупо, будет пустой A и полный B
>B невозможно
B> возможно
A>B невозможно
B>A глупо
И так далее. После >X или X> имеет смысл делать только переливание, и только одно.
После переливания делать второе переливание нет смысла, а среди остальных операций имеет смысл только одна: это или наполнение пустого сосуда, или опорожнение полного.
Рассмотрим следующий бесконечный алгоритм:
while(true)
{
если B полон, B>
иначе если A пуст, >A
иначе A>B
}
А также его зеркальное отражение, где A и B поменяны местами.
Запускаем оба алгоритма одновременно. Который из них первый придет к N - это и есть кратчайшее решение.
Можно решение не запоминать вовсе, так как генерация его занимает линейное время, и сгенерировать вторым проходом. Сложность по времени: O(E), где E - длина решения. Сложность по памяти: O(1).
Единственное, что надо добавить, это сразу проверку: если N не делится на НОД(A,B) или N>max(A,B), то решения нет.
Доказать, что в противном случае решение есть всегда, оставляю читателю. Я это сделал используя диофантово уравнение, приведенное .
Да, вот это решение для пятиклассника!
Единственно, мое имхо, круче так: без диофантова уравнения (или линейного сравнения), просто идем твоим алгоритмом, если вернулись в ситуацию "оба пустые", то решения нет.
Единственно, мое имхо, круче так: без диофантова уравнения (или линейного сравнения), просто идем твоим алгоритмом, если вернулись в ситуацию "оба пустые", то решения нет.
Кстати, я рад за тебя, что ты знаком с таким многообещающим пятиклассником.
Задай ему задачу на китайскую теорему об остатках, это похожая тема:
Задай ему задачу на китайскую теорему об остатках, это похожая тема:
Китайский император очень любил строить свою армию в колонну.
Но когда он строил ее в колонну по n1, n2, ... nK человек, все время оставались лишние солдаты в количестве r1, r2, ... rK > 0.
И только когда он построил армию в колонну по n человек, лишних солдат не осталось.
Какой минимальный возможный размер армии?
Ну решать уравнение нужно для доказательства существования. А так-то можно без него, просто посчитать НОД.
Просто без такой проверки мы проделаем НОК(A,B) операций, прежде чем убедимся в отсутствии решения, а на НОК у нас нет ограничения в 10^5
Просто без такой проверки мы проделаем НОК(A,B) операций, прежде чем убедимся в отсутствии решения, а на НОК у нас нет ограничения в 10^5
Ну ок, тогда с отсечением на 10^5 операций корректно, но там не заморачивались.
я лично не знаком, просто так получилось, что увидел. Может быть ему идею и подсказал кто.
ну, не знаю как в 5ом классе, а в шестом я написал бы рекурсией (как раз в 6ом нарисовал свою первую снежинку коха на паскале). ведь тогда я не знал, что есть http://stackoverflow.com/ ^_^
имхо рекурсией с бесконечным стеком и памятью получается элементарная задача.
гораздо круче вот решение игры загони все ящики в лоском лабиринте в домик (забыл как называется)
имхо рекурсией с бесконечным стеком и памятью получается элементарная задача.
гораздо круче вот решение игры загони все ящики в лоском лабиринте в домик (забыл как называется)
имхо рекурсией с бесконечным стеком и памятью получается элементарная задача.Это утверждение справедливо для очень широкого класса задач
гораздо круче вот решение игры загони все ящики в лоском лабиринте в домик (забыл как называется)Игра, вероятно, называется "Сокобан". Решить сокобан в общем случае- NP-трудная задача, так что лучше, вероятно, подождать хотя бы класса до 7-го
На том же StackOverflow кто-то давал ссылку на свою дипломную работу, где он составлял обзор существующих подходов к решению сокобана.
Мне кажется, в этом треде ты выглядишь слегка невежественно.
N должно быть кратным НОД(a,b), или что-то из этой оперы.1. Необходимость.
Никакое действие над полными/пустыми не может дать не кратный НОДу объём (потому что НОД можно вынести за скобки). По индукции показываем то же самое для всякого состояния системы
2. Достаточность. Построением. Переливаем в цикле воду, получаем либо доливание, либо сложение по модулю большего сосуда. Гоняем цикл пока не получится требуемый объём (количество шагов не больше max(a,b)/( nod(a,b) ))
Вообще это задачка не на динамическое программирование, а на подумать
Без перебора:
http://thedeemon.livejournal.com/45950.html
Возможно не в точности эта задача, но очень похожая.
http://thedeemon.livejournal.com/45950.html
Возможно не в точности эта задача, но очень похожая.
Мне кажется,Корректуры псто.в этом тредеты выглядишьслегканевежественно.
Комп зачастую быстрее думает.
Помню на каком-то спецкурсе мы эту задачу решали через автоматическое доказательство теорем. Типа пусть P(a, b) предикат, который обозначает что состояние (a , b) можно достичь. Переписываем правила 1-6 в виде аксиом
P(a, b) => P(A, b)
P(a, b) => P(0, b)
...
P(a, b) & a+b <= A => P(a+b, 0)
P(a, b) & a+b > A => P(A, a+b-A)
...
P(0, 0)
Дальше мы брали простенький доказатель теорем через метод резолюций, и просили его доказать P(N, 0). Если у него получалось, то по выведенному доказательству было понятно, что там куда переливать нужно
P(a, b) => P(A, b)
P(a, b) => P(0, b)
...
P(a, b) & a+b <= A => P(a+b, 0)
P(a, b) & a+b > A => P(A, a+b-A)
...
P(0, 0)
Дальше мы брали простенький доказатель теорем через метод резолюций, и просили его доказать P(N, 0). Если у него получалось, то по выведенному доказательству было понятно, что там куда переливать нужно
Оставить комментарий
Serab
Есть два сосуда емкостью A и B литров (целые числа). Можно:1. Наполнить A (записывается >A)
2. Наполнить B (>B)
3. Опустошить A (A>)
4. Опустошить B (B>)
5. Перелить из A в B, при этом либо A опустошается, либо B становится полным (A>B)
6. Перелить из B в A, аналогично.
Изначально оба сосуда пусты.
Дано число N, надо определить, возможно ли получить в одном из сосудов ровно N литров, и если возможно, найти последовательность действий для этого, если невозможно, сообщить об этом (Impossible).
Гарантируется, что если решение существует, то его можно вывести за адекватное время (в нем будет не более 10^5 операций 1-6).
Вот. Тут интересна не только алгоритмическая часть, но и написательская, но не вынуждаю писать