2020-08-05
178
ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 4096 KB.
ввод: input.txt
вывод: output.txt
Правильной скобочной последовательностью называется такая последовательность круглых и квадратных скобок, которая могла бы встречаться в каком-нибудь арифметическом выражении. Например, последовательности ()[] и ([]) являются правильными скобочными последовательностями, а последовательности (][) и)()(- нет. Считается, что круглые и квадратные скобки равноправны, но круглой открывающей скобке обязательно должна соответствовать круглая закрывающая, а квадратной - квадратная. Скобки считаются упорядоченными в таком порядке: `(', `)', `[', `]'. Например, `)' больше чем `(', но меньше чем `[', а максимальной из всех скобок считается `]'. Говорят, что одна скобочная последовательность лексикографически меньше другой, если существует такое число k, что первые k скобок в них совпадают, а k+1-ая скобка в первой меньше, чем во второй. Программист Вася выписал на бумажке все правильные скобочные последовательности длины 2n таким образом, что каждая написанная скобочная последовательность лексикографически меньше следующей за ней. Он очень обрадовался, что теперь может по лексикографическому номеру скобочной последовательности найти саму последовательность (последовательности, записанные на бумажке, нумеруются, начиная с 1). Однако бумажка потерялась... А повторять эту огромную работу Васе лень... Помогите бедному Васе написать программу, которая бы выдавала правильную скобочную последовательность по ее лексикографическому номеру!
|
|
|
Входные данные
Во входном файле задано число n (1 <= n <= 50) и произвольное натуральное число A - лексикографический номер искомой последовательности.
Выходные данные
В первой строке выходного файла должна содержаться искомая скобочная последовательность.
Пример
Ввод
Test #1
2 1
Test #2
2
3
Вывод
Test #1
(())
Test #2
()[]
День пограничника
ограничение времени на тест: 3 сек.
ограничение памяти на тест: 32768 KB.
ввод: input.txt
вывод: output.txt
N пограничников собираются отпраздновать с размахом свой профессиональный праздник. У каждого из них есть знакомые матросы, при этом если пограничник приходит на праздник, то он обязательно приводит с собой всех своих знакомых матросов.
После торжества пограничники и матросы собираются "сыграть в шахматы", однако пограничники плохо умеют играть, поэтому они хотят иметь наибольшее возможное численное преимущество перед матросами.
Ваша задача - определить, какие именно пограничники должны придти на праздник, чтобы это преимущество (разность между числом пограничников и матросов на празднике) было наибольшим.
|
|
|
Входные данные
Первая строка содержит числа N и M - количество пограничников и матросов соответственно (1 <= M,N <= 300). В последующих N строках описаны знакомые пограничников в следующем формате: i-я строка начинается с числа Di - числа знакомых у i-го пограничника, а затем следуют Di чисел - номера этих знакомых.
Выходные данные
В первой строке выходного файла должно располагаться число пограничников, которые должны придти на праздник, а во второй - их номера.
Пример
Ввод
Test #1
1 3
3 1 2 3
Test #2
3 2
1 1
1 1
2 1 2
Вывод
Test #1
0
Test #2
2
1 2
Военный лабиринт
ограничение времени на тест: 3 сек.
ограничение памяти на тест: 8192 KB.
ввод: input.txt
вывод: output.txt
Лабиринт представляет собой клетчатый прямоугольник MxN, в котором некоторые клетки пустые, среди этих пустых клеток K клеток имеют под собой бомбоубежище, а остальные представляют из себя монолитные бетонные блоки.
Военное руководство решило взорвать этот лабиринт "к чертовой матери"1. Для этого в лабиринте находятся K солдат, которые должны активировать взрывной механизм. После того, как механизм активирован, солдаты должны укрыться в бомбоубежищах. К сожалению, в каждом бомбоубежище может укрыться только один солдат.
Посчитайте минимальное время от момента активации взрывного механизма до момента взрыва, которое необходимо, чтобы все солдаты укрылись в бомбоубежищах. Солдат тратит 1 секунду на то, чтобы из клетки, где он находится перейти в соседнюю с ней по горизонтали или вертикали и еще 3 секунды на то, чтобы спуститься из клетки в бомбоубежище, которое под ней находится. Выходить из лабиринта солдатам запрещено.
Входные данные
Во входном файле записаны числа M и N (1<=M,N<=100), задающие размеры лабиринта, а затем N строк по M чисел в каждой, задающие лабиринт. 0 обозначает пустую клетку, 1 - монолитный бетонный блок, 2 - пустую клетку с бомбоубежищем под ней. Клеток с цифрой "2" будет ровно K штук (1_K_100). Затем идет K пар чисел, задающих начальные координаты солдат. Левый верхний угол лабиринта имеет координаты (1,1), левый нижний - (1,N), правый нижний - (M,N).
Выходные данные
В выходной файл выведите одно число T - минимальное число секунд, через которое можно взрывать бомбу. Затем для каждой секунды (с первой по T-ую), в отдельной строке записать передвижения, которые в эту секунду происходят. Действия задаются номером солдата, и его перемещением, которые записываются через пробел. Перемещение задается одним из символов N - вверх, S - вниз, E - направо, W - налево, D - спускается в убежище. Действия, происходящие в одно и то же время, отделяются друг от друга пробелом.
Если всем солдатам спрятаться не удастся, выведите 0.
Пример
Ввод
Test #1
10 5
0 0 1 2 1 0 0 0 0 0
0 0 1 2 1 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 2 2 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
4 1
5 4
4 1
6 3
Test #2
10 5
0 0 1 2 1 0 0 0 0 0
0 0 1 2 1 0 0 0 0 0
0 0 1 1 1 0 0 0 0 0
0 0 0 2 2 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
4 1
5 4
4 1
4 1
Вывод
Test #1
6
1 D 2 W 4 S
1 D 3 S 2 W 4 W
1 D 2 D 3 D 4 W
4 D
4 D 2 D 3 D
2 D 3 D 4 D
Test #2
0
Дороги в королевстве
ограничение времени на тест: 3 сек.
ограничение памяти на тест: 32768 KB.
ввод: input.txt
вывод: output.txt
В одном королевстве имеется N городов. Чтобы жители могли путешествовать по стране, города должны быть соединены дорогами так, чтобы каждый житель мог проехать из каждого города в каждый.
Однако по главному закону этого королевства каждый год дороги уничтожаются и перестраиваются по-новому. При этом конфигурация дорог каждый год должна быть новая, то есть не должна повторять конфигурацию, уже использованную ранее.
Легенда гласит, что если однажды в королевстве не удастся построить дороги новым способом, то королевство будет завоевано. Ваша задача - выяснить, сколько лет просуществует королевство для N = 200.
Входные данные
no input
Выходные данные
|
|
|
В выходном файле должно быть записано, сколько лет просуществует королевство.
Пример
Ввод
Test #1
3
Test #2
20
Вывод
Test #1
4
Test #2
1569215570739406346256547210377768575765884983264804405248
Рамочки
ограничение времени на тест: 3 сек.
ограничение памяти на тест: 8192 KB.
ввод: input.txt
вывод: output.txt
Alpha-версия системы "Windows 0.9" работала в текстовом режиме. Единственное, что она умела делать - рисовать на экране окна (она не умела убирать нарисованные окна, переносить окна, изменять их размер). При этом у окна рисовалась рамка, состоящая из одного и того же символа (который у каждого окна был свой), внутренность же окна оставалась такой, какой она была до прорисовки окна.
Обои в "Windows 0.9" были по тем временам необычайно красивыми - весь экран заполнялся символом "." (точка). Таким образом, в процессе работы системы экран мог выглядеть например так, как это показано в примере входного файла.
Напишите программу, которая бы по виду экрана восстанавливала, в каком порядке происходило рисование окон.
Замечания. Вы можете считать, что у каждого окна видно (то есть не было перекрыто рамками других окон) как минимум по одному символу на каждой из сторон окна (левой, верхней, правой, нижней). Угловой символ считается принадлежащим сразу обоим сторонам.
Для рамок окон используются латинские буквы и цифры. Разные окна обрамляются разными символами. Большие и маленькие буквы считаются различными.
Решение всегда существует.
Входные данные
В первой строке входного файла записаны два числа N и M, задающие соответственно ширину и высоту экрана (1<=N,M<=100). В последующих строках изображен экран. В конце строк могут быть пробельные символы (первые N символов строки - не пробелы).
Выходные данные
В выходной файл выведите строку, состоящую из символов, которыми нарисованы рамки окон в том порядке, в каком они рисовались на экране. Если решений несколько, выведите любое из них.
Пример
Ввод
10 6
.AAAAA....
.AbbbAa...
.AAAAAa...
..bbb.a...
...aaa11..
......11..
Вывод
abA1
Цветные перестановки
ограничение времени на тест: 3 сек.
ограничение памяти на тест: 32768 KB.
|
|
|
ввод: input.txt
вывод: output.txt
Даны две перестановки A=(a1, a2,..., aN) и B=(b1, b2,..., bN) целых чисел от 1 до N (перестановкой чисел от 1 до N называется последовательность длины N, в которой каждое из чисел от 1 до N встречается ровно один раз).
Каждое из чисел от 1 до N необходимо покрасить в один из трех цветов - красный, зеленый или синий. После этого разрешается в перестановке A менять местами пары разноцветных соседних элементов так, чтобы в конце получилась перестановка B.
Например, если A=(1, 2, 3), а B=(2, 3, 1), то можно покрасить 1 в красный цвет, а 2 и 3 - в синий, после чего преобразовать A в B так: (1, 2, 3) > (2, 1, 3) > (2, 3, 1).
Ваша задача: написать программу для нахождения искомой раскраски чисел от 1 до N.
Входные данные
В первой строке входного файла записано число N (1 <= N <= 100000). Во второй и третей строках указаны перестановки A и B соответственно. Числа в перестановках отделены пробелами.
Выходные данные
Если искомой раскраски не существует, то выведите в выходной файл слово NO. В противном случае выведите строку из N символов. i-й символ данной строки должен определять цвет числа i (1 <= i <= N), причем красный цвет представляется символом R, зеленый - G, а синий - B.
Пример
Ввод
Test #1
3
1 2 3
2 3 1
Test #2
4
1 2 3 4
4 3 2 1
Вывод
Test #1
RBB
Test #2
NO
Парковка
ограничение времени на тест: 3 сек.
ограничение памяти на тест: 32768 KB.
ввод: input.txt
вывод: output.txt
Администрация города Немногоярославца в связи с резким увеличением потока туристов решила организовать в центре города автомобильную стоянку. Стоянка имеет вид кольца с N парковочными местами. Парковочные места занумерованы от 1 до N по часовой стрелке. Автомобилист, подъезжая к стоянке, двигается вдоль нее по часовой стрелке, пока не найдет свободное парковочное место. После этого он паркует свой автомобиль на этом месте.
Вчера, после открытия, стоянку посетило M автомобилистов. Про каждого автомобилиста известно время его подъезда к стоянке, время, когда он покинул свою стоянку, а также парковочное место, около которого он подъехал к стоянке. Требуется определить для каждого автомобилиста номер парковочного места, которое он занял. Известно, что никакие два события не произошли одновременно, в частности никакие два автомобилиста не подъезжают к парковке одновременно, и пока некоторый автомобилист ищет место для парковки, ни один другой автомобилист не подъезжает к парковке и не покидает ее.
Входные данные
Первая строка входного файла содержит числа N - количество парковочных мест и M - количество автомобилистов (1 <= N <= 10^5, 1 <= M <= N). Следующие M строк содержат описания автомобилистов в следующем формате: t1 - время подъезда к стоянке, t2 - время, когда он покинул стоянку, и c - номер парковочного места, около которого он подъехал к стоянке (t1, t2 целые, 1 <= t1 < t2 <= 10^9; 1 <= c <= N).
Выходные данные
Выведите в выходной файл M чисел - для всех автомобилистов в порядке их перечисления во входном файле выведите номер занятого парковочного места.
Пример
Ввод
6 6
1 9 6
2 5 6
3 7 6
4 11 4
6 10 5
8 12 4
Вывод
6
1
2
4
5
1
