XVIII Всеукраїнська комплексна олімпіада з математики, фізики
та інформатики

"Турнір чемпіонів"

2011 р.

Задания по информатике

Командный тур

Задача Пузырьки (BUBBLES)

Как известно, когда два пузырька различного диаметра соединены трубкой, меньший из них сдувается (а больший раздувается), пока меньший не окажется нулевого размера. Будем считать, что суммарный объём пузырьков при этом сохраняется.

Имеется конструкция, где 1‑й и 2‑й пузырьки,  а также 2‑й и 3‑й соединены трубками с кранами. Это даёт возможность разрешать/запрещать естественное перетекание газа отдельно между 1‑м и 2‑м пузырьками, отдельно между 2‑м и 3‑м. Можно приоткрыть кран и закрыть в нужный момент, чтобы произошло перетекание определенного объема газа.

Требуется выяснить, можно ли добиться того, чтобы 1‑й и 3‑й пузырьки оказались одинакового размера.

Технические условия   Прграмма BUBBLES читает с клавиатуры три строки по три числа V1, V2, V3 в каждой. Каждая строка является отдельным примером, для которого надо вывести на экран  в отдельной строке либо число 1 (если возможно добиться равенства крайних пузырьков), либо 0 (если невозможно). Все объемы – целые положительные числа, не превосходящие 1000.

Пример:

Задача Почти арифметическая прогрессия (ARITHM)

Последовательность чисел называется «почти арифметической», если модуль разности между любыми двумя соседними элементами одинаков. Требуется для заданной последовательности определить можно ли переставить ее элементы таким образом, чтобы она стала «почти арифметической».

Технические условия. Программа ARITHM читает с клавиатуры целое число N (1≤N≤200000) — количество элементов в последовательности, а во второй строке – сама последовательность. Все числа в последовательности не превосходят 106  по абсолютной величине. Программа выводит на экран N чисел, определяющих «почти арифметическую» последовательность, получающуюся из исходной перестановкой элементов. Если такой перестановки не существует, выведите сообщение «No solution» без кавычек.

Пример:

Задача Триангуляция (TRIANG)

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

Задан правильный N-угольник. Пронумеруем все вершины в порядке обхода против часовой стрелки натуральными числами от 1 до N. Пусть заданы неотрицательные целые числа d1, d2­, …, dN. Требуется определить, существует ли хотя бы одна такая триангуляция, что для каждого i вершина i имеет относительно нее степень di, и если существует, то указать любую из них.

Выведите диагонали, задающие искомую триангуляцию. Каждая диагональ задается двумя числами ­– номерами вершин, которые соединяет эта диагональ. Каждая диагональ должна выводиться в отдельной строке. Номера вершин разделяются одним пробелом. В случае, если триангуляции с заданными степенями вершин не существует, выведите одно число 0.

Технические условия.  Программа TRIANG в первой строке читает с клавиатуры целое число N (3≤N≤200000), во второй строке – N целых чисел d1, d2­, …, dN (0≤di≤N).

Программа выводит на экран К – количество диагоналей, задающих искомую триангуляцию, а далее – K строк с диагоналями.  Каждая диагональ задается двумя числами ­– номерами вершин, которые соединяет эта диагональ и выводится в отдельной строке. Номера вершин разделяются одним пробелом. В случае, если триангуляции с заданными степенями вершин не существует, выведите одно число  -1.

Пример: