Задача A. Перестановка в 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

Задача B. K-ая порядковая статистика

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

Условие

K-ой порядковой статистикой N-элементной последовательности AN называется число AK, которое будет стоять на K-ом месте после упорядочивания элементов этой последовательности по возрастанию.

Последовательность AN задаётся следующим образом. A1 = P, Ai = (Ai − 1 ⋅ Q) mod V.

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

Во входном файле содержатся целые числа Q V P N K

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

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

Ограничения

V, Q ≠ 0

0 ≤ Q ⋅ V, Q ⋅ P ≤ 231 − 1

1 ≤ K ≤ N ≤ 4 ⋅ 107

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

Входной файл (input.txt) Выходной файл (output.txt)
1
343 32767 3 10 7
16478

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

Автор: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

Задача D. Код Грея

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

Условие

Дана строка, состоящая из N символов 0 и 1. Требуется построить последовательность из всех возможных строк длиной N, состоящих из 0 и 1, такую что:

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

Во входном файле содержится строка из символов 0 и 1

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

Выходной файл должен содержать 2N строк — искомую последовательность.

Ограничения

1 ≤ N ≤ 15

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
0
2
110
110
111
101
100
000
001
011
010

Задача E. Длина геодезической на N-мерной сфере

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

Условие

В N-мерном пространстве на N-мерной сфере, с центром в начале координат и радиусом R, заданы две точки. Требуется найти длину геодезической между заданными точками.

Точка задаётся в "обобщённых полярных координатах":

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

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

Во второй строке входного файла содержатся N − 1 целых чисел — координаты α1, α2, …, αN − 1 первой точки

В третьей строке входного файла содержатся N − 1 целых чисел — координаты β1, β2, …, βN − 1 второй точки

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

В выходном файле должно содержаться единственное число — длина геодезической между точками с абсолютной ошибкой не более 10 − 3.

Ограничения

2 ≤ N ≤ 10

0 ≤ φ1, φ2, …, φN − 2 ≤ 180

0 ≤ φN − 1 ≤ 360

Все углы задаются в градусах

1 ≤ R ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 10
1
181
31.415926536
2
3 10
30 45
45 60
4.796965142

Задача F. Пересечение двух прямых

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

Условие

Прямая a проходит через точки A1 (aX1; aY1) и A2 (aX2; aY2). Прямая b проходит через точки B1 (bX1; bY1) и B2 (bX2; bY2).

Требуется найти точку пересечения прямых a и b или установить что прямые параллельны.

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

Во входном файле содержаться восемь целых чисел — aX1, aY1, aX2, aY2, bX1, bY1, bX2, bY2

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

Выходной файл должен содержать:

Ограничения

0 ≤ |aXk|, |aYk|, |bXk|, |bYk| ≤ 105

A1 ≠ A2

B1 ≠ B2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
0 0  2 2  1 1  3 3
-1
2
0 0  1 1
2 3  5 6
0
3
1 1
3 5
-1 5
8 -1
2.000000000 3.000000000

Задача G. Поворот отрезка

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

Условие

Вершины отрезка AB имеют координаты (Xa; Ya) и (Xb; Yb).

Требуется найти координаты вершин отрезка A *  B *  (X * a; Y * a) и (X * b; Y * b), полученного путём поворота отрезка AB вокруг точки O (Xo; Yo) на β градусов.

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

Входной файл содержит целые числа Xa, Ya, Xb, Yb, Xo, Yo, β

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

Выходной файл должен содержать четыре вещественных числа X * a, Y * a, X * b, Y * b с точностью 10 − 3.

Ограничения

0 ≤ |Xa|, |Ya|, |Xb|, |Yb|, |Xo|, |Yo| ≤ 105

0 ≤ β ≤ 360

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1  2 2  0 0  90
-1.000000000 1.000000000 -2.000000000 2.000000000
2
1 1  2 2
0 0
45
0.000000000 1.414213562 0.000000000 2.828427125
3
7 5
11 11
9 8
180
11.000000000 11.000000000 7.000000000 5.000000000

Задача H. Точка Ферма-Торричелли

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

Условие

Для заданных трёх точек A, B, C найти такую точку O, что AO + BO + CO — минимально.

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

Во входном файле содержатся целые числа XA YA XB YB XC YC — координаты точек A, B, C соответственно.

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

Выходной файл должен содержать два числа XO YO — координаты точки O с точностью до 3-х знаков после запятой.

Ограничения

0 ≤ |XA|, |YA|, |XB|, |YB|, |XC|, |YC| ≤ 105

Никакие две точки не совпадают

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 2 0 0 2 2
2 2
2
-2 -3 1 3 4 -2
1.30120904214632 -0.720188590098661

0.555s 0.014s 27