Возведение в степень по модулю

ограничение времени на тест: 0.2 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

Даны целое неотрицательное число a (a<=30000), целое положительное число n (n<=1000) и целое неотрицательное число b (b<=10^9). Известно, что a+b>0.
Требуется написать программу, вычисляющую d = a^b mod n - остаток от деления a^b на число n.

Входные данные

В единственной строке заданы через пробел три числа - a, b, и n.

Выходные данные

В единственной строке должно содержаться одно число - d.

Пример

Ввод

3 3 7

Вывод

Вредный преподаватель

ограничение времени на тест: 0.2 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

Вредный преподаватель в сессию начинает принимать экзамен у студентов, только если они выстроились по росту. Помогите студентам выстроиться в нужном порядке.

Входные данные

В первой строке содержится целое N (1<=N<=5000) - общее число студентов. Каждая i-тая строка из следующих N строк содержит имя студента Name_i (от одной до пяти букв латинского алфавита) и его рост x_i (целое число, 130<=x_i<=215). Рост студента отделен от его имени, по крайней мере, одним пробелом.

Выходные данные

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

Пример

Ввод

4
SASHA 150
MISHA 215
ANNA 158
DASHA 150

Вывод

DASHA
SASHA
ANNA
MISHA

Про определители

ограничение времени на тест: 3 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

Вычислить определитель матрицы V(x_0, x_1,..., x_{n-1}) для данных целых x_0, x_1,:, x_{n-1}

V(x_0, x_1,..., x_{n-1}) =

[ 1 x_0 x_0^2.... x_0^{n-1} ] [ 1 x_1 x_1^2.... x_1^{n-1} ] [......................................... ] [ 1 x_{n-1}.... x_{n-1}^{n-1} ]

Входные данные

Первая строка содержит число n (1<=n<=100). Вторая - n чисел x_0, x_1,:, x_{n-1}, разделенных пробелом. Числа x_1,... x_{n-1} - целые числа от 0 до 1000.

Выходные данные

Выходной файл должен содержать единственное целое число без лидирующих нулей - определитель матрицы.

Пример

Ввод

4
0 1 2 3

Вывод

В детском саду

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

В детском саду в младшей группе проводили следующий конкурс. Детям предложили табличку, в которой следующим образом записали одно и то же слово. Первое слово записано так, чтобы оно заканчивалось в правом верхнем углу таблицы. Слово во второй строке размещалось на один символ левее первого. Слово в третьей строке на один символ левее второго и так далее. Слова читаются следующим образом: начинается слово с первой буквы одной из строк; следующая буква расположена либо справа, либо снизу от предыдущей.

c h е l о v е k

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

Входные данные

В первой строке входного файла находится М - число строк. (1<=M<=10000). Во второй строке - предложенное слово длиной не менее одной буквы и не более 15 букв.

Выходные данные

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

Пример

Ввод

2
chelovek

Вывод

В поисках

ограничение времени на тест: 0.25 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

Вы планируете авиапутешествие. Вам необходимо попасть из пункта A в пункт B, попутно побывав в пункте C. Составьте искомый маршрут путешествия.

Входные данные

В первой строке записано три натуральных различных числа A, B, C. Во второй строке записаны два числа N и M (3<=N<=200; 0<=M<=N*(N-1)/2). Далее в M строках описаны все рейсы парами номеров пунктов, которые они соединяют. Все рейсы двунаправлены. Между парой городов существует не более одного рейса. Не бывает рейса из города в себя.

Выходные данные

В первой строке выходного файла выведите фразу <YES>, если искомый маршрут существует и <NO> в противном случае. Если ответ положительный выведите во вторую строку искомый маршрут. Первое число во второй строке - его длина. Если ответов несколько - выводите любой.

Пример

Ввод

1 2 3
3 2
1 2
2 3

Вывод

YES
4 1 2 3 2

192. 1/2

ограничение времени на тест: 0.3 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

Найдите такую последовательность различных натуральных чисел A_1 < A_2 <...< A_N, что 1/2 = 1/A_1^2 + 1/A_2^2 +... + 1/A_N^2.
Ищите такую последовательность, что N < 30 и 1 <= A_i <= 1000.

Входные данные

Для этой задачи нет входных данных

Выходные данные

Выведите в первой строке число N, а во второй возрастающую последовательность натуральных чисел A_1, A_2,..., A_N.

Пример

Ввод

---

Вывод

---

Box world

ограничение времени на тест: 0.75 сек.
ограничение памяти на тест: 10240 KB.

ввод: input.txt
вывод: output.txt

На поле N*M (3 <= N*M <= 100) проводится игра Socoban по вполне известным правилам. Вы управляете человечком, находящимся в лабиринте. Кроме человека в лабиринте присутствуют зловещие стены и тяжёлые коробки (коробки одинаковые, в количестве от 1 до 2 штук). Ваш персонаж обладает феноменальными способностями:
1) он может передвинуться из данного положения на пустую клетку вверх/вниз/вправо/влево (по диагонали ходить нельзя). Клетка считается пустой, если она не является ни стеной, ни коробкой.

2) он может подвинуть коробку, находящуюся рядом с ним (сверху/снизу/справа/слева) на пустое место в этом же направлении, переместившись сам на место коробки
Цель игры - расставить коробки в нужные места (в каждое место по одной коробке). Специально для вас задача усложнена - вам необходимо сделать это за минимальное количество шагов (шагом считаются пункты 1 и 2)

Обозначим человека буквой 'M', коробки буквой 'B', первоначальное положение коробок - 'X', стены - '#', а пустое место - '.'.

Входные данные

В первой строчке находятся числа: n,m. Следующие n строк содержат по m символов - это матрица, представляющая собой конфигурацию лабиринта. Количество символов 'B' обязательно равно количеству символов 'X'.

Выходные данные

Если задача не имеет решения, то вы должны вывести в выходной файл фразу 'MISSION IMPOSSIBLE'. Иначе в первой строке вы должны вывести число T - требуемое количество шагов. Затем T строчек с описаниями ходов в следующем формате:
если вы следуете пункту 1, то слово 'MOVE', если пункту 2, то слово 'PUSH'; затем через пробел - направление движения: 'LEFT'/'RIGHT'/'UP'/'DOWN'

Пример

Ввод

Test #1
2 6
.BB.XX
M#....

Test #2
2 6
...B.X
M#.B.X

Test #3
2 6
...#..
M#.B.X

Вывод

Test #1
MISSION IMPOSSIBLE

Test #2
10
MOVE UP
MOVE RIGHT
MOVE RIGHT
PUSH RIGHT
PUSH RIGHT
MOVE LEFT
MOVE LEFT
MOVE DOWN
PUSH RIGHT
PUSH RIGHT

Test #3
6
MOVE UP
MOVE RIGHT
MOVE RIGHT
MOVE DOWN
PUSH RIGHT
PUSH RIGHT

Супер-точка

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 640 KB.

ввод: input.txt
вывод: output.txt

На плоскости дано N (1 <= N <= 50) точек. Найдите такую точку, что сумма растояний до нее - наименьшая.

Входные данные

В первой строке записано целое N, далее в N строках описаны сами N точек парами своих координат. Все координаты целые, по модулю не превосходящие 10000.

Выходные данные

Выдайте координаты искомой точки с точностью 10^-3.

Пример

Ввод

4
1 0
-1 0
0 1
0 -1

Вывод

0.000 0.000

Выстрел

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

Мальчику Пете подарили пистолет, стреляющий стрелами с присоской. Петя долго тренировался и теперь легко попадает в любой неподвижный объект. Но с движущимися предметами дело обстоит гораздо хуже. В этой нелегкой проблеме ему должны помочь вы. Предположим, что Петя стоит в начале координат, а объект, в который нужно попасть, в точке P. Объект движется со скоростью V. В какую сторону нужно выстрелить, чтобы попасть в объект?

Входные данные

В первой строке записаны координаты объекта Px, Py, Pz. Во второй строке - его скорость Vx, Vy, Vz. В третьей - скорость пули |U|. Все числа во входном файле целые, по абсолютной величине не превосходящие 10000, |U|>|V|.

Выходные данные

Выведите Ux, Uy и Uz с двумя знаками после запятой - направление, в котором нужно стрелять. Помните, что Ux^2+ Uy^2 +Uz^2=|U|^2.

Пример

Ввод

7 3 0
-3 0 0
5

Вывод

4.00 3.00 0.00

Догнать

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

Черный король поцеловал белую королеву. Теперь белый король хочет догнать черного, чтобы отомстить. Короли находятся на стандартной шахматной доске и ходят по шахматным правилам. Первым ходит белый король. Сколько ходов необходимо сделать белому королю, чтобы оказаться на одной клетке с черным?

Входные данные

В первой строке записаны позиции белого и черного королей через пробел.

Выходные данные

Выведите ответ на задачу или -1, если белый король никогда не догонит черного.

Пример

Ввод

c3 a1

Вывод

Игровой автомат

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.

ввод: input.txt
вывод: output.txt

В казино имеется игровой автомат с M барабанами. На каждом барабане написано число от 0 до N. Бросив жетон можно увеличить число на одном из барабанов на 1 (N меняется на 0). Девочка Катя задумалась, а сколько нужно жетонов, чтобы выиграть главный приз? Для получения главного приза нужно на всех барабанах получить одно и то же число. Не подскажите ли вы Кате?

Входные данные

В первой строке записаны натуральные числа M и N (0<M, N<=15000). Во второй строке записано N чисел - текущее положение барабанов.

Выходные данные

Выведите ответ для девочки Кати.

Пример

Ввод

3 10
9 9 1

Вывод

Прямоугольное окно

ограничение времени на тест: 3 сек.
ограничение памяти на тест: 16384 KB.

ввод: input.txt
вывод: output.txt

Дан многоугольник в некоторой декартовой системе координат. Все стороны данного многоугольника параллельны осям координат. Каждые две смежные стороны многоугольника - перпендикулярны. Все координаты вершин - целые. Внутренняя часть многоугольника закрашена серым (но не его периметр). Какое количество серых несвязных областей можно наблюдать через данное прямоугольное окошко?
Стороны окна параллельны осям координат. На рисунке через окошко можно видеть две части.

Входные данные

В первой строке входного файла записаны числа x1, y1, x2, y2 (x1 < x2; y2 < y1) - координаты левого верхнего и правого нижнего углов соответственно. Далее во второй строке записано N (4 <= N <= 5000) - количество вершин многоугольника. В N строках записаны координаты многоугольника в порядке обхода против часовой стрелки. Все координаты лежат в отрезке [0, 10000].

Выходные данные

Выведите количество несвязных серых областей видимых через прямоугольное окно.

Пример

Ввод

0 5 8 1
24
0 0
4 0
4 2
5 2
5 0
7 0
7 3
3 3
3 2
2 2
2 4
1 4
1 5
2 5
2 6
3 6
3 5
4 5
4 6
5 6
5 4
7 4
7 7
0 7