Пример входных и выходных данных

Задача 0 Загулявшие гости

 

Входные данные: Input.txt
Выходные данные: Output.txt
Время на тест: 1 секунда

N гостей (1 ≤ N ≤ 30) засиделись на даче и боятся опоздать на последнюю электричку. У хозяина дачи, который остается на ночь, есть автомобиль, но в него могут сесть одновременно не более 4 человек, не считая шофера. Скорость движения автомобиля по лесной дороге - V км/час, скорость движения пешехода - U км/час, расстояние от дачи до железнодорожной станции - Z км, затратами времени на посадку-высадку пассажиров и разворот автомобиля можно пренебречь. За какое минимальное время все гости доберутся до станции?

Входные данные: текстовый файл Input.txt содержит единственную строку со значениями величин N, V, U и Z, разделенными одним или несколькими пробелами. Все числа, кроме N - положительные, не превосходящие 100.

Выходные данные помещаются в текстовый файл Output.txt и содержат единственную строку с искомым значением времени, рассчитанным с точностью до 0.001.

Пример входных данных 8 30 5 15

Пример выходных данных 1.056

 

 

Задача 1 Стильная одежда

Имя входного файла: style. in

Имя выходного файла: style. out

Ограничение по времени: 1 second

Ограничение по памяти: 64 megabytes

 

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

В наличии имеется N₁ кепок, N₂ маек, N₃ штанов и N₄ пар ботинок (1 ≤ Ni ≤ 100000). Про каждый элемент одежды известен его цвет (целое число от 1 до 100 000). Комплект одежды – это одна кепка, майка, штаны и одна пара ботинок. Каждый комплект характеризуется максимальной разницей между любыми двумя его элементами. Помогите Глебу выбрать максимально стильный комплект, то есть комплект с минимальной разницей цветов.

 

Формат входных данных

Для каждого типа одежды i (i = 1, 2, 3, 4) сначала вводится количество N_i элементов одежды этого типа далее в следующей строке – последовательность из N_i целых чисел, описывающих цвета элементов. Все четыре типа подаются на вход последовательно, начиная с кепок и заканчивая ботинками. Все вводимые числа целые, положительные и не превосходят 100 000.

 

Формат выходных данных

Выведите единственное целое число – максимальную разницу между любыми элементами максимально стильного комплекта.

 

Примеры

style.in	style.out	Пояснения
1 2 3 1 3 3 4 2 3		Комплект 3 3 3 3
3 6 7 10 1 8 3 9 1 1		Комплект: 5 6 9 20

Задача 2. Словарь

Имя входного файла: stdin

Имя выходного файла: stdout

Ограничение по времени: 2 seconds

Ограничение по памяти: 64 megabytes

 

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

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

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

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

Формат входных данных

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

Все слова состоят только из маленьких латинских букв, длина каждого слова не превосходит 15 символов. Общее количество слов на входе не превышает 100 000.

Формат выходных данных

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

Примеры

Std.in	Std.out
apple - malum, pomum, popula fruit - baca, bac ca, popum puni shment - malum, mult a	baca - fruit bac ca - fruit malum - apple, puni shment multa - punishment pomum - apple popula - apple popum - fruit

 

Комментарии

«Лексикографический порядок» означает, что слова идут по алфавиту. Иначе говоря, если у двух слов A и B несколько первых символов совпадают, то раньше идет то, у которого первая буква после общей части идет в алфавите раньше (например, слова solut ion и solve идут именно в таком порядке, так как первые 3 буквы в этих словах совпадают, а 4-я буква u в слове solut ion идет по алфавиту раньше буквы v слова solve). Если слово A является началом слова B, то раньше идет слово A (например, сначала идет слово school, а затем слово schoolboy).

 

Задача 3 Домино

Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На каждой из половинок нарисованы точки, количество которых соответствует числу от 0 до M включительно. На костяшках полного набора домино обозначены все возможные различные пары чисел, например, если M равно 3, то полный набор содержит 10 костяшек: (0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).

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

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

Задание

Напишите программу DOMINO, которая по информации о наборе домино должна ответить, какое минимальное количество цепочек нужно выложить.

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

В первой строке входного файла DOMINO.DAT содержится одно целое число M (0 ≤ M ≤ 100), которое соответствует максимально возможному количеству точек на половинке костяшки. Во второй строке записано одно целое число N, равное количеству костяшек, удаленных из полного набора. Каждая i-я из последующих N строк содержит по два числа Ai и Bi. Это количества точек на половинках i-й удалённой костяшки.

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

Единственная строка выходного файла DOMINO.SOL должна содержать одно целое число L - минимальное количество цепочек.

Пример входных и выходных данных

DOMINO.DAT	DOMINO.SOL
7 5 3 4