Шариковые часы.
Изобретатель создал часы, которые можно настраивать для отсчета времени. Часы состоят из шариков, желоба и трех чашек: секундной, минутной и часовой. В каждый момент времени количество шариков в чашках показывает время: секунды, минуты, часы. Каждую секунду первый шарик из желоба попадает в секундную чашку. Если секундная чашка наполнилась, то этот шарик переходит к минутной чашке, а остальные шарики переходят из секундной чашки в конец желоба в порядке, обратном к их поступлению в секундную чашку. Аналогично, при наполнении минутной чашки последний шарик переходит к часовой чашки, а остальные шарики с минутной чашки переходит в конец желоба в порядке, обратном к их поступленю в минутную чашку. Если заполняется часовая чашка, то все шарики из нее переходят в конец желоба в порядке, обратном к их поступлению в часовую чашку. Все шарики пронумерованы и в начальный момент времени находятся в желобе.
Написать программу, которая будет вычислять наименьшее количество суток, необходимых для того, чтобы исходное положение шариков в желобе повторилось.
Формат входных данных
Входной файл содержит в единственной строке натуральные числа S, M, H, K (количество секунд в минуте, минут в час, часов в сутках и общее количество шариков соответственно; S, M, H ≤ 60, S + M + H-2 ≤ K ≤ 1000).
Формат результата
Выходной текстовый файл должен содержать в единственной строке количество суток.
Пример
Вопрос:
1) надо ли программно моделировать перемещение шаров (очередь + три стека), чтобы решить задачу? Или надо подсчитать количество комбинаций (то есть за что "ухватится", какая идея решения)?
2) допустим все чашки могут содержать по 2 шарика и находятся в состоянии [1,2], [3,4], [5,6]. при добавлениий к секундной чашке шарика №7 куда перейдут шарики и какое состояние будет у всех чашек?
_>2) допустим все чашки могут содержать по 2 шарика и находятся в состоянии [1,2], [3,4], [5,6]. при добавлениий к секундной чашке шарика №7 куда перейдут шарики и какое состояние будет у всех чашек?
Я так понял, что 2 шарика в чашке находиться не может. Как только добавляем второй шарик, то тут же чашка опорожняется.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Здравствуйте, olimp_20, Вы писали:
_>Вопрос: _>1) надо ли программно моделировать перемещение шаров (очередь + три стека), чтобы решить задачу? Или надо подсчитать количество комбинаций (то есть за что "ухватится", какая идея решения)?
Можно смоделировать ровно одни сутки, тогда ты получишь в желобе перестановку исходного порядка элементов. Каждый следующий день будет просто применением этой перестановки к текущему состоянию. А задача "когда повторное применение перестановки приведет к исходному состоянию" куда более известная и решается довольно просто (без моделирования, конечно).
_>2) допустим все чашки могут содержать по 2 шарика и находятся в состоянии [1,2], [3,4], [5,6]. при добавлениий к секундной чашке шарика №7 куда перейдут шарики и какое состояние будет у всех чашек?
Такого состояния быть не может, как только в чашке становится 2 элемента она сразу опустошается (ну как с секундами, как только к 59 прибавляется 1, становится 0). А вот если вместимость чашек 3, такое состояние и добавляется 7, то в желоб пойдет сначала 7 и 2 (если чашка заполнена слева-направо, и 2 было добавлено после 1), затем 1 перейдет в минутную чашу и из нее в желоб пойдут 1 и 4, затем 3, 6 и 5. И все чашки будут пустые: 0 часов, 0 минут, 0 секунд.
Здравствуйте, olimp_20, Вы писали:
_>Шариковые часы. _>Вопрос: _>1) надо ли программно моделировать перемещение шаров (очередь + три стека), чтобы решить задачу? Или надо подсчитать количество комбинаций (то есть за что "ухватится", какая идея решения)? _>2) допустим все чашки могут содержать по 2 шарика и находятся в состоянии [1,2], [3,4], [5,6]. при добавлениий к секундной чашке шарика №7 куда перейдут шарики и какое состояние будет у всех чашек?
Разобрав пример из условия, вы смогли бы приблизиться к решению на половину:
[], [], [], [1, 2, 3, 4]
[], [], [1], [2, 3, 4]
[], [2],[], [3, 4, 1]
[], [2], [3], [4, 1]
[4], [], [], [1, 3, 2]
[4], [], [1], [3, 2]
[4], [3], [], [2, 1]
[4], [3], [2], [1]
[4, 1], [], [], [2, 3]
[], [], [], [2, 3, 1, 4]
Итак, за сутки шарики меняют свое положение с [1, 2, 3, 4] на [2, 3, 1, 4].
Каким будет расположение шариков на следующие сутки? Как называется такое преобразование?
_>Теги (не открываются) в твоем сообщении что-то должны были мне подсказать или для красоты ?
переведи эти теги и подумай как это применить на практике.