Задача 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. Восстановление скобок

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

Условие

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

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

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

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

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

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

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

Задача C. Арифметическая прогрессия

Автор:Жюри ВКОШП 2010   Ограничение времени:2 сек
Входной файл:arithm.in   Ограничение памяти:256 Мб
Выходной файл:arithm.out  

Условие

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

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

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

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

Напомним что последовательность a1, a2, …, an называется арифметической прогрессией, если ai = ai1 + d для всех i от 2 до n и некоторого d. Число d называется разностью арифметической прогрессии.

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

В первой строке входного файла находится целое число n (1 ≤ n ≤ 100 000). В следующей строке находится 2 n целых чисел по модулю не превосходящих 109 — числа, написанные на карточках, перечисленные в произвольном порядке. Гарантируется, что можно выбрать n из них так, чтобы они образовывали арифметическую прогрессию.

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

В первой строке выходного файла выведите a1 и d — первый элемент и разность найденной арифметической прогрессии. Если d = 0, число a1 должно встречаться среди заданных чисел n раз.

Если существует несколько решений, выведите любое.

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

Входной файл (arithm.in) Выходной файл (arithm.out)
1
3
8 7 1 5 4 3
1 3

Задача D. Матрёшки

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

Условие

На столе стоят N матрёшек разного размера. Матрёшку меньшего размера можно поместить внутрь большей, ту, в свою очередь, внутрь ещё большей и так далее.

Сколькими способами можно поместить часть матрёшек внутрь других, чтобы осталось ровно K матрёшек?

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

Входной файл содержит целые числа N K.

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

Требуется вывести в выходной файл единственное целое число — искомое число способов.

Ограничения

1 ≤ K ≤ N ≤ 12.

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

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

Problem E. Doors and... more doors

Author:A. Klenin   Time limit:2 sec
Input file:input.txt   Memory limit:128 Mb
Output file:output.txt  

Statement

When wondering through the labyrinth, the goal is usually to find some kind of door. Well, not this time.

A labyrinth consists of N × N cells, each 1 × 1 meter in size. Cells are separated by doors. Each door opens in a specific direction (as shown on the picture):

  1. left outwards;
  2. left inwards;
  3. right outwards;
  4. right inwards.
So a cell can be represented by two numbers describing doors on its eastern and southern sides according to the list above. The doors are just slightly less then 1 meter in width. The traveler in the labyrinth is also slightly less then 1 meter in diameter, so he has following limitations:

Your program must find the shortest path for the traveler from north-western cell (1, 1) to south-eastern cell (N, N).

Input file format

Input file contains labyrinth size N followed by 2 × N2 numbers describing doors for each cell row by row. As there are no doors leading outside of labyrinth, values for eastern doors in the last column and southern doors in the last row are zero.

Output file format

Output file must contain the shortest path as a list of cell coordinates (column number, then row number), including both (1, 1) and (N, N) cells. If there are several solutions with the same length, output any one of them. If it is impossible to get to a destination cell, output a singe zero.

Constraints

1 ≤ N ≤ 1000

Sample tests

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

Задача F. Контрольная сумма

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

Условие

Напишите программу, которая копирует текст из входного файла и добавляет к нему фразу "Это сообщение содержит ровно K букв и ровно M цифр.", при этом K и M должны учитывать буквы и цифры в добавленной фразе. Буквами считаются строчные и прописные латинские буквы, а также все символы с ASCII-кодами от 128 до 255. Слова "буквы" и "цифры" во фразе должны иметь окончание, соответствующее числительному, например, "21 цифру", "4 цифры", "15 цифр". При необходимости в контрольной фразе можно не выводить одно или оба слова "ровно".

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

Входной файл содержит одну строку.

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

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

Ограничения

Длина строки не более 200 символов. Русские буквы должны быть в кодировке WINDOWS-1251.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
Сегодня contest.
Сегодня contest.
Это сообщение содержит ровно 49 букв и 3 цифры.

Problem G. 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

Задача H. Монстры

Автор:?   Ограничение времени:2 сек
Входной файл:monsters.in   Ограничение памяти:200 Мб
Выходной файл:monsters.out  

Условие

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

Рисунок 1. Монстры на столе для экспериментов

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

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

Первая строка входного файла содержит числа M и N - размеры лабораторного стола. Следующая строка содержит число K - количество монстров. Следующие K строк содержат описания монстров - два целых числа и один символ из множества {N, E, S, W} - начальные координаты и направление соответствующего монстра (соответствие направлений и координат приведено на рисунке 1). Символ отделен от чисел ровно одним пробелом.

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

В выходной файл выведите единственное число - количество клеток стола, на которых побывают монстры.

Ограничения

1 ≤ N, M ≤ 106, 1 ≤ K ≤ 103,

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

Входной файл (monsters.in) Выходной файл (monsters.out)
1
8 5
4
4 4 S
6 2 W
6 3 N
6 4 S
13

Задача I. Эллипс и окружность revisited

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

Условие

Эллипс — геометрическое место точек, сумма расстояний для которых от двух заданных постоянна и равна 2 a. Две заданных точки называются фокусами эллипса и в нашей задаче их координаты обозначаются как x1, y1, x2, y2. Число a называется большой полуосью эллипса.

Окружность — геометрическое место точек, расстояние для которых от заданной постоянно и равно R. Заданная точка называется центром окружности и в нашей задаче её координаты обозначаются как x, y. Число R называется радиусом окружности.

И для окружности, и для эллипса можно определить их внутреннюю часть — площадь, ограниченную окружностью или эллипсом соответственно.

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

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

Во входном файле находятся целые числа x, y, R, x1, y1, x2, y2, a в этом порядке.

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

Выведите единственное число - площадь пересечения с точностью до 103.

Ограничения

10 ≤ x, y, x1, y1, x2, y2 ≤ 10;

1 ≤ R ≤ 10;

|x2x1|2 + |y2y1|2/2 < a ≤ 20;

Фокусы эллипса не совпадают.

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

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

Problem J. Aerodynamics

Author:NEERC-2008 Jury   Time limit:2 sec
Input file:aerodynamics.in   Memory limit:64 Mb
Output file:aerodynamics.out  

Statement

Bill is working in a secret laboratory. He is developing missiles for national security projects. Bill is the head of the aerodynamics department.

One surprising fact of aerodynamics is called Whitcomb area rule. An object flying at high-subsonic speeds develops local supersonic airflows and the resulting shock waves create the effect called wave drag. Wave drag does not depend on the exact form of the object, but rather on its cross-sectional profile.

Consider a coordinate system with OZ axis pointing in the direction of object's motion. Denote the area of a section of the object by a plane z=z0 as S(z0). Cross-sectional profile of the object is a function S that maps z0 to S(z0). There is a perfect aerodynamic shape called Sears-Haack body. The closer cross-sectional profile of an object to the cross-sectional profile of Sears-Haack body, the less wave drag it introduces. That is an essence of Whitcomb area rule.

Bill's department makes a lot of computer simulations to study missile's aerodynamic properties before it is even built. To approximate missile's cross-sectional profile one takes samples of S(z0) for integer arguments z0 from zmin to zmax.

Your task is to find the area S(z0) for each integer z0 from zmin to zmax, inclusive, given the description of the missile. The description of the missile is given to you as a set of points. The missile is the minimal convex solid containing all the given points. It is guaranteed that there are four points that do not belong to the same plane.

Input file format

The first line of the input file contains three integer numbers: n, zmin and zmax. The following n lines contain three integer numbers each: x, y, and z coordinates of the given points. All coordinates do not exceed 100 by their absolute values. No two points coincide. There are four points that do not belong to the same plane.

Output file format

For each integer z0 from zmin to zmax, inclusive, output one floating point number: the area S(z0). The area must be precise to at least 5 digits after decimal point.

Constraints

4 ≤ n ≤ 100

0 ≤ zmin ≤ zmax ≤ 100

Sample tests

No. Input file (aerodynamics.in) Output file (aerodynamics.out)
1
9 0 5
0 0 5
-3 0 2
0 -1 2
3 0 2
0 1 2
2 2 0
2 -2 0
-2 -2 0
-2 2 0
16.00000
14.92000
10.08000
4.48000
1.12000
0.00000

Задача K. Ним - 1

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

Условие

Задана начальная позиция в игре Ним. Определите, кто победит при оптимальной игре обоих игроков.

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

Во входном файле содержится число N — количество Ним-куч. Далее следует N чисел ai — величина каждой кучи.

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

В выходной файл выведите число 1, если выиграет первый игрок, 2 — если выиграет второй. В случае, если позиция выигрышна для первого игрока, выведите количество вариантов оптимального первого хода.

Ограничения

1 ≤ N ≤ 1000, 1 ≤ ai ≤ 2311.

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

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

Задача L. Ним с делением

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

Условие

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

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

Во входном файле содержится число N — количество Ним-куч. Далее следует N чисел ai — величина каждой кучи.

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

В выходной файл выведите число 1, если выиграет первый игрок, 2 — если выиграет второй.

Ограничения

1 ≤ N ≤ 1000, 1 ≤ ai ≤ 109.

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

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

Задача M. Новое слово в рекламе

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:word.in   Ограничение памяти:256 Мб
Выходной файл:word.out  

Условие

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

Небольшая компания «Домострой» также решила выйти на этот рынок и стала предлагать место для рекламы на своих блоках заборов. Блок представляет собой параллелепипед размером 1 × 1 × L, на одной из сторон которого есть место для рекламы — пространство размера 1 × L, в которое можно вписать ровно L букв латинского алфавита.

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

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

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

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

Необходимо, чтобы рекламная надпись, требуемая заказчику, входила в получившуюся строку как подстрока TOEIIZENITKN.

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

Система оценивания

Решения, правильно работающие только для N ≤ 5, будут оцениваться из 50 баллов.

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

Первая строка входного файла входного файла содержит два натуральных числа N и L — число различных типов блоков на складе и длина каждого блока соответственно. Последующие N строк содержат по одной записи длиной L, состоящей из строчных латинских букв — надписи на блоках соответствующего типа. Надписи на блоках разных типов не совпадают.

Последняя строка входного файла содержит новую рекламную надпись s — строку, состоящую только из строчных латинских букв. Можно считать, что на складе находится неограниченное число блоков каждого типа.

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

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

Если ответов несколько, выведите любой из них. Если решения не существует, выведите в выходной файл число 1.

Ограничения

1 ≤ N, L ≤ 100, 1 ≤ |s| ≤ 200

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

Входной файл (word.in) Выходной файл (word.out)
1
3 4
tiet
oink
ezin
zenit
3
1 2 3
2
2 11
sillysample
happysample
sam
1
2
3
2 3
baa
aab
bb
2
2 2
4
2 3
aaa
bbb
cc
-1

0.183s 0.004s 47