Симметрическая разность

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Даны два множества чисел. Выведите все такие числа из этих множеств, которые не содержатся в обоих множествах одновременно.

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

В первой строке входного файла содержится описание первого множества, а во второй строке -- второго. Каждое описание начинается с количества элементов в данном множестве. Далее следуют все элементы множества в произвольном порядке. В каждом множестве содержится хотя бы один элемент, количество элементов в каждом множестве не превосходит 1000. Все элементы множеств -- целые числа от -1000 до 1000.

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

Выведите количество искомых чисел, а затем сами числа через пробел.

Пример

Ввод

Test #1
3 1 2 3
3 2 3 4

Test #2
3 1 2 3
2 1 3

Вывод

Test #1
2 1 4

Test #2
1 2

Картины на стене

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

У программиста Пети есть две картины прямоугольной формы. Первая имеет размеры A1хB1, вторая - A2хB2. Стена, на которую Петя собирается повесить эти картины, тоже имеет вид прямоугольника размера AхB. Сможет ли Петя совершить задуманное? Картины не должны иметь внутренних общих точек. Картины можно поворачивать, но их стороны должны быть параллельны сторонам стены.

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

В первой строке входного файла содержится N (1 <= N <= 1000), обозначающее количество наборов входных данных в файле. Далее в N строках содержатся описания наборов входных данных. Каждое описание состоит из 6 натуральных чисел A1, B1, A2, B2, A, B. Каждое из этих чисел не превосходит 1000.

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

На каждый набор входных данных выведите строку. В эту строку выведите 1, если Петя может расположить картины на стене. Выведите 0 в противном случае.

Пример

Ввод

4
1 1 1 1 1 2
1 1 1 1 1 1
1 2 2 1 2 2
2 2 1 2 2 3

Вывод

1
0
1
1

Печать буклета

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Когда происходит печать документа, обычно первая страница печатается первой, вторая -- второй, третья -- третьей и так далее до конца. При создании буклета порядок печати должен быть другим. При печати буклета на одном листе печатаются четыре страницы: две -- на лицевой стороне и две -- на обратной. Когда вы сложите все листы по порядку и согнете их пополам, страницы будут идти в правильном порядке, как у обычной книги. Например, 4-х страничный буклет должен быть напечатан на одном листе бумаги: лицевая сторона должна содержать сначала страницу 4, потом -- 1, обратная -- 2 и 3.
Если в буклете число страниц не кратно четырем, то в конце можно добавить несколько пустых страниц, но так, чтобы количество листов бумаги при этом было минимально возможным.
Ваша задача -- написать программу, которая считывает из входного файла количество страниц в буклете и генерирует порядок его печати.

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

Входной файл содержит количество страниц в буклете -- натуральное число, не превышающее 500.

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

В выходной файл необходимо выдать порядок печати данного буклета -- последовательность команд, каждая из которых располагается на отдельной строке и состоит из четырех чисел. Первое число обозначает номер листа, на котором происходит печать. Второе число обозначает сторону (1 - если печать происходит на лицевой стороне, и 2 - если на обратной). Два оставшихся числа - номера страниц буклета, которые должны быть напечатаны. Пустая страница задается числом 0. Если целая сторона должна быть оставлена пустой, команду для ее печати выводить не надо.

Пример

Ввод

Test #1
1

Test #2
4

Test #3
14

Вывод

Test #1
1 1 0 1

Test #2
1 1 4 1
1 2 2 3

Test #3
1 1 0 1
1 2 2 0
2 1 14 3
2 2 4 13
3 1 12 5
3 2 6 11
4 1 10 7
4 2 8 9

Обратное преобразование

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Строку, состоящую только из символов 0 и 1, будем называть бинарной. Например, строка 011100011 -- бинарная. Один из способов ее закодировать -- это прибавить к каждой цифре в этой строке ее соседей. Строка 011100011 после кодирования будет иметь вид: 123210122. Ваша задача произвести обратное преобразование данной строки S. Если оно неоднозначно -- надо вывести все такие строки, из которых может быть получена данная.

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

В первой строке входного файла записана строка S. Ее длина -- натуральное число, не превосходящее 50.

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

В первую строку выходного файла выведите количество бинарных строк, из которых описанным преобразованием получается строка S. Далее выведите сами эти строки в лексикографическом порядке. Каждую строку выводите в отдельной строке.

Пример

Ввод

Test #1
123210122

Test #2
11

Вывод

Test #1
1
011100011

Test #2
2
01
10

Корпорация II

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

 

Структура корпорации такова, что каждый служащий, кроме служащих нижнего звена, является непосредственным начальником не менее чем одного другого служащего (возможно, служащего нижнего звена). Во главе компании стоит Президент, которому подчиняются (вероятно, косвенно, то есть по длинной цепочке) все остальные служащие. Каждый служащий (разумеется, кроме Президента) имеет одного непосредственного начальника. Структура корпорации является корпоративной тайной и строго охраняется. Однако, на сайте компании доступна следующая информация. Так как Президент компании доволен работой каждого служащего нижнего звена, он решил каждому такому служащему передать одно благодарственное письмо. Каждое благодарственное письмо преодолело путь от Президента до некоторого служащего нижнего звена. Передача писем осуществлялась от начальника его непосредственному подчиненному. На сайте доступен перечень всех путей следования писем от Президента до каждого служащего нижнего звена. Все пути записаны в одной строке, поэтому понять, где заканчивается очередной путь и начинается новый без вашей помощи довольно трудно. Все работники занумерованы индивидуальными номерами от 1 до N.
Ваша задача -- по сведениям, доступным на сайте, восстановить структуру корпорации.

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

Во входном файле содержится последовательность чисел -- перечень всех путей следования писем от Президента до каждого служащего нижнего звена в произвольном порядке. Все пути записаны в одной строке и разделяются между собой пробелом. Известно, что количество работников корпорации N удовлетворяет неравенству 2 <= N <= 10000. Гарантируется, что заданная последовательность корректна, то есть существует корпорация, ей соответствующая. Размер входного файла не превосходит 1 MB.

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

В выходной файл выведите N строк. В i-ой строке выведите список всех непосредственных подчиненных i-ого работника. Подчиненных выводите в любом порядке, но каждого подчиненного выводите ровно один раз. Список следует завершать числом 0. Если решений несколько выведите любое.

Пример

Ввод

3 4 2 3 1

Вывод

0
0
1 4 0
2 0

Пояснение

Пример соответствует рисунку. Сначала в последовательности выписан путь до служащего нижнего звена 2, затем до служащего нижнего звена 1.