Задача A. Сумма с перестановкой ≡

Автор:Методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Заданы три числа: a, b, c. Необходимо выяснить, существуют ли такие числа x и y, что:

  1. x получается перестановкой цифр числа a;
  2. y получается перестановкой цифр числа b;
  3. x и y не содержат лидирующих нулей;
  4. x + y = c.

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

Входной файл содержит целые числа a b c.

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

Если искомые числа существуют, вывести в первую строку выходного файла слово YES, а во вторую — числа x y, разделённые пробелом. В противном случае вывести слово NO.

Ограничения

1 < a, b, c < 109

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
12 31 25
 
YES
12 13
2 
12 31 26
 
NO

Problem B. Water pipe ≡

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:200 Mb
Output file:output.txt  

Statement

The Eastowner city is perpetually haunted with water supply shortages, so in order to remedy this problem a new water-pipe has been built. Builders started the pipe from both ends simultaneously, and after some hard work both halves were connected. Well, almost. First half of pipe ended at a point (x1, y1), and the second half — at (x2, y2). Unfortunately only few pipe segments of different length were left. Moreover, due to the peculiarities of local technology the pipes can only be put in either north-south or east-west direction, and be connected to form a straight line or 90 degree turn. You program must, given L1, L2, … Lk  — lengths of pipe segments available and C1, C2, … Ck  — number of segments of each length, construct a water pipe connecting given points, or declare that it is impossible. Program must output the minimum required number of segments.

Input file format

Input file contains integers x1 y1 x2 y2 k followed by 2k integers L1 L2 … Lk C1 C2 … Ck

Output file format

Output file must contain a single integer — the number of required segments, or −1 if the connection is impossible.

Constraints

1 ≤ k ≤ 4, 1 ≤ xi, yi, Li ≤ 1000, 1 ≤ Ci ≤ 10

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
20 10 60 50 2 70 30 2 2
 
4
2 
5 5 5 6 1
2 10
 
-1

Задача C. Разрезанная рамка ≡

Автор:А. Кленин   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Прямоугольная рамка была разрезана на N кусков. Каждый кусок может представлять собой либо отрезок прямой, либо "уголок" — два отрезка, соединённых под прямым углом.

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

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

Входной файл содержит число кусков N, за которым следуют N пар целых чисел ai bi, описывающих длину двух отрезков "уголка" i-го куска. Если кусок является отрезком, то ai = 0 либо bi = 0.

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

Выходной файл должен содержать два положительных целых числа W H — ширину и высоту рамки, при этом W ≥ H. Если решения не существует, следует выдать число −1. Если решений несколько, следует выдать решение с максимальным значением W.

Ограничения

1 ≤ N ≤ 10, 0 ≤ ai, bi ≤ 100

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
10
1 1  1 1
1 0  1 0  1 0  1 0
0 2  0 2  0 2  0 2
 
7 1
2 
5
1 1  1 1  1 1  1 1  5 0
 
-1
0.120s 0.008s 17