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

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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), в котором отмечать те тройки параметров T₁, a₁, b₁ для которых функция уже вызывалась. Теперь, при вызове функции с параметрами T₁, a₁, b₁, следует проверить значение vis[T₁][a₁][b₁] и прекратить работу, если его значение истинно. Каждый рекурсивный вызов выполняется за O(1), поэтому общая асимптотическая сложность составляет O(Tab).

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

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