Задача Schoolnet2015d. Лаборатория ИКТ ФМГ17 инициировала развитие оптоволоконных каналов связи между школами. На практике это выглядит так: при наличии средств между некоторыми двумя школами прокладывается оптоволоконный кабель. Работа долговременна, но к началу 3-го тура справились. Сетевые администраторы научились направлять пакеты между школами любым путем, а не только через прямую связь между ними. Но сразу возник вопрос повышения надежности работы сети, исключения "сетевых коллизий". Один из методов, который предложила Лаборатория - передача данных некоторыми линиями лишь в одном направлении. Чем больше таких однонаправленных линий - тем выше надежность сети в целом. Какое максимальное количество каналов можно перевести в режим однонаправленной передачи данных? Разумеется, сеть должна обеспечивать связь между любой парой школ в обоих направлениях.
Технічні умови. Программа Schoolnet2015d читает с клавиатуры два целых числа N - количество школ в городе и M - количество линий между ними (1≤N≤20000, 1≤M≤200000). Дальше читает M строк, в каждой из которых записаны два числа через пробел - номера школ, между которыми проложена линия. Каждые две школы соединяются не более чем одной линией.
Программа выводит на экран одно число K - максимальное количество линий, на которых можно ввести односторонний траффик.
Пример:
|
Ввод |
Вывод |
|
5 6 2 1 2 3 2 4 2 5 4 3 4 5 |
5
|
Задача Tri2015. Жители далекой планеты Трианглии решили построить новый алтарь в Храме Священной Тройки. Алтарь должен иметь форму равностороннего треугольника с длиной стороны n см, и составленным из камней в форме равносторонних треугольников со стороной 1 см. При этом n должен быть степенью числа три: n = 3k (рис. 1).
Рис. 1. Пример алтаря с длиной стороны n=3см
Каждый из маленьких треугольников-камней должен быть окрашенным в один из трех цветов: красный, зеленый или синий. Для того, чтобы определить цвет каждого камня будущего алтаря, сначала создают вспомогательный слой (фундамент) из n+1 камней, по одному на каждого жителя. Дальше алтарь строится послойно - сначала слой над фундаментом, потом второй слой, и так к самой вершине, придерживаясь двух правил:
• если цвета двух соседних треугольников внизу какого-то треугольника разные, то этот треугольник должен быть третьего цвета;
• если цвет двух соседних треугольников внизу совпадает, то этот же цвет должен иметь и текущий треугольник.
Герой Трианглии Тривася Трипупкин опоздал на момент закладки фундамента. Остальные n его друзей уже положили свои камни в фундамент, так что там осталось место лишь для крайнего правого треугольника (синий камень в фундаменте на рис. 1). Тривася хочет узнать, камень какого цвета он должен положить в фундамент, чтобы вершина алтаря была окрашена в зеленый цвет.
Технические условия. Программа Tri2015 читает с устройства стандартного ввода целое число 1 <= M <= 10 - количество фундаментов. Далее программа читает из той же строки через пробелы М последовательностей символов из множества {r,g,b}, отображающие цвета камней в почти готовом фундаменте слева направо (в каждой последовательности символы записаны без пропусков, количество символов в каждой последовательности n = 3k, где k ⩽ 10 , то есть n ⩽ 59049). Программа выводит на устройство стандартного выведения М подмножеств множества {r,g,b}. Каждое подмножество записано в виде одного или последовательности символов без пробелов. Последовательности разделены одним пробелом. Если Тривася не может получить зеленую вершину ни одним из способов, вывести единственный символ n.
Пример
Ввод 2 rgg ggrggrggr
Вывод: b g
Задача FindLCG Дано 4 целых неотрицательных числа x0, A, B, k. Они задают последовательность (линейный конгруэнтный генератор) вида
xn+1 = (A*xn + B) mod 2k . Необходимо по заданному целому неотрицательному числу x найти его самый первый номер в последовательности (минимальное целое неотрицательное n такое, что xn=x).
Технические условия. Программа читает с устройства стандартного ввода 5 целых неотрицательных чисел x0, A, B, k, x (1<=k<=64, 0<=x0,A,B,x<2k).
Программа выводит на экран (устройство стандартного вывода) единственное целое неотрицательное число - искомое n. Если решения не существует - программа выводит -1 .
Пример
Ввод 1 5 7 4 3
Вывод 2
Задача Tram. Руководство Муниципальной Транспортной Компании г. Винницы решило установить новую систему оплаты за проезд в трамваях. Маршрут представляет собой отрезок прямой, на которой последовательно размещено N остановок. Планируется разбить их на M непрерывных зон, следующих подряд, так, чтобы каждая зона содержала хотя бы одну остановку. Оплату проезда от остановки i до остановки k необходимо установить равной 1+|zi−zk|, где zi і zk − номера зон, которым принадлежат остановки i и k соответственно.
Известно количество пассажиров, отправляющихся за день с каждой остановки на каждую другую. Напишите программу, которая определяет, какую максимальную сумму денег за день можно получить по новой системе при оптимальном разбиении на зоны.
Технические условия. Программа Tram считывает со стандартного устройства ввода N строк. Первая строка содержит два целых числа N и M (1≤M≤N≤1000). Вторая - одно число, которое означает количество пассажиров, которые едут от остановки 1 до остановки 2. Третья - два числа, которые означают количество пассажиров, которые едут от остановки 1 к остановке 3 и от остановки 2 к остановке 3, соответственно. И так далее. В N- ой строке содержится N − 1 число, i- е из них определяет количество пассажиров от остановки i к остановке N. Количество пассажиров для каждой пары остановок дано с учетом движения в обе стороны. Все числа целые неотрицательные и не превышают 10000.
Программа должна вывести на стандартное устройство вывода единственное целое число - искомую максимальную дневную сумму денег.
Пример:
|
Ввод |
Вывод |
|
3 2 200 10 20 |
440 |
Задача Latest10. Подсчитать 5 последних знаков до десятичной запятой и 5 первых знаков после десятичной запятой
для числа 
,0 ⩽ n ⩽ 100000.
Технические условия. Программа Latest10 читает с устройства стандартного ввода число n. Программа выводит на устройство стандартного вывода 5 последних знаков до десятичной запятой, точку и 5 первых знаков после десятичной запятой без пробелов.
Примеры
Ввод: 5
Вывод: 00152.21023
Вводя: 7
Вывод: 01136.11266
Задания подготовили Г.Непомнящий, А.Островский, Ю.Пасихов, Д.Полищук