Алгоритмы

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

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

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

Источник: Уральская региональная командная олимпиада по программированию 2011

Чтобы помешать появлению СЭС в лагере, администрация ЛКШ перекопала единственную дорогу, соединяющую «Берендеевы поляны» с Судиславлем, теперь проехать по ней невозможно. Однако, трудности не остановили инспекцию, хотя для СЭС остается только одна возможность — дойти до лагеря пешком. Как известно, Судиславль находится в поле, а «Берендеевы поляны» — в лесу.

 

    - Судиславль находится в точке с координатами (0, 1).

    - «Берендеевы поляны» находятся в точке с координатами (1, 0).

    - Граница между лесом и полем — горизонтальная прямая y=a, где a — некоторое число (0 ≤ a ≤ 1).

    -  Скорость передвижения СЭС по полю составляет V_p, скорость передвижения по лесу — V_f. Вдоль границы можно двигаться как по лесу, так и по полю.

Администрация ЛКШ хочет узнать, сколько времени у нее осталось для подготовки к визиту СЭС. Она попросила вас выяснить, в какой точке инспекция СЭС должна войти в лес, чтобы дойти до «Берендеевых полян» как можно быстрее.

 

В первой строке входного файла содержатся два положительных целых числа V_p  и V_f  (1≤ V_p, V_f ≤ 10⁵) . Во второй строке содержится единственное вещественное число — координата по оси Oy  границы между лесом и полем a  (0 ≤ a ≤ 1) .

 

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

Ввод	Вывод
5 3 0.4	0.783310604
5 5 0.5	0.500000000

Велосипедисты, участвующие в шоссейной гонке, в некоторый момент времени, который называется начальным, оказались в точках, удалённых от места старта на x₁, x₂, ..., x_n метров (n – общее количество велосипедистов). Каждый велосипедист двигается со своей постоянной скоростью v₁, v₂, ..., vn метров в секунду. Все велосипедисты двигаются в одну и ту же сторону.

 

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

 

Требуется написать программу, которая по заданному количеству велосипедистов n, заданным начальным положениям велосипедистов x₁, x₂, ..., x_n и их скоростям v₁, v₂, ..., vn, вычислит момент времени t, в который расстояние l между лидирующим и замыкающим велосипедистом будет минимальным.

 

Первая строка входного файла содержит целое число n – количество велосипедистов.

 

В последующих n строках указаны по два целых числа: x_i – расстояние от старта до i-го велосипедиста в начальный момент времени (0 ≤ x_i ≤ 10⁷ ) и v_i – его скорость (0 ≤ v_i ≤ 10⁷ ).

 

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

 

Числа t и l должны иметь абсолютную или относительную погрешность не более 10^–6, что означает следующее. Пусть выведенное число равно x, а в правильном ответе оно равно y. Ответ будет считаться правильным, если значение выражения |x – y| /  max(1,  |y| )  не превышает 10^–6.

 

Подзадачи и система оценки

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

Ввод	Вывод
3 0 40 30 10 40 30	1 30
5 90 100 100 70 100 70 110 60 120 35	0.5 5.000000000000

 

 

Входной файл содержит 12 чисел: x₁, y₁, x₂, y₂, x₃, y₃, x₄, y₄, v_1x, v_1y, v_2x, v_2y. Координаты вершин первого отрезка: (x₁, y₁) и (x₂, y₂), координаты вершин второго отрезка: (x₃, y₃) и (x₄, y₄), скорость первого отрезка (v1x, v1y), скорость второго отрезка (v2x, v2y). Все числа целые и не превосходят по модулю 104. В начальный момент времени веточки не соприкасаются. Гарантируется, что веточки имеют ненулевую длину.

 

Выведите в выходной файл время до ближайшего момента, когда веточки соприкоснутся, с ошибкой не более 10⁻⁴. Если веточки не соприкоснутся никогда, выведите число -1.
 

Ввод	Вывод
0 0 -1 3 4 4 7 7 3 0 0 -1	1.6
0 0 -1 3 4 4 7 7 1 0 0 -3	-1

Дима недавно поступил на работу в НИИ Плоских Кривых. Как следует из названия этого научно- исследовательского института, он занимается различными исследованиями в области плоских кривых. Недавно Димин начальник Георгий столкнулся с весьма интересной кривой, которая, как выяснилось после некоторого исследования, известна под названием Архимедовой спирали. Архимедова спираль плоская кривая, изображающая траекторию точки M, которая равномерно движется вдоль луча OK с началом в O, в то время как сам луч OK равномерно вращается вокруг точки O (см. рисунок). Другими словами, расстояние до начала координат ρ = OM линейно зависит от угла поворота φ луча OK. При этом повороту луча OK на один и тот же угол соответствует одно и то же приращение расстояния ρ. 

 

Движение точки M можно задать с помощью ряда параметров:

 

• начального угла поворота α луча OK (измеряется в градусах против часовой стрелки относительно положительного направления оси OX);

 

• угловой скорости вращения ω луча OK (измеряется в градусах за единицу времени);

 

• начального расстояния R от точки M до начала координат (точки O);

 

• скорости движения V точки M по лучу OK.

 

Если, задав эти параметры, не ограничить время движения точки M, то получится бесконечная кривая, исследовать которую достаточно трудно. Поэтому Дима решил ограничиться исследованием некоторой части этой кривой той, которая получается при движении точки M от нулевого момента времени до момента времени T. Задача, которую решает Дима состоит в поиске прямоугольника минимальной площади со сторонами, параллельными осям координат, в который ее можно вписать.

 

Требуется написать программу, которая найдет искомый прямоугольник

 

Входной файл содержит четыре целых числа: ω (1 ≤ ω ≤ 100), V (1 ≤ V ≤ 100), R (0 ≤ R ≤ 100) и T (1 ≤ T ≤ 1000). В этой задаче считается, что начальный угол поворота α равен нулю.

 

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

 

Ответ будет считаться правильным, если значение каждой из координат будет отличаться от истинного значения не более чем на 10-5.

Экипаж Серенити межпланетного корабля класса Светлячок занимается доставкой грузов на различные планеты звездной системы. На корабле имеется секретный грузовой отсек, состоящий из N × M ячеек. Каждая ячейка грузового отсека имеет предельный объем, который она может вместить. Невозможно в ячейку вместить груз объемом больше, чем предельный объем ячейки. В одну ячейку можно поместить только ровно один груз. 

 

 Капитан Серенити Малькольм Рейнольдс продумывает размещение грузов по ячейкам. Помогите ему определить, какое максимальное количество грузов удастся доставить капитану.

 

Входные данные
В первой строке даны числа N и M (\(1 \leq N, M \leq 40\)). В каждой из последующих N строк содержится по M чисел, обозначающих предельный объем соответствующей ячейки. В (N+2)-ой строке находится число K (\(1 \leq K \leq 2000\)) – количество грузов. В (N+3)-ей строке содержатся K чисел, i-ое из которых – объем i-ого груза. Все объемы – натуральные числа, не превышающие 10⁹.

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

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

 

На первой строке дано число N (\(1 <= N <= 1000\)) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю 109.

 

Выведите одно число – количество обменов пузырьковой сортировки.
 

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 4 5	0
2	5 5 4 3 2 1	10

Требуется отсортировать массив по неубыванию методом "пузырька".

 

Входные данные
В первой строке вводится одно натуральное число N, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000).

 

Выходные данные
Вывести получившийся массив.

Палиндром - это строка, которая читается одинаково как справа налево, так и слева направо. 

 

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

 

В первой строке входных данных содержится число N (1 <= N <= 100000). Во второй строке задается последовательность из N больших латинских букв (буквы записаны без пробелов).

 

В единственной строке выходных данных выдайте искомый палиндром.
 

Ввод	Вывод
3 AAB	ABA
6 QAZQAZ	AQZZQA
6 ABCDEF	A

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

 

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

 

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

 

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100) – количество клавиш на клавиатуре. Вторая строка содержит n целых чисел – с1, с2, … , сn, где сi (1 ≤ сi ≤ 100000) – количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1 ≤ k ≤ 100000) – общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj (1 ≤ pj ≤ n) – последовательность нажатых клавиш.

 

В выходной файл необходимо вывести n строк, содержащих информацию об исправности клавиш. Если i-ая клавиша сломалась, то i-ая строка должна содержать слово “yes” (без кавычек), если же клавиша работоспособна – слово “no”.

 

 

Ввод	Вывод
5 1 50 3 4 3 16 1 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5	yes no no no yes

Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2009, 2 день, Задача A

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

 

После нескольких месяцев использования своего форума юных хакеров заинтересовал вопрос - какая тема на их форуме наиболее популярна. Помогите им выяснить это.

 

В первой строке вводится целое число N - количество сообщений в форуме (1 <= N <= 1000). Следующие строки содержат описание сообщений в хронологическом порядке. 

 

Описание сообщения, которое представляет собой начало новой темы, состоит из трех строк. Первая строка содержит число 0. Вторая строка содержит название темы. Длина названия не превышает 30 символов. Третья строка содержит текст сообщения. 

 

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

 

Длина каждого из сообщений не превышает 100 символов.

 

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

Ввод	Вывод
2 0 topic 1 body of message 1 0 topic 2 body of message 2	topic 1

 

Дано N целых чисел, которые требуется отсортировать в порядке неубывания. В связи с нормами СЭС среди чисел не будет двух, разница между которыми превышает 10⁷.

 

Первая строка входного файла содержит целое число N. (1 <= N <= 100000), вторая строка – N целых чисел, не превышающих по модулю 2*10⁹. Никакие два не различаются более, чем на 10⁷.

 

Выведите данные числа в порядке неубывания.

 

Ввод	Вывод
1 863961129	863961129
5 1866455200 1866455199 1866455198 1866455197 1866455196	1866455196 1866455197 1866455198 1866455199 1866455200

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

 

Даны два слова на отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают 255.

 

Требуется вывести "YES"  – если введенные слова являются анаграммами друг друга, "NO"  – если нет.

Имеется стол длины L. На столе разложено N носков так, что никакой носок не вылезает за границы стола. Далее имеется умный мальчик Васёк, который хочет (сугубо в корыстных целях) замерить толщину покрытия стола носками в M точках.

 

Во входном файле даны сначала L, N, M (1 ≤ L ≤ 10000, 1 ≤ N ≤ 10000, 1 ≤ M ≤ 100000). Далее идут N пар чисел l ≤ r от 1 до L – левые и правые концы носков. Затем идут M чисел от 1 до L интересующие Васька точки.

 

Выведите M чисел – толщину носкового покрытия в каждой точке.

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

 

На вход программе сначала подается значение n <= 100000 – количество элементов массива. В следующей строке расположены сами элементы – целые числа, по модулю не превосходящие 10000.

 

Выведите на экран отсортированный по неубыванию массив.
 

Примеры

№	Входные данные	Выходные данные
1	5 1 3 4 2 5	1 2 3 4 5

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

 

В первой строке входного потока записано через пробел два целых числа N и М (1 ≤ N, М ≤ 300 000) — количество элементов первого и второго наборов, соответственно. В следующих двух строках записано сначала N чисел первого набора, а затем M чисел второго набора. Числа разделены пробелами. Каждое из этих чисел попадает в промежуток от 0 до 10⁵.

 

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

Входные данные	Выходные данные
11 6 2 4 6 8 10 12 10 8 6 4 2 3 6 9 12 15 18	6 12

Дан связный ациклический ориентированный граф. Каждая вершина данного графа кроме листьев имеет по 2 сына.

Найдите количество способов топологически отсортировать, зная только количество вершин.

 

Входные данные
Входная строка содержит одно натуральное число n - кол-во вершин (n <= 15).

Выходные данные  
Выведите ответ на задачу.

В августе Владлена Александровна решила составить расписание для 9 «И» класса. Она считает, что уроков в один день должно быть N (2<=N<=8). От учителей она получила M (1<=N) запросов. Так как Владлена Александровна учитель географии, то с компьютером опыт работы у нее не такой как у вас, она просит вас о помощи, решите эту «невыполнимую» задачу, соблюдая запросы учителей.

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

 

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

 

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

 

Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны. 

 

В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений. 
Примеры

№	Входные данные	Выходные данные
1	4 5  1 2  2 3  3 4  1 4  4 1	No