Problem A. Cthulhu spawn

Author:A. Zhuplev, A. Klenin, I. Tufanov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Scientists of the Nearsea Institute of Underwater Mythology are researching the mythical creature called Cthulhu.

The creature is famous for producing many offspring known as Cthulhu spawn. Each spawn has a small round body with N radially protruding appendages. Each appendage is either a tentacle or a claw.

Two spawns are considered identical, if one of them can be rotated in such a way that the sequence of tentacles and claws will coincide with the other spawn.

For example, if we designate tentacle by "T" and claw by "C", spawns "TCTCCT" and "CCTTCT" are identical and different from spawns "TTTCCT" ad "CCTTTC".

You program must, for given N, calculate the total number of different spawns with N appendages.

Input file format

Input file contains a single integer N.

Output file format

Output file must contain a single integer — number of different spawns.

Constraints

1 ≤ N ≤ 58

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
2
2
4
6

Задача B. Перестановка в K-ой степени

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

Условие

Произведением перестановок называется их композиция: (Q * R)(X) = Q(R(X))

Для заданной перестановки P и числа K найти T = PK.

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

В первой строке входного файла содержатся два целых числа N K

Во второй строке входного файла содержатся N чисел pi, задающих перестановку P

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

Выходной файл должен содержать N чисел ti, задающих перестановку T = PK.

Ограничения

1 ≤ N ≤ 105

1 ≤ K ≤ 1018

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 2
3 1 5 4 2
5 3 2 4 1
2
4 1000000000000000000
3 4 1 2
1 2 3 4

Задача C. Восстановление скобок

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

Условие

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

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

Первая строка входного файла содержит заданный шаблон длиной не более 80 символов.

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

Выведите в выходной файл искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2 * 109.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
????(?
2

Problem D. Diversify start positions

Author:I. Tuphanov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

New Vasuki Challenge (NVC) is a race developed to make New Vasuki a new racing capital of the world. An outstanding feature of NVC is the distribution of start positions.

Let n be the number of cars taking place in NVC during the whole season. Each car has its id — integer number in range from 1 to n. A season consists of x races. Before a race each car takes a start position. There are n start positions, numbered from 1 to n.

In the beginning of a new season NVC director declares a permutation P = (p1, p2, …, pn). Before the first race car number i takes start position number i for each i from 1 to n. Before each next race start positions are permuted according to P: car which was on start position pi in the last race now goes to start position i.

Say, n = 6, x = 3, P = (4, 3, 6, 5, 1, 2). So, there will be three races and cars will stand in positions (1, 2, 3, 4, 5, 6) before the first race, (4, 3, 6, 5, 1, 2) before the second race, and (5, 6, 2, 1, 4, 3) before the third race.

A permutation P of size n is called feasible for given x iff:

For the example given above, (4, 3, 6, 5, 1, 2) is feasible because all three start position distributions are different, and if there were a forth race the distribution would be (1, 2, 3, 4, 5, 6) which already met in the first race.

Your task is to find a feasible permutation P for given n and x. If there are multiple solutions, output any of them.

Input file format

Input file contains two integers n and x.

Output file format

Output file must contain a feasible permutation. If a feasible permutation doesn't exist, output a single integer  − 1.

Constraints

2 ≤ n ≤ 103

2 ≤ x ≤ 106

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
6 3
4 3 6 5 1 2

Задача E. Домино (классика)

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

Условие

Найти количество способов замостить домино 1 × 2 поле n × m.

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

Во входном файле содержатся числа n и m.

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

В выходной файл выведите ответ.

Ограничения

1 ≤ n ≤ 16;

1 ≤ m ≤ 10;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 3
3

Задача F. Доклад с картинками

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

Условие

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

Текстовый процессор, который использует Вася, работает следующим образом. Каждая страница имеет высоту k сантиметров. Картинки располагаются одна за другой, начиная с первой страницы. Если очередная картинка не входит на текущую страницу целиком, то текстовый процессор переходит на следующую страницу.

Зная высоту каждой картинки в сантиметрах hi, определите порядок следования картинок, при котором полученный документ будет иметь наибольшее количество страниц.

В тестовом примере имеется 4 картинки с высотами 6 см, 4 см, 6 см и 4 см. Высота страницы составляет 10 см. Одно из оптимальных решений — расположить картинки в следующем порядке: 4, 4, 6, 6. Тогда первые две картинки окажутся на первой странице, а оставшиеся две картинки займут по одной странице каждая. Таким образом, весь доклад займёт 3 страницы.

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

Входной файл содержит два целых числа — n k, за которыми следуют n целых чисел — h1… hn.

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

Выходной файл должен содержать n целых чисел — высоты картинок в оптимальном порядке. Если имеется несколько оптимальных ответов, выведите любой из них.

Ограничения

1 ≤ n ≤ 15;

1 ≤ k ≤ 108;

1 ≤ hi ≤ k;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 10
4 6 4 6

4 4 6 6

Задача G. Количество инверсий последовательнсти

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

Условие

Пара элементов (Ai, Aj) последовательности AN называется инверсией, если Ai > Aj и i < j.

Напишите программу, которая по заданной последовательности AN посчитает количество инверсий.

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

В первой строке входного файла содержится число N — количество элементов последовательности

Последующие N целых чисел задают саму последовательность

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

В выходном файле должно содержаться единственное число — количество инверсий входной последовательности.

Ограничения

2 ≤ N ≤ 105

0 ≤ Ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7 1 2 5 9 13 16 20
0
2
9
1 1 2 3 8 6 1 9 9
5

Задача H. Наибольшая возрастающая подпоследовательность

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

Условие

Дана последовательность из N целых чисел. Найдите любую из ее наибольших строго возрастающих подпоследовательностей.

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

Во входном файле находится число N, а за ним следует последовательность ai из N целых чисел.

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

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

Ограничения

1 ≤ N ≤ 100000;  − 109 ≤ ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
123 456 124 124 125
3
1 4 5

Задача I. LCA

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

Условие

Дано дерево из N вешрин, все некоторым образом пронумерованы, а корень имеет номер 1. Найдите LCA для некоторых пар вершин.

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

Первая строка входного файла состоит из единственного числа N. Далее в N − 1 строке следует описание дерева: пары соединенных вершин. После этого до конца файла записаны пары номеров веришин, для которых следует найти LCA. Количество этих пар не превосходит 10^5.

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

В выходном файле для каждого запроса выведите единственное число: номер LCA.

Ограничения

1 ≤ N ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6
1 3
2 3
3 4
3 5
6 2
1 2
6 5
1
3

0.559s 0.012s 31