Задача A. Сумма

Вовочка, как известно, любит придумывать математические задачки. Вот недавно он придумал такую: для заданного S найти все такие целые положительные $A$ и $B$, что $A \le B$ и $A + (A + 1) + (A + 2) + ... + (B - 1) + B = S$ Входной файл содержит одно целое число $S$ ($1 \le S \le 10^{12}$). Первая строка выходного файла должна содержать одно число $K$ — количество найденных пар $A$, $B$. На следующих $K$ строках должны быть по два целых числа, первое не больше второго — соответствующая пара. Пары должны выводиться в порядке увеличения первого числа. Вход

25

Ответ

3
3 7
12 13
25 25

Задача B. Путь

В стране $N$ городов. Перемещаться между ними можно только по дорогам, которые есть между некоторыми парами городов. Путем назовем список городов $A_1$, $A_2$, ... $A_K$, такой, что все города в нем различны, $K > 1$ и для всех $i < K$ есть дорога между городами $A_i$ и $A_{i + 1}$. У каждого пути есть длина — сумма длин всех дорог между соседними в пути городами. Упорядочим все возможные пути из города $1$ в город $N$ (то есть $A_1 = 1$, $A_K = N$) по увеличению их длины, а в случае двух путей одинаковой длины — их упорядочим в лексикографическом порядке. Найдите $L$ первых путей в этом списке (гарантируется, что путей будет не меньше $L$). Первая строка входного файла содержит три целых числа $N$ — количество городов, $M$ — количество дорог, и $L$ — количество путей ($1 \le N \le 20$, $0 \le M \le N(N - 1)$, $1 \le L \le 30$). Следующие $M$ строк содержат по три целых числа $S_i$, $T_i$, $C_i$ — номера городов, соединенных $i$-й дорогой и ее длина ($1 \le S_i, T_i \le N$, $S_i \ne T_i$, $1 \le C_i \le 100$). Числа в строках разделены пробелами. В выходной файл выведите $L$ строк — пути, как они идут в списке. Первое число в каждоей строке — $K$ — количество городов в найденном пути, следующие $K$ чисел — номера городов в том порядке, в котором они идут в найденном пути. Числа в строках должны быть разделены пробелами. Вход

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

Ответ

3 1 3 4
3 1 2 4

Задача C. Игра

Недавно Амир разработал новую игру. Она представляет собой поле из $N \times M$ цветных клеток. При нажатии на клетку, все соседние с ней по стороне клетки меняют цвета по следующему правилу: синий меняется на желтый, желтый — на зеленый, зеленый — на красный, красный — на черный, черный — на синий. Цель игры: из начальной раскраски поля получить заданную конечную раскраску. Ваша задача — выиграть, то есть определить, какие клетки и сколько раз нужно нажать, чтобы сделать это. Первая строка входного файла содержит два целых числа $N$ и $M$ ($1 \le N, M \le 10$). Для удобства далее цвета обозначены цифрами: $1$ — синий, $2$ — желтый, $3$ — зеленый, $4$ — красный, $5$ — черный. На следующих $N$ строках расположены по $M$ целых чисел в пределах от $1$ до $5$ — цвета соответствующих клеток поля в начальной раскраске. На следующих $N$ строках расположены по $M$ целых чисел в пределах от $1$ до $5$ — цвета соответствующих клеток поля в конечной раскраске. Числа в строках разделены пробелами. Если игру можно выиграть выведите $N$ строк по $M$ целых чисел от $0$ до $4$, разделенных пробелами — сколько раз нужно нажать соответствующую клетку. Если игру выиграть нельзя выведите \t{No solution}. Вход

2 2
2 1
1 2
1 1
1 1

Ответ

0 4
0 0

Задача D. Сравнения

$N$ различных целых чисел от $1$ до $N$ выписали на доске в ряд и расставили между ними знаки <, >, затем числа стерли, а знаки оставили. Восстановите стертые числа. Первая строка входного файла содержит одно целое число $N$ ($1 \le N \le 10^5$). Вторая строка содержит строку длиной $N - 1$ символ. Каждый символ это один из знаков сравнения < или >. В выходной файл выведите $N$ чисел разделенных пробелами — исходную последовательность. Если существует несколько вариантов ответа, выведите любой. Вход

5
>><<

Ответ

3 2 1 4 5

Задача E. Цифры

Ержан выписал все числа от $1$ до $X$ в ряд без пробелов. Затем, из каждой группы последовательных одинаковых цифр он оставил ровно одну цифру. В итоге осталось написано $S$ цифр, но Ержан забыл, до какого $X$ он выписывал числа вначале. Помогите ему — найдите $X$. Входной файл содержит одно целое число $S$ ($1 \le S \le 10^{18}$). Выходной файл должен содержать одно целое число $X$. Если нужного числа не существует выведите $-1$. Вход

13

Ответ

12

123456789101112 => 1234567891012

Задача F. Строки

Имеются две строки. Из каждой строки разрешается удалять символы, но количество подряд идущих удаленных символов не должно превышать $W$. Ваша задача — удалив минимально возможное количество символов, сделать строки одинаковыми (символы разного регистра считать разными). Входной файл содержит на первой строке число $W$ ($1 \le W \le 1500$), на второй и третьей — две заданные строки, состоящие из цифр и символов английского алфавита длиной от $1$ до $1500$ символов. Выходной файл должен содержать одну строку, которую можно получить из обеих строк по правилам задачи. Если существует несколько вариантов ответа, выведите любой. Если ответа не существует выведите \t{No solution}. Вход

1
xabcd
aefdz

Ответ

No solution

Вход

2
xabcd
aefdz

Ответ

ad