Время

14:04:40
24 May 2012
Версия для печати

Мысли наоборот

   Деление плоскости на части различными фигурами - известная задача в области компьютерных наук. Внизу на рисунке изображено несколько таких диаграмм. На рисунке 1 четыре окружности могут разделить плоскость максимум на 14 областей, четыре эллипса могут разделить плоскость максимум на 26 областей, а три треугольника - на 20 частей. Классическая задача состоит в том, чтобы найти максимальное количество областей, на которое могут разделить плоскость m фигур. Например, для окружностей известна формула m2 - m + 2. В смешанном случае (когда пересекается несколько типов фигур) максимально возможное количество областей найти также не трудно.

prb1538

   На рисунке 2 восемь областей образованы пересечением одного эллипса и одного треугольника. Здесь Вам следует решить обратную задачу. По заданному максимальному количеству областей следует найти количество эллипсов, окружностей и треугольников, которое могло их образовать.


Технические условия

   Входные данные

   Состоит из менее чем 300 строк. Каждая строка содержит 32-битовое беззнаковое целое N - максимальное количество областей, образованное m эллипсами, n окружностями и p треугольниками. Последняя строка содержит –1 и не обрабатывается. Все числа кроме –1 в последней строке положительны.

   Выходные данные

   Для каждого теста необходимо вывести две или более строк. Первая строка каждого теста содержит его номер. Каждая из следующих строк содержит три целых числа - возможные значения m, n и p, для которых образуется максимальное количество областей N. Если существует несколько решений, то их следует отсортировать сначала по возрастанию m, а потом по возрастанию n. Если решения не существует, то вывести строку “Impossible.”. Выводить следует только те решения, для которых 0m < 100, 0n < 20000 и 0p < 100.


Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 20
Сложность: 20% 40/50
Классификация: Комбинаторика

Пример

Пример входных данных

20
10
-1

Пример выходных данных

Case 1:
0 0 3
0 1 2
1 0 2
1 3 0
Case 2:
Impossible.


← Полоса Список задач Сколько точек пересечения? →