|
(19-22 января 2007г.)
Задача A. Скобочки
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Строка, состоящая из символов «(» и «)», называется скобочной последовательностью. Скобочная последовательность называется правильной, если она может быть получена из некоторого корректного арифметического выражения удалением всех символов, кроме скобок. Например, правильная скобочная последовательность «(())()» может быть получена из выражения «(2-(3+4)*6)*(1+1)».
Глубиной правильной скобочной последовательности называется максимальная разность между количеством открывающихся и закрывающихся скобок в префиксе последовательности (префиксом строки S называется строка, которую можно получить из S удалением некоторого количества последних символов, например, префиксами строки «ABCAB» являются строки «», «A», «AB», «ABC», «ABCA» и «ABCAB»). Например, глубина последовательности «()()(())» равна двум, т.к. префикс «()()((» имеет 4 открывающиеся и 2 закрывающиеся скобки.
Требуется написать программу, определяющую по заданным значениям N и K количество правильных скобочных последовательностей с N открывающимися скобками, которые имеют глубину, равную K.
Входные данные
Входной файл INPUT.TXT содержит в одной строке целые числа N и K (1 ≤ K ≤ N ≤ 50), разделенные пробелом.
Выходные данные
Выходной файл OUTPUT.TXT должен содержать одно число — количество правильных скобочных последовательностей с n открывающимися скобками, которые имеют глубину k.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 2 | 3 |
| 2 | 37 23 | 203685956218528 |
Задача B. Склад
(Время: 1 сек. Память: 16 Мб Баллы: 100)
На роботизированном складе имеется n отсеков, в которые робот может размещать грузы. Отсек с номером i имеет вместимость ci. Груз с номером i имеет размер si, поступает на склад в момент времени ai и забирается со склада в момент времени di. Вместимость отсека и размер груза имеют одну и ту же размерность. Если в отсеке с вместимостью c находится несколько грузов с суммарным размером d, то свободное место в этом отсеке равно c – d.
Когда груз с номером i поступает на склад, робот сначала пытается найти отсек, в котором достаточно свободного места для размещения этого груза. Если отсеков, в которых достаточно свободного места, несколько, то робот помещает груз в тот из них, в котором свободного места меньше. Если и таких отсеков несколько, то робот выбирает отсек с минимальным номером.
Если отсеков с достаточным количеством свободного места нет, робот пытается переместить грузы, уже расположенные в отсеках. Для этого он пытается найти такой отсек и такой груз в нем, что перемещение его в другой отсек обеспечивает достаточное количество свободного места для размещения поступившего груза. Если таких вариантов перемещения грузов несколько, то выбирается тот вариант, в котором потребуется перемещение груза с минимальным размером. Если и таких вариантов несколько, то выбирается вариант перемещения, при котором в отсеке, из которого перемещается груз, свободное место после перемещения этого груза будет минимально, а при прочих равных условиях — тот вариант, при котором в отсеке, куда осуществляется перемещение, свободное место после этого перемещения будет также минимально. Если и после этого остается более одного варианта, то выбирается тот вариант, при котором номер перемещаемого груза минимален и номер отсека, в который он перемещается, – также минимален. Если варианта с перемещением одного груза найти не удалось, то груз не принимается на склад.
Требуется написать программу, которая по списку грузов, поступающих для размещения на складе, выводит последовательность действий, выполняемых роботом.
Входные данные
Первая строка входного файла содержит два целых числа: n — количество отсеков, и m — количество грузов (1 ≤ n ≤ 10, 1 ≤ m ≤100). Вторая строка содержит n целых чисел ci, определяющих вместимости отсеков (1 ≤ ci ≤ 109). Последующие m строк описывают грузы: каждый груз описывается тремя целыми числами: своим размером si, временем поступления на склад ai и временем, когда его забирают со склада di (1 ≤ si ≤ 109, 1 ≤ ai < di ≤ 1000, все времена во входном файле различны, грузы упорядочены по возрастанию времени поступления на склад). Все числа в строках разделены пробелом.
Выходные данные
Выведите последовательность действий робота в том порядке, в котором они выполняются. Следуйте формату выходного файла, приведенного в примере. Возможны следующие сообщения:
- put cargo X to cell Y - разместить груз с номером X в отсеке с номером Y;
- move cargo X from cell Y to cell Z - переместить груз с номером X из отсека с номером Y в отсек с номером Z;
- take cargo X from cell Y - взять груз с номером X из отсека с номером Y.
- cargo X cannot be stored - груз X невозможно переместить
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 5
3 2 10
1 1 6
3 2 8
9 3 5
2 4 9
12 7 10 |
put cargo 1 to cell 2
put cargo 2 to cell 1
put cargo 3 to cell 3
move cargo 1 from cell 2 to cell 3
put cargo 4 to cell 2
take cargo 3 from cell 3
take cargo 1 from cell 3
cargo 5 cannot be stored
take cargo 2 from cell 1
take cargo 4 from cell 2
|
Задача C. Треугольник
(Время: 1 сек. Память: 16 Мб Баллы: 100)
В декартовой системе координат на плоскости заданы координаты вершин треугольника и еще одной точки. Требуется написать программу, определяющую, принадлежит ли эта точка треугольнику.
Входные данные
В четырех строках входного файла INPUT.TXT находятся пары целых чисел - координаты точек. Числа в первых трех строках - это координаты вершин треугольника (x1,y1), (x2,y2), (х3,у3), в четвертой строке - координаты тестируемой точки (x4,у4). Все координаты не превышают 10000 по абсолютной величине.
Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести слово «In», если точка находится внутри треугольника и «Out» в противном случае.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 0 0
100 0
0 100
100 100
| Out |
| 2 | 0 0
100 0
0 100
10 10
| In |
| 3 | 0 0
100 0
0 100
50 50
| In |
| 4 | 0 0
100 0
0 100
0 0
| In |
Задача D. Радио
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Как известно, при распространении радиоволн возникает интерференция, поэтому если рядом расположены две радиопередающие станции, вещающие на одной и той же частоте, то качество радиопередач резко снижается.
Радиостанция «Радио Информатика» планирует транслировать свои программы в стране Флатландия. Министерство связи Флатландии выдало радиостанции лицензию на вещание на двух различных частотах.
Владельцы радиостанции имеют возможность транслировать свои радиопрограммы с использованием n радиовышек, расположенных в различных точках страны. Для осуществления трансляции на каждой радиовышке требуется установить специальный передатчик – трансмиттер. Каждый передатчик можно настроить на одну из двух частот, выделенных радиостанции. Кроме частоты вещания, передатчик характеризуется также своей мощностью. Чем мощнее передатчик, тем на большее расстояние он распространяет радиоволны. Для простоты, предположим, что передатчик мощности R распространяет радиоволны на расстояние, равное R километрам.
Все передатчики, установленные на вышках, должны, согласно инструкции министерства, иметь одну и ту же мощность. Чтобы программы радиостанции могли приниматься на как можно большей территории, мощность передатчиков должна быть как можно большей. С другой стороны, необходимо, чтобы прием передач был качественным на всей территории Флатландии. Прием передач считается качественным, если не существует такого участка ненулевой площади, на который радиоволны радиостанции «Радио Информатика» приходят на одной частоте одновременно с двух вышек.
Требуется написать программу, которая определяет, какую максимальную мощность можно было установить на всех передатчиках, позволяющую выбрать на каждом передатчике такую одну из двух частот передачи, чтобы прием был качественным на всей территории Флатландии.
Входные данные
Первая строка входного файла INPUT.TXT содержит число N – количество вышек (3 ≤ N ≤ 1200). Последующие N строк содержат по два целых числа — координаты вышек. Координаты заданы в километрах и не превышают 104 по модулю. Все точки, в которых расположены вышки, различны. Все числа в строках разделены пробелом.
Выходные данные
В первой строке выходного файла OUTPUT.TXT выводится вещественное число — искомая мощность передатчиков. Во второй строке выводятся N чисел, где i-е число должно быть равно 1, если соответствующий передатчик должен вещать на первой частоте, и 2, если на второй. Ответ должен быть выведен с точностью, не меньшей 10–8.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4
0 0
0 1
1 0
1 1 | 0.70710678118654752
1 2 2 1 |
Задача E. Преобразование последовательности
(Время: 1 сек. Память: 16 Мб Баллы: 100)
Задана последовательность, содержащая n целых чисел. Необходимо найти число, которое встречается в этой последовательности наибольшее количество раз, а если таких чисел несколько, то найти минимальное из них, и после этого переместить все такие числа в конец заданной последовательности. Порядок расположения остальных чисел должен остаться без изменения.
Например, последовательность 1, 2, 3, 2, 3, 1, 2 после преобразования должна превратиться в последовательность 1, 3, 3, 1, 2, 2, 2.
Требуется написать программу, которая решает данную задачу.
Входные данные
Первая строка входного файла INPUT.TXT содержит число n — количество чисел во входной последовательности (3 ≤ n ≤ 200000). Следующая строка содержит входную последовательность, состоящую из n целых чисел, не превышающих по модулю 109. Все числа в строке разделены пробелом.
Выходные данные
В выходной файл OUTPUT.TXT выводится последовательность чисел, которая получается в результате названного преобразования. Все числа в последовательности должны быть разделены пробелом.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 7
1 2 3 2 3 1 2 | 1 3 3 1 2 2 2 |
| |
