Задача 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$) по увеличению их длины, а в случае двух путей одинаковой длины — их упорядочим в лексикографическом порядке. Найдите первые $2$ пути в этом списке (гарантируется, что путей будет не меньше $2$). Первая строка входного файла содержит два целых числа $N$ — количество городов, $M$ — количество дорог ($1 \le N \le 20$, $0 \le M \le N(N - 1)$). Следующие $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$). Числа в строках разделены пробелами. В выходной файл выведите $2$ строки — пути, как они идут в списке. Первое число в каждой строке — $K$ — количество городов в найденном пути, следующие $K$ чисел — номера городов в том порядке, в котором они идут в найденном пути. Числа в строках должны быть разделены пробелами. Вход

4 4
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$ — белый. На следующих $N$ строках расположены по $M$ целых чисел в пределах от $1$ до $2$ — цвета соответствующих клеток поля в начальной раскраске. На следующих $N$ строках расположены по $M$ целых чисел в пределах от $1$ до $2$ — цвета соответствующих клеток поля в конечной раскраске. Числа в строках разделены пробелами. Если игру можно выиграть выведите $N$ строк по $M$ целых чисел от $0$ до $1$, разделенных пробелами — сколько раз нужно нажать соответствующую клетку. Если игру выиграть нельзя выведите \t{No solution}. Вход

2 2
2 1
1 2
1 1
1 1

Ответ

0 1
0 0

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

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

5
>><<

Ответ

3 2 1 4 5

Задача E. Нолики

Найдите минимальное число $X$ такое, что если выписать все числа от $1$ до $X$, то количество выписанных цифр $0$ будет не меньше $S$. Входной файл содержит одно целое число $S$ ($1 \le S \le 10^{18}$). Выходной файл должен содержать одно целое число $X$. Вход

1

Ответ

10

Вход

2

Ответ

20

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

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

1
xabcd
aefdz

Ответ

No solution

Вход

2
xabcd
aefdz

Ответ

ad