Страница: 1 2 >> Отображать по:
#1047
Праздники
  
Темы: [Массивы]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

На планете в звездной системе Альфа Кентавра неделя состоит из A дней, а год - из B дней. Годы нумеруются последовательными натуральными числами: 1, 2, 3, ... Кроме того, годы с номерами C1, C2, ..., CN являются високосными и состоят из (B+1) дней. В году дни с номерами D1, D2, ..., DM являются праздничными. Если праздник попадает на (B+1)-й день года, то он отмечается только в високосные годы. Первый день первого года является первым днем недели.

Один из жителей планеты решил устроиться на новую работу. В соответствии с заключенным трудовым договором он будет числиться на данной работе в течение E дней, начиная с первого дня 1-го года. По договору он имеет право выбрать один день недели (с 1 по A), который будет для него выходным. Праздничные дни также считаются нерабочими. Житель хочет выбрать себе выходной день таким образом, чтобы за период действия договора у него было максимальное количество нерабочих дней.

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

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

В первой строке входного файла через пробел записаны числа A и B - количество дней в неделе и в невисокосном году соответственно (1 ≤ A ≤ 2500, 1 ≤ B ≤ 10000). Во второй строке записано число N - количество високосных лет, и в третьей - номера C1, C2, ..., CN високосных лет в возрастающем порядке (0 ≤ N ≤ 5000, 1 ≤ C1 < C2 < ... < CN ≤ 107). В следующей строке число M - количество праздничных дней в году, и на новой строке - D1, D2, ..., DM в возрастающем порядке (1 ≤ D1 < D2 < ... < DM ≤ B+1). В последней строке записано число E (1 ≤ E ≤ 109). Известно, что житель заключил контракт не более чем на 107 лет.

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

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

Примеры
Входные данные
7 13
1
2
2
1 14
29
Выходные данные
1 8
#1048
Опечатки
  
Темы: [Строки]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Два слова называются похожими, если можно удалить из каждого слова не более одной буквы так, чтобы слова стали одинаковыми, возможно пустыми. Например, слова "spot" и "sport" похожи, так как одно и то же слово "spot" можно получить из первого слова без удаления букв, а из второго - удалением буквы "r".

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

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

В первой строке входного файла через пробел записаны натуральные числа N ≥ 1 - общее количество слов в словаре и M ≥ 1 - количество слов в проверяемом тексте (N+M ≤ 20000) В последующих N строках записаны слова, входящие в словарь, по одному на строке. Все слова словаря различны. Далее следуют M строк, в которых записаны слова проверяемого текста, по одному слову в строке.

Слова состоят из строчных и прописных букв латинского алфавита (прописные и строчные буквы считаются различными). Любое слово состоит не менее чем из одной и не более чем из 12 букв.

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

Для каждого слова из текста выведите в выходной файл строку, содержащую это слово, далее через пробел количество слов из словаря, на которые оно похоже. Если в словаре имеется единственное похожее слово, то также выведите в этой строке это слово (через пробел).

Примеры
Входные данные
5 8
father
and
or
mother
a
Father
and
mather
go
o
for
e
walk
Выходные данные
Father 1 father
and 1 and
mather 2
go 1 or
o 2
for 1 or
e 1 a
walk 0
#1049
Горнолыжные соревнования
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

В первой строке входного файла задано число N - количество ворот на трассе (0 ≤ N ≤ 500), в следующих двух строках заданы Sx, Sy, Fx, Fy - координаты точек старта и финиша соответственно. В каждой из следующих N строк записаны четыре числа ai, bi, yi, ci - x-координаты левого и правого концов ворот, y-координата ворот и штраф за непрохождение данных ворот (ai < bi, Fy < yi < Sy, ci - целое число, 0 ≤ ci ≤ 10000). Все координаты - целые числа, не превосходящие по модулю 10000.

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

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

Система оценки

Потестовая.

Примеры
Входные данные
4
3 6
3 1
5 7 4 1
4 5 5 10
1 2 4 5
2 5 2 0
Выходные данные
7.8126
#1053
Pinball
  

Поле в Pinball представляет собой прямоугольник без стенок, состоящий из n x m квадратных клеток, (n клеток по вертикали, m клеток по горизонтали). Клетки по вертикали нумеруются сверху вниз, по горизонтали - слева направо. В каждой клетке можно установить одну отражающую пластинку в одном из двух положений: в положении 1 - от левого верхнего угла к правому нижнему или в положении 2 - от левого нижнего к правому верхнему. Летящий шарик при столкновении с пластинкой изменяет свою траекторию, при этом угол падения шарика всегда равен углу отражения и составляет 45° (см. рисунок).

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

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

Требуется написать программу, устанавливающую пластинку таким образом, чтобы шарик попадал из точки A в точку B и длина его пути была минимальна.

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

Первая строка входного файла содержит три числа: n, m (1 ≤ n, m ≤ 1000) и k, где k - общее количество пластинок, которые были исходно расставлены.

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

Третья строка содержит описание точки B в том же формате.

 

 

Номера сторон клеток

Возможные положения пластинок

Следующие k-1 строк описывают пластинки, оставшиеся на поле. В каждой строке записаны по три числа: первое - номер клетки по вертикали, второе - номер клетки по горизонтали, третье - положение пластинки в клетке (число 1 или 2).

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

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



Подзадача 1.

\(1 \leq n, m \leq 300\). Решение оценивается в \(50\) баллов.


Подзадача 2.

Дополнительные ограничения отсутствуют. Решение оценивается в \(50\) баллов.

#1054
Великолепный Гоша
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
 

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


 

 


 

          Схема

 

          Сеть Гоши

Рис. 1

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



 





 

 

 

 

 

а)


б)


в)

Рис. 2

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

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

В первой строке входного файла задано число N (4 ≤ N ≤ 1000) - количество домов на схеме. Во второй строке записано число M (2 ≤ M ≤ 20000) - количество кабелей в схеме. В следующих M строках расположены пары номеров домов, соединенных кабелями на схеме. Дома имеют номера от 1 до N. Затем в M строках указаны пары номеров домов, которые Гоша соединил кабелями.

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

Если перестроить сеть согласно схеме невозможно, или для перестройки сети требуется более 48000 операций, то выходной файл должен содержать только число '-1'. В противном случае выходной файл должен содержать описание последовательности операций, по одной операции в строке.

Каждая операция описывается начальным и конечным положением кабелей. Сначала четырьмя целыми числами V1, V2, V3, V4 записывается исходное положение кабелей, при этом один из кабелей соединяет дома с номерами V1, V2, а другой --- V3, V4. Затем в таком же формате описывается конечное положение.

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