Задача 0A. Hello, world!

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

Требуется написать программу, которая печатает "Hello, world!" (без кавычек)


Задача 0B. Олины торты

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

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

Входные данные содержат числа M и N, каждое на новой строке.

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

Необходимо вывести единственное число — максимальное количество сахара.

Ограничения

1 < N, M < 10000

Примеры тестов

Стандартный вход Стандартный выход
1
10
2
5
2
6
4
1.5

Задача 0C. Заплыв

Автор:Н. Чистякова   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Оксана любит плавать и готовится к заплыву через Амурский залив. Для подготовки она каждый день приходит в бассейн и проводит там несколько часов, переплывая от одного края бассейна до другого. Длина бассейна, где занимается Оксана — N метров. Она успевает пересечь его за M секунд, и ещё K секунд тратит на разворот. Сколько метров Оксана успеет проплыть за L минут?

Формат входного файла

Первая строка входного файла содержит четыре натуральных числа: N M K L.

Формат выходного файла

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

Ограничения

1 ≤ N, M, K, L ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
25 76 2 45
865
2
50 50 1 60
3530

Задача 0D. Максимальный элемент массива

Автор:А. Усманов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:1  

Условие

Вам необходимо написать программу, которая находит наибольший элемент в массиве.

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

В первой строке записано одно целое число N — количество элементов в массиве.

Далее следует N целых чисел ai — элементы массива.

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

Выведите единственное целое число — наибольший элемент массива.

Ограничения

1 ≤ N ≤ 103

 − 106 ≤ ai ≤ 106

Описание подзадач и системы оценивания

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

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

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
ai
1451 ≤ ai ≤ 106
255 − 106 ≤ ai ≤ 1061

Подсказка

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

Примеры тестов

Стандартный вход Стандартный выход
1
3
1 3 2
3
2
5
8 5 6 10 3
10
3
1
1000000
1000000

Задача 0E. Подсчёт баллов за задачу

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

В одной из задач итоговой олимпиады летней школы по информатике имеется N тестов. i-ый тест оценивается в ai баллов. Итоговый балл за задачу — сумма баллов за каждый тест, ответ на который является правильным.

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

Формат входного файла

В первой строке файла содержится единственное число N.

Во второй строке файла содержатся N чисел — на i-ом месте находятся баллы за i-ый тест.

В третьей строке файла содержаться N символов '+' (ASCII 43) или '-' (ASCII 45). Если ответ на i-ый тест верный, то i-ый символ — '+', в противном случае — '-'

Формат выходного файла

Выходной файл должен содержать единственное число — количество баллов за задачу.

Ограничения

1 ≤ N ≤ 100

1 ≤ ai ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 2 3 5 10 
+-++-
9
2
6
1 1 3 5 10 25
+-+--+
29

Задача 0F. Стремление к нулю

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:100  

Условие

Дано число N и массив из S целых чисел Ai.

За одну операцию можно заменять число N на любое из чисел N + Ai, N − Ai, N × Ai, N / Ai.

Второй операнд может быть любым элементом массива A.

Деление выполняется нацело, с округлением вниз.

Необходимо рассчитать минимальное количество операций, необходимых, чтобы получить из числа N число 0.

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

Первая строка входных данных содержит целое число N.

Вторая — целое число S.

Третья — S целых чисел, массив A.

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

Выходные данные должны содержать одно целое число — минимальное количество операций.

Ограничения

0 ≤ N, Ai ≤ 2 * 109

1 ≤ S ≤ 100

Пояснения к примеру

100 / 25 = 4 ; 4 - 4 = 0

100 / 11 = 9 ; 9 / 11 = 0

В обоих случаях затрачено 2 операции, что в данном примере является минимально возможным.

Примеры тестов

Стандартный вход Стандартный выход
1
100
6
4 7 10 5 25 11
2

Задача 0G. Уравнение для 5 класса

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Уравнение для пятиклассников представляет собой строку длиной 5 символов. Второй символ строки является либо знаком '+' (плюс) либо '-' (минус), четвёртый символ — знак '=' (равно). Из первого, третьего и пятого символов ровно два являются цифрами из диапазона от 0 до 9, и один — буквой x, обозначающей неизвестное.

Требуется решить данное уравнение относительно x.

Формат входного файла

Входной файл содержит единственную строку — уравнение.

Формат выходного файла

В выходной файл следует вывести единственное целое число — значение x.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
x+5=7
2
2
3-x=9
-6

Задача 0H. Среднее арифметическое

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:512 Мб
Максимальный балл:1  

Условие

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

Формат входного файла

Входные данные содержат число n, за которым следует n положительных вещественных чисел.

Формат выходного файла

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

Ограничения

1 < n < 105

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 3 5
3

Задача 1A. Неоплаченные счета

Автор:ONTI   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:20  

Условие

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

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

Необходимо определить, сколько минут потребуется Василию Ивановичу на оплату всех счетов.

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

Входные данные содержат два целых числа N и M. Каждое число записано в новой строке.

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

Выведите одно число - минимальное время, за которое Василий Иванович оплатит все счета.

Ограничения

1 ≤ N, M ≤ 109

Примеры тестов

Стандартный вход Стандартный выход
1
10
5
11
2
10
3
16

Задача 1B. Стажeры

Автор:ONTI   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:20  

Условие

В связи с тем, что перед компанией по разработке ПО руководством было поставлено большое количество Очень Важных Задач, было принято решение набрать N новых стажeров из лучших вузов России. Про каждого стажeра известно, в каком вузе он учился.

Теперь, когда стажeры набраны, их необходимо посадить за компьютеры. В офисе есть ровно N свободных компьютеров, стоящих в одну линию вдоль стены.

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

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

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

В первой строке входных данных содержится целое положительное число N ≤ 1000. Далее в N строках содержатся названия вузов, в которых учились стажeры. Названия вузов - непустые строки, состоящие не более, чем из десяти заглавных латинских букв.

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

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

Если составить такую рассадку невозможно программа должна вывести строку «IMPOSSIBLE». Строки названия вузов необходимо выводить через пробел.

Если решений задачи несколько, выведите любой из них.

Примеры тестов

Стандартный вход Стандартный выход
1
4
HSE
HSE
MIPT
MSU
HSE MSU HSE MIPT 
2
4
HSE
HSE
MSU
HSE
IMPOSSIBLE

Задача 1C. Переезд

Автор:ONTI   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:20  

Условие

В связи с переездом в новый офис компании необходимо распределить опенспейсы между отделами. Известно, что в компании N отделов, в i-ом отделе Ai cотрудников. Теперь перед генеральным директором стоит задача: выделить каждому отделу собственный опенспейс. В новом офисе есть M ≤ N опенспейсов, в j-ом опенспейсе есть Bj рабочих мест. Для работы отдела необходимо, чтобы у каждого сотрудника было своe рабочее место, и ещe одно место нужно для начальника отдела. К сожалению, ремонт опенспейсов завершeн и изменить расстановку рабочих мест невозможно. Помогите генеральному директору распределить отделы компании по опенспейсам.

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

Для справки. Оpen space в переводе с английского - офис открытого типа, то есть помещение спланировано таким образом, что создается единое рабочее пространство для сотрудников.

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

На первой строке входного файла расположены числа N и M (1 ≤ N ≤ M ≤ 1000). На второй строке расположено N чисел - A1, . . . , AN (1 ≤ Ai ≤ 1000 для всех 1 ≤ i ≤ N). На третьей строке расположено M чисел B1, ..., BM (1 ≤ Bj ≤ 1000 для всех 1 ≤ j ≤ M).

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

Выведите на первой строке число P - количество отделов, которые удастся распределить по опенспейсам. На второй строке выведите распределение отделов по опенспейсам - N чисел, i-е число должно соответствовать номеру опенспейста, в котором разместится i-ый отдел (нумерация отделов и опенспейсов начинается с 1).

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

Примеры тестов

Стандартный вход Стандартный выход
1
3 3
1 2 3
2 3 4
3
1 2 3

Задача 1D. Печать документа

Автор:ONTI   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:20  

Условие

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

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

На вход программы сначала поступает число N , количество листов в итоговом отчeте (1 ≤ N ≤ 109), затем - число M (1 ≤ M ≤ 15) и далее M попарно различных чисел X1, X2, ..., XM (1 ≤ XI ≤ 109).

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

Сначала выведите K - количество пачек, которое придется передать со склада канцелярских товаров, если суммарно в этих пачках будет N листов бумаги. Далее выведите K чисел, задающих количество листов в каждой из пачек, которые требуется передать в отдел. Если решений несколько, выведите вариант, в котором придeтся передать минимальное количество пачек. Если таких вариантов несколько, выведите любой из них.

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

Примеры тестов

Стандартный вход Стандартный выход
1
108 7
45 35 12 4 3 1 931751396
5
45 35 12 12 4
2
7 2
1 2
-1
3
5 2
3 4
0

Задача 1E. Суперсекретная информация

Автор:ONTI   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:20  

Условие

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

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

Необходимо написать программу, которая выведет минимальное время, которое потребуется сотруднику для того, чтобы добраться из офиса a в офис b.

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

Сначала вводится число N - общее число офисов компании (1 ≤ N ≤ 100), затем в новой строке - номера офисов a и b (1 ≤ a, b ≤ N). Далее следует число рейсов корпоративных шаттлов R (0 ≤ R ≤ 105). После идут описания рейсов шаттлов: каждый рейс задается номером офиса отправления, временем отправления, номером офиса назначения и временем прибытия (все времена - целые от 0 до 10000). Если в момент t сотрудник приезжает в какой-то офис, то уехать из него он может в любой момент времени, начиная с t.

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

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

Примеры тестов

Стандартный вход Стандартный выход
1
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
5

Задача 4D. Извлечение ключа

Автор:ONTI   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:25  

Условие

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

Строка s2 является подпоследовательностью строки s1, если еe можно получить путeм удаления некоторых символов из s1, не меняя порядок оставшихся символов.

Например если s1 это abracadabra, то еe подпоследовательностями являются babr, arcada, aacaa и r. В то же время, такие строки как bob, bard и d_c не являются подпоследовательностями строки s1.

Ключ, который хочет передать Алиса, состоит из малых букв латиницы и обладает следующим свойством: любые два рядом стоящие в нeм символа находятся рядом и в алфавите. То есть следующий символ ключа по отношению к предыдущему является либо следующей, либо предыдущей буквой латиницы. Назовeм такие строки «правильными». Например, правильными являются строки cdef edef gh или abababab, а вот строки abba или cede не являются правильными.

Алиса очень постаралась и «зашила» ключ в строку так, что Боб серьезно задумался. Он знает, что нужно выбрать из полученной строки самую длинную правильную подпоследовательность, и если таких несколько, взять самую большую по лексикографическому (алфавитному) порядку. Но «знать» и «уметь делать» - очень разные вещи. Нужно помочь Бобу извлечь искомый ключ.

Пояснения к примеру

В присланной Алисой строке bdaedbceab содержатся следующие правильные подпоследовательности длины 5: babab, babcb и dedcb. Последняя, так как она лексикографически самая большая, и будет ответом.

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

В первой строке содержится число n - длина строки, которую прислала Алиса.

1 ≤ n ≤ 3·105.

Во второй строке приведена сама строка, которую прислала Алиса. Она состоит из малых букв латиницы.

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

В ответ вывести одну строку - «спрятанный» в исходной строке по указанным выше правилам ключ.

Примеры тестов

Стандартный вход Стандартный выход
1
10
bdaedbceab
dedcb

Задача 5B. Космические связи

Автор:ONTI   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Ученые решили изучить состояние межпланетных отношений. В первую очередь им нужно посчитать количество планетарных коалиций (групп планет). Они имеют информацию об n планетах во Вселенной. У каждой планеты есть координаты в двухмерном пространстве x и y. Планета состоит в некоторой коалиции, если она попадает в радиус r хотя бы одной планеты из этой коалиции. Они просят Вас написать программу, которая определит количество коалиций во Вселенной.

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

В первой строке записано два целых числа n (1 ≤ n ≤ 103) и r (1 ≤ r ≤ 106) — количество планет, которые известны ученым, и радиус взаимодействия планет.

В следующих n строках записано по два числа x и y ( − 106 ≤ x, y ≤ 106) — координаты планет.

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

Выведите одно целое число — количество коалиций, образованных всеми известными планетами.

Методика проверки Программа проверяется на 50 тестах. Прохождение каждого теста оценивается в 2 балла. Тест из примера к задаче при проверке не используется.

Примеры тестов

Стандартный вход Стандартный выход
1
5 3
1 1
3 4
6 3
5 1
4 4
2

Задача 6A. Сплав

Автор:ONTI   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:10  

Условие

Сплав состоит из n компонентов. Для каждого компонента i известна его процентная доля массы в сплаве ri . В лаборатории имеются все компоненты сплава, однако, можно использовать не более mi килограмм вещества i-того компонента. Напишите программу, которая определит максимальную возможную массу сплава, которую можно получить.

Пояснения к примеру

В приведенном примере масса сплава равна 27,5 кг. Взяв 50, 40 и 10% от этой массы, получим 13,75, 11 и 2,75 кг соответственно. Массы соответствующих компонентов не превосходит этих значений. Но при этом изготовить сплав большей массы не получится, поскольку не хватит вещества второго компонента.

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

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

На вход программы в первой строке подается одно натуральное число n — количество компонентов в сплаве. 1 ≤ n ≤ 30. Во второй строке через пробел записаны n целых неотрицательных чисел r1... rn — процентные доли компонентов в сплаве.

0 ≤ ri ≤ 100. Гарантируется, что сумма всех ri равна 100. Если ri = 0, то это означает, что компонент i в сплаве не используется. В третьей строке через пробел записаны n натуральных чисел m1... mn — масса вещества каждого компонента. 0 < mi < 1000.

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

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

Ответ будет считаться верным, если выведенное число отличается от правильного ответа не более чем на 0, 001.

Примеры тестов

Стандартный вход Стандартный выход
1
1
100
17
17.0

Задача 6B. Съемка заповедника

Автор:ONTI   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:15  

Условие

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

Каждый снимок имеет вид прямоугольника с шириной a и высотой b. Стороны прямоугольника должны быть параллельны осям координат. Поворачивать снимки нельзя. Снимки могут выходить за границу заповедника или накладываться друг на друга. При заказе каждого снимка можно указать его местоположение. Администрация заповедника хочет заказать как можно меньше снимков.

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

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

На вход программы в первой строке через пробел подаются три натуральных числа n, a, b — ширина криволинейной трапеции (количество столбиков из которых состоит трапеция), а также ширина снимка и высота снимка. 1 ≤ n ≤ 2000; 1 ≤ a ≤ 2000; 1 ≤ b ≤ 5000. Во второй строке через пробел записаны n целых неотрицательных чисел h1... hn — высоты столбиков. 0 ≤ hi ≤ 5000.

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

Требуется вывести одно число — минимальное количество снимков.

Методика проверки и пояснение к тесту Рисунки в условии задачи соответствуют тесту. Как видно из рисунков, минимальное количество снимков равно девяти.

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

Примеры тестов

Стандартный вход Стандартный выход
1
23 5 1
1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1
4

Задача 7A. Конвертер графов

Автор:М. Спорышев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:1  

Условие

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

Формат входного файла

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

Начиная со второй строки в файле содержится описание графа в одном из следующих форматов

Формат выходного файла

Выходной файл должен содержать описание графа в требуемом формате.

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ N2

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
edges mat
3 4
1 2
2 3
1 3
2 2
3
0 1 1
0 1 1
0 0 0
2
mat lists
4
1 0 1 1
0 0 0 0
1 1 0 0
0 1 1 0
4
3 1 3 4
0
2 1 2
2 2 3

Задача 7B. Интернет по ЛЭП

Автор:И. Олейников   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Один из интернет-провайдеров решил опробовать новую технологию — передачу данных по линиям электропередач. Для этого на подстанциях были установлены N ретрансляторов.

Рассмотрим i-й ретранслятор и провод от него к другому ретранслятору. Количество ретрансляторов, сигнал от которых к i-му проходит через рассматриваемый провод, назовем нагрузкой на данный провод для i-го ретранслятора. Максимум из нагрузок на все провода для i-го ретранслятора называется нагрузкой на данный ретранслятор. Известно, что по проводам электросети сигнал может пройти от одного ретранслятора к другому единственным образом.

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

Формат входного файла

Во входном файле содержится число N — количество ретрансляторов, за которыми следуют N − 1 пар чисел ui vi, означающих, что i-ый провод соединяет ретрансляторы ui и vi.

Формат выходного файла

В выходном файле должно содержаться N чисел a1 a2… aN, где ai — нагрузка на i-ый ретранслятор.

Ограничения

1 ≤ N ≤ 100000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 2
2 3
2 1 2
2
4
1 2
1 3
1 4
1 3 3 3

Задача 7C. Бег по коридору

Автор:И. Туфанов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  
Максимальный балл:1  

Условие

Школьник Петя собрал собственный цветной дисплей с разрешением 2 пикселя по вертикали и N пикселей по горизонтали. Каждый пиксель определяется координатами (a, b), где a — номер строки от 1 до 2, а b — номер столбца от 1 до N.

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

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

Изначально игрок находится в пикселе с координатами (1, 1). Цель игры — добраться до N-ого столбца, минимизировав конечный уровень усталости.

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

Формат входного файла

В первой строке входного файла содержится число N — горизонтальное разрешение дисплея. Далее следует описание игрового поля — пара строк длиной N каждая. Символ "." (точка) соответствует свободному пикселю, символ "#" (решетка) — занятому препятствием, символ "X" (прописная латинская X) — пикселю с эликсиром.

Гарантируется, что первый символ первой строки равен ".", кроме того, последний символ хотя бы одной из двух строк не равен "#".

Гарантируется, что можно добраться до N-ого столбца.

Формат выходного файла

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

Ограничения

2 ≤ N ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
..
.#
1
2
6
....X.
#XXX..
3

Problem 7D. SST for sparse graph

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  
Maximum points:1  

Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain &minus;1.

Constraints

1 &le; N, M &le; 100000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 10
2 3 10
3 1 10
20

Задача 7E. Бюрократия

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  
Максимальный балл:1  

Условие

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

Будем считать, что чиновники занумерованы целыми числами от 1 до N. Тот факт, что для посещения чиновника с некоторым номером, требуется справка от чиновника с другим номером, будем называть "условием".

Формат входного файла

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

Формат выходного файла

Выведите в выходной файл N целых чисел - одну из возможных последовательностей посещения чиновников. Если такой последовательности не существует (бывает же и такое!), выведите  − 1.

Ограничения

1 ≤ N ≤ 100000; 0 ≤ M ≤ 100000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4 3
1 2
1 3
3 4
1 3 2 4

0.750s 0.009s 57