Задача C. Профессор и песок

Автор:А. Кленин, И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Профессор одной из кафедр ДВФУ разработал инновационный метод для того, чтобы определять момента завершения лекции. У профессора есть двое песочных часов. В первых песок полностью пересыпается за a минут, во вторых — за b минут. В начале лекции весь песок в часах находится внизу и профессор переворачивает первые, вторые или сразу и те и другие часы. Как только песок в каких-нибудь часах полностью пересыпался, профессор может опять перевернуть первые, вторые или сразу и те и другие часы.

К концу лекции весь песок в часах вновь должен оказаться внизу. Лекция длится T минут.

По заданным a, b и T определите искомую последовательность переворотов.

Считается, что профессор переворачивает часы мгновенно.

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Баллы будут начисляться пропорционально количеству правильных ответов в выходном файле. Решение будет полностью проверяться сразу после отправки, и участникам будут видны набранные за данную задачу баллы.

Формат входного файла

Первая строка входного файла содержит количество тестов n. Далее следует n строк с целыми числами T, a, b.

Формат выходного файла

Выходной файл должен содержать n блоков с ответами на тесты.

Первая строка каждого блока должна содержать количество действий, k. Далее должно следовать k строк с парами целых чисел ti mi в каждой, где ti — время выполнения действия, mi — одно из чисел 1, 2 или 3, обозначающее, что необходимо перевернуть первые, вторые или и те и другие часы соответственно. Для первого действия должно быть ti = 0, для остальных ti должно быть таким, что в этот момент песок хотя бы в одних часах только что полностью пересыпался вниз. Все ti должны быть различны и расположены по возрастанию.

Для каждого теста выведите такой ответ, в котором количество действий не превосходит 500. Гарантируется, что в каждом тесте такой ответ существует.

Примечание: Поскольку блоки в выходном файле находятся один за другим, то, если указать неверное k в начале блока, все последующие блоки будут восприняты как ошибочные. Поэтому в случае частичного решения задачи рекомендуется указывать k = 0 для тех тестов, ответ к которым вам найти не удалось.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
11 4 7
7 4 7

2
0 1
4 2
1
0 3

Разбор

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

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

Подход 2. Медленное решение. Рассмотрим переборное решение для данной задачи. Изначально у профессора имеется выбор: перевернуть первые часы, вторые часы или и те и другие сразу. При этом в зависимости от выбора профессора несложно вычислить, когда наступит момент времени, в который он сможет предпринять следующее действие. Таким образом, в каждый момент принятия решения имеется четыре действия (ведь можно и не переворачивать ни одни часы, а просто дождаться, пока в обоих окончательно закончит пересыпаться песок). Теперь можно реализовать переборное решение. Центральным его элементом будет рекурсивная функция, принимающая описание текущего состояния (время, прошедшее с начала, количество песка в верхней части первых часов и количество песка в верхней части вторых часов), и осуществляющая те из четырёх рекурсивных вызовов, которые возможны.

Подход 3. Динамическое программирование. Заметим, что наша рекурсивная функция может принимать не более (T + 1)(a + 1)(b + 1) различных наборов параметров (для каждого параметра его значение может быть и нулевым). А значит, можно завести трёхмерный массив булевых значений (назовём его vis), в котором отмечать те тройки параметров T1, a1, b1 для которых функция уже вызывалась. Теперь, при вызове функции с параметрами T1, a1, b1, следует проверить значение vis[T1][a1][b1] и прекратить работу, если его значение истинно. Каждый рекурсивный вызов выполняется за O(1), поэтому общая асимптотическая сложность составляет O(Tab).

Заметим, что один из параметров a1 и b1 всегда будет нулевым, поэтому можно существенно улучшить решение до O(T(a + b)).

Похожая задача была предложена на городской олимпиаде школьников Санкт-Петербурга в 2005-ом году.


0.186s 0.030s 15