Страница: 1 2 3 4 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Клавиатура сотового телефона выглядит так:


1 — пробел



2 — abc


3 — def


4 — ghi



5 — jkl


6 — mno


7 — pqrs



8 — tuv


9 — wxyz

Режим ввода T2005 устроен следующим образом. В телефоне есть словарь. Пользователь, чтобы ввести слово, последовательно нажимает клавиши, на которых написаны буквы этого слова. Например, чтобы ввести слово begin пользователь должен нажимать клавиши 23446. Но как только в словаре оказывается только одно слово с таким началом, это слово автоматически подставляется и, кроме того, после этого слова автоматически добавляется пробел. Например, пусть пользователь нажал клавиши 234, и оказалось, что слов, ввод которых начинается с нажатия именно этих клавиш, — ровно одно. Тогда автоматически подставится это слово и пробел после него, а все последующие нажатия клавиш уже будут относиться к вводу следующего слова.

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

Вам дан словарь и последовательность нажатий клавиш. Выведите текст, который был введен пользователем.

Примечание: в тексте используются только маленькие латинские буквы и символ пробел.

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

Сначала на вход программы поступает число N — количество слов в словаре (2N100000). В следующих N строках задается словарь. Каждое слово записано в отдельной строке. Слова расположены в алфавитном порядке. Никакое слово в словаре не встречается дважды. Длина каждого слова не превосходит 10 символов.

Далее вводится число M — количество нажатий клавиш (1M20000). Затем задается M разделяющихся пробелами чисел, описывающих нажатые клавиши. Последней нажатой клавишей всегда является клавиша "1".

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

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

Примечание:


2
a
z
2
5 1



Примечание: в этом примере выходной файл должен быть создан, но должен быть пустым, в частности, в него не нужно выводить пробел.

Оценка задачи

1 балл получат программы, правильно решающие задачу при ограничениях 2N100, 1M200.

Примеры
Входные данные
5
po
pod
sasha
shla
shosse
12
7 4 5 7 2 7 6 1 7 4 6 1
Выходные данные
shla sasha po shosse 
Входные данные
2
sem
vosem
6
7 8 9 7 8 1
Выходные данные
sem vosem 
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке входных данных содержатся два числа: D — максимальное расстояние удара и N — количество соперников на поле (D и N натуральные числа, D ≤ 1000, N ≤ 200). В следующих N строках задается по три числа – начальные координаты xi и yi и максимальная скорость vi соответствующего игрока (скорости и координаты — целые числа, –1000 ≤ xi ≤ 1000, 0 ≤ yi ≤ 1000, 0 < vi ≤ 1000), никакие два игрока не находятся изначально в одной точке. Игрок, бьющий мяч, находится в точке с координатами (0,0). Мяч выбивается в точку с неотрицательной ординатой (y   0).

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

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

Оценка задачи

1 балл получат программы, которые верно работают, когда в поле не более двух соперников.

Примеры
Входные данные
10 2
1 1 1
-1 1 1
Выходные данные
9.05539
0.00000 10.00000
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

Чтобы повлиять на исход выборов, бизнесмен собирается выделить деньги на агитационную работу среди жителей страны. Исследование рынка показало, что для того, чтобы один житель сменил свои политические воззрения, требуется потратить одну условную единицу. Кроме того, чтобы i-я партия в случае победы сформировала правительство, которое будет действовать в интересах бизнесмена, необходимо дать лидеру этой партии взятку в размере pi условных единиц. При этом некоторые партии оказались идеологически устойчивыми и не согласны на сотрудничество с бизнесменом ни за какие деньги.

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

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

В первой строке вводится целое число n – количество партий ( 1$ le$n$ le$105). Следующие n строк описывают партии. Каждая из этих строк содержит по два целых числа: vi – количество жителей, которые собираются проголосовать за эту партию перед началом агитационной компании, и pi – взятка, которую необходимо дать лидеру партии для того, чтобы сформированное ей в случае победы правительство действовало в интересах бизнесмена ( 1$ le$vi$ le$106, 1$ le$pi$ le$106 или pi = - 1). Если партия является идеологически устойчивой, то pi равно -1. Гарантируется, что хотя бы одно pi не равно -1.

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

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

Примеры
Входные данные
3
7 -1
2 8
1 2
Выходные данные
6
3
3 2 5 
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Даны эльфы, обладающие темпераментом Bi и олени со строптивостью Ai. С каждым оленем должны ехать два эльфа, причем Bk < Ai < Bj. Необходим выбрать наибольшее количество оленей.

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

Но волшебные олени – строптивые животные, поэтому не любые два эльфа могут ехать на любом олене. А именно, каждый олень характеризуется некоторой строптивостью ai, а каждый эльф – темпераментом bi. Два эльфа j и k могут ехать на i-м олене в том и только в том случае, если либо bj < ai < bk, либо bk < ai < bj.

Чтобы его появление было максимально зрелищным, Санта-Клаус хочет, чтобы в его упряжке было как можно больше оленей. Про каждого оленя Санта знает его строптивость, а про каждого эльфа – его темперамент.

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

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

В первой строке вводятся два целых числа m и n – количество оленей и эльфов, соответственно ( 1$ le$m, n$ le$100 000).

Вторая строка содержит m целых чисел ai – строптивость оленей ( 0$ le$ai$ le$109). В третьей строке записаны n целых чисел bi – темперамент эльфов ( 0$ le$bi$ le$109).

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

В первой строке  выведите одно число k – максимальное количество оленей, которое Санта-Клаус может включить в свою упряжку. В следующих k строках выведите по три целых числа: di, ei, 1, ei, 2 – для каждого оленя в упряжке выведите его номер и номера эльфов, которые на нем поедут. Если решений несколько, выведите любое.

И эльфы, и олени пронумерованы, начиная с единицы, в том порядке, в котором они заданы во входных данных.

Примеры
Входные данные
4 6
2 3 4 5
1 3 2 2 5 2
Выходные данные
2
1 1 2
2 4 5
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задан выпуклый многоугольник, необходимо определить минимальную величину Dmin*Dmax, где Dmin (Dmax) - минимальное и максимальное расстояние от начала координат по всевозможным лучам.

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

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

Степень точки A относительно многоугольника вычисляется по следующему правилу. Рассмотрим все лучи с вершиной в точке A, имеющие общие точки с многоугольником. Для каждого такого луча найдем минимальное и максимальное расстояние вдоль него от точки A до некоторой точки многоугольника: dmin и dmax. Степенью точки относительно данного многоугольника назовем минимум величины dmin×dmax по всем таким лучам.

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

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

Будем считать, что наблюдательный центр находится в точке (0, 0). На вход программы поступает описание полигона.

В первой строке вводится число n – количество вершин полигона ( 3$ le$n$ le$100). Следующие n строк содержат по два вещественных числа – координаты вершин полигона в порядке обхода их против часовой стрелки. Координаты не превышают 1000 по абсолютной величине. Гарантируется, что наблюдательный центр находится вне полигона, полигон представляет собой выпуклый невырожденный многоугольник, никакие три его последовательных вершины не лежат на одной прямой. Никакая сторона многоугольника не лежит на луче с центром в начале координат.

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

Выведите одно число – степень наблюдательного центра относительно полигона. Ответ должен отличаться от правильного не более чем на 10-4.

includegraphics{pics/polygon.1}
Примеры
Входные данные
3
1.0 2.0
3.0 2.0
0.5 3.25
Выходные данные
7.0000000000

Страница: 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест