Прямоугольная рамка была разрезана на N кусков.
Каждый кусок может представлять собой либо отрезок прямой, либо "уголок" — два отрезка,
соединённых под прямым углом.
По данным длинам отрезков требуется восстановить исходную рамку или определить,
что это невозможно.
Куски можно поворачивать, но нельзя отражать. Требуется использовать все куски.
Формат входного файла
Входной файл содержит число кусков N, за которым следуют N пар целых чисел aibi,
описывающих длину двух отрезков "уголка" i-го куска.
Если кусок является отрезком, то ai = 0 либо bi = 0.
Формат выходного файла
Выходной файл должен содержать два положительных целых числа WH —
ширину и высоту рамки, при этом W ≥ H.
Если решения не существует, следует выдать число − 1.
Если решений несколько, следует выдать решение с максимальным значением W.
Клуб Юных Хакеров организовал на своем сайте форум.
Форум имеет следующую структуру: каждое сообщение либо начинает новую тему,
либо является ответом на какое-либо предыдущее сообщение и принадлежит той же теме.
После нескольких месяцев использования своего форума юных хакеров заинтересовал
вопрос — какая тема на их форуме наиболее популярна. Помогите им выяснить это.
Формат входного файла
Первая строка входного файла содержит целое число N — количество сообщений в форуме.
Следующие строки содержат описание сообщений в хронологическом порядке.
Описание сообщения, которое представляет собой начало новой темы, состоит из трех строк.
Первая строка содержит число 0. Вторая строка содержит название темы.
Длина названия не превышает 30 символов. Третья строка содержит текст сообщения.
Описание сообщения, которое является ответом на другое сообщение, состоит из двух строк.
Первая строка содержит целое число — номер сообщения, ответом на которое оно является.
Сообщения нумеруются, начиная с единицы. Ответ всегда появляется позже, чем сообщение,
ответом на которое он является. Вторая строка содержит текст сообщения.
Формат выходного файла
Выведите в выходной файл название темы, к которой относится наибольшее количество сообщений.
Если таких тем несколько, то выведите первую в хронологическом порядке.
Ограничения
1 ≤ N ≤ 1000,
Длина всех сообщений не превышает 100 символов.
Примеры тестов
№
Входной файл (forum.in)
Выходной файл (forum.out)
1
7
0
Олимпиада по информатике
Скоро третья командная олимпиада?
0
Новая компьютерная игра
Вышла новая крутая игра!
1
Она пройдет 24 ноября
1
В Санкт-Петербурге и Барнауле
2
Где найти?
4
Примет участие более 50 команд
6
Интересно, какие будут задачи
Московская городская олимпиада по информатике 2003/04 г.
Ограничение времени:
5 сек
Входной файл:
f.in
Ограничение памяти:
200 Мб
Выходной файл:
f.out
Условие
На клеточном поле введена система координат так,
что центр координат находится в точке пересечения линий сетки и оси направлены вдоль линий сетки.
На этом поле выложили связную фигуру, состоящую из спичек. Использовались спички двух типов:
Спички длины 1 выкладывались по сторонам клеток.
Спички длины sqrt(2) выкладывались по диагоналям клеток.
Ребенок хочет сжечь фигуру. При этом он может поджечь ее в одной точке,
имеющей целочисленные координаты (например, в точке A на рисунке поджигать фигуру нельзя, а в точках B и C — можно).
Известно, что огонь распространяется вдоль спички равномерно (но по каждой спичке — со своей скоростью).
Спичка может гореть в нескольких местах (например, когда она загорается с двух концов;
или когда в середине диагональной спички огонь перекидывается с одной спички на другую — огонь расползается
по вновь подожженной спичке в обе стороны).
Напишите программу, которая определит, в какой точке нужно поджечь фигуру, чтобы она сгорела за минимальное время.
Формат входного файла
Во входном файле записано сначала число N - количество спичек.
Затем идет N пятерок чисел вида X1, Y1,
X2, Y2, T, задающих координаты
концов спички и время ее сгорания при условии, что она будет подожжена с одного конца
(гарантируется, что каждая спичка имеет длину 1 или sqrt(2), все спички образуют связную фигуру,
и положение никаких двух спичек не совпадает).
Формат выходного файла
Выведите минимальное время сгорания фигуры.
Время должно быть выведено с точностью не менее 2-х знаков после десятичной точки.
Если решений несколько, выведите любое из них.
Ограничения
1 ≤ N ≤ 40
Все координаты — целые числа, по модулю не превышающие 200,
время сгорания — натуральное число, не превышающее 107.
Любимым напитком большинства учеников K-й средней школы является кефир.
Однако, в последнее время в результате активной рекламной кампании всё больше учеников переходят на
новый газированный напиток "UnhealthyCola". Этот факт беспокоит школьную администрацию.
В результате социологического опроса учащихся выяснилось, что у каждого школьника в классе есть
ближайшие друзья, с мнением которых он считается.
Если больше половины ближайших друзей школьника уже пьют UnhealthyCola,
то школьник поддаётся их дурному влиянию и, в свою очередь, влияет на оставшихся друзей.
К сожалению, никакое количество друзей не способно переубедить школьника перейти обратно с
UnhealthyCola на кефир.
На педагогическом совете было решено, что распространение UnhealthyCola можно было бы сдержать,
если бы больше школьников дружили между собой.
Требуется подружить двух учеников школы таким образом, чтобы максимизировать количество
школьников, которые останутся верны кефиру.
Формат входного файла
Входной файл содержит число школьников N, за которым идёт N чисел
ci, где ci=0, если i-й ученик пьёт кефир,
и ci=1, если он пьёт UnhealthyCola.
Далее число пар друзей M, за которым идут
M пар чисел ai bi, означающих, что школьники
ai и bi — друзья.
Формат выходного файла
В выходной файл должно быть выведено два числа — ученики, которых следует подружить.
Если решений несколько, вывести любое из них. Если никакая пара новых друзей не
улучшит результат, следует вывести число −1.
В некотором городе однажды выпал снег. Неожиданно выяснилось, что вся снегоуборочная техника
находится на ремонте, и для расчистки улиц было решено привлечь тяжёлые гусеничные бульдозеры.
Задача осложняется тем, что асфальтовое покрытие улиц может выдержать только один проход
такого бульдозера.
Город представляет из себя N площадей и M отрезков улиц между ними.
Бульдозер может начинать
расчистку с любой площади, и не должен ехать по уже расчищенным улицам (но может
проезжать уже расчищенные площади). Если бульдозер оказывается на площади,
все улицы которой уже расчищены, бульдозерист считает свой рабочий день законченным,
бросает бульдозер и уходит.
Требуется определить минимально необходимое число бульдозеров.
Формат входного файла
Входной файл содержит числа N и M за которыми идут
M пар чисел aibi — номера площадей,
соединенных i-й улицей (по улице, соединяющей площади ai и bi,
можно проехать
либо из ai и bi,
либо из bi в ai).
Две площади могут быть соединены больше чем одной улицей.
Формат выходного файла
В выходной файл должно быть выведено единственное число — наименьшее количество бульдозеров,
необходимых для расчистки всех дорог и площадей города по указанным выше правилам.
Имеется N кубиков, на гранях которых написаны буквы.
Требуется определить, можно ли из этих кубиков составить данное слово длиной K символов,
и если да, то вывести номера использованных кубиков.
При этом каждый кубик можно использовать только один раз.
Если решений несколько, выдать любое из них.
Формат входного файла
В первой строке входного файла содержится количество кубиков N.
Во второй строке — слово, в следующих N строках — по шесть символов без разделителей,
определяющих буквы на гранях кубиков. (Порядок букв не имеет значения).
Формат выходного файла
Выходной файл должен содержать последовательность из K различных целых чисел от 1 до N,
задающих номера кубиков для каждой буквы слова, начиная с первой.
Если решения нет, выходной файл должен содержать единственное число 0.
Московская городская олимпиада по информатике 2003/04 г.
Ограничение времени:
3 сек
Входной файл:
e.in
Ограничение памяти:
200 Мб
Выходной файл:
e.out
Условие
Для игры в "Поле чудес" используется круглый барабан, разделенный на сектора, и стрелка.
В каждом секторе записано некоторое число. В различных секторах может быть записано одно и то же число.
Однажды ведущий решил изменить правила игры.
Он сам стал вращать барабан и называть игроку (который барабана не видел) все числа подряд в том порядке,
в котором на них указывала стрелка в процессе вращения барабана.
Получилось так, что барабан сделал целое число оборотов, то есть последний сектор совпал с первым.
После этого ведущий задал участнику вопрос: какое наименьшее число секторов может быть на барабане?
Напишите программу, отвечающую на этот вопрос.
Формат входного файла
Во входном файле записано сначала число N — количество чисел, которое назвал ведущий.
Затем записано N чисел, на которые указывала стрелка в процессе вращения барабана.
Первое число всегда совпадает с последним (в конце стрелка указывает на тот же сектор, что и в начале).
Формат выходного файла
Выведите минимальное число секторов, которое может быть на барабане.
Ограничения
2 ≤ N ≤ 30000
Числа, записанные в секторах барабана, — натуральные, не превышающие 32000.
Недавно в главном офисе картографической службы Ландшафтии случился пожар.
Сгорел архив, хранящий таблицы с перепадами высот в различных регионах страны.
Для восстановления этой информации требуется заново
посчитать перепады высот по сохранившимся картам.
Карта региона представляет собой матрицу размером N x N клеток,
в каждой клетке которой содержится
средняя высота определённого района над уровнем моря.
Максимальным перепадом высот называется
максимальная величина, на которую отличаются средние высоты двух районов,
соседних на карте по горизонтали или по вертикали.
Требуется по карте региона определить максимальный перепад высот в нем.
Формат входного файла
Входной файл содержит число N,
за которым следуют N2 целых чисел — описание карты региона.
Формат выходного файла
Выходной файл должен содержать единственное целое число —
максимальный перепад высот в этом регионе.
Ограничения
1 ≤ N ≤ 100.
Все высоты — целые числа от 0 до 231−1
You are to write a program that receives an unweighted undirected graph and writes all its vertices in
order of increasing distance from given vertex S.
Distance between vertices A and B is the length of the shortest path from A to B.
If there are several vertices such that their distances to S are equal,
they may be printed in arbitrary order.
Input file format
Input file contains three integers N, M and S.
Vertices are numbered with integer numbers from 1 to N. M is the number of edges,
S is the starting vertice.
Each of next M lines contain pair of integers — numbers of vertices connected by an edge.
Output file format
Output file must contain sequence of vertex numbers sorted by increasing distance from S.
If some vertex is not reachable from S, output must contain a single number −1.
You are to write a program that receives a weighted directed graph and finds
distances from source vertex S to all other vertices. Distance from S to
some vertex W is the minimal length of path going from S to W.
Length of path is the sum of weights of its edges.
Vertices are numbered with integers from 1 to N.
Input file format
First line of input file contains three integers NM and S,
where M is the number of edges. Next M lines contain three
integers each —
starting vertex number, ending vertex number and weight of some edge respectively.
All weights are positive.
There is at most one edge connecting two vertices in every direction.
Output file format
Output file must contain N integers — distances from
source vertex to all vertices.
If some vertices are not reachable from S, corresponding numbers must be −1.
Constraints
1 ≤ N ≤ 1000.
All weights are less or equal than 1000.
You are to write a program that finds shortest distances between all pairs
of vertices in a directed weighted graph.
Graph consists of N vertices, numbered from 1 to N, and M edges.
Input file format
Input file contains two integers N and M, followed my M triplets of integers
ui vi wi — starting vertex, ending vertex and weight or the edge.
There is at most one edge connecting two vertices in every direction. There are no cycles of negative weight.
Output file format
Output file must contain a matrix of size NxN.
Element in the j-th column of i-th row mush be the shortest distance between
vertices i and j.
The distance from the vertex to itself is considered to be 0.
If some vertex is not reachable from some other,
there must be empty space in corresponding cell of matrix.
Constraints
0 ≤ N ≤ 100.
All weights are less than 1000 by absolute value.
Для изготовления качественной табуретки необходимы 4 ножки одинаковой длины.
На табуреткоизготовительную фабрику поступило N ножек,
имеющих слегка различающиеся длины L1,
L2, … LN.
Научно-исследовательский отдел фабрики обнаружил,
что выпуск табуреток можно увеличить, если укорачивать некоторые ножки.
При этом отпиленная часть выбрасывается.
Требуется определить минимальное количество распилов, необходимых для
для изготовления N / 4 качественных табуреток.
Формат входного файла
Входной файл содержит число N, за которым следуют N чисел
Li — длины ножек. Все числа целые.
Формат выходного файла
В выходной файл следует вывести единственное целое число — минимальное
количество распилов.
Ограничения
1 ≤ N ≤ 10000, N mod 4 = 0,
1 ≤ Li ≤ 100.
Примеры тестов
№
Входной файл (input.txt)
Выходной файл (output.txt)
1
8
18 16 17 17 16 17 17 19
2
Задача M. Умножение неотрицательных длинных чисел
≡
