Информатика

Алекс настраивает связь между исследовательскими станциями. Есть n станций и m возможных двусторонних каналов. Канал между станциями u и v начинает работать, если общая настройка мощности P не меньше указанного для него порога w.

Сообщение нужно передать со станции s на станцию t, использовав не более k каналов подряд. Использование одного канала считается одним переходом. Промежуточные станции могут пересылать сообщение.

Найдите минимальную целую мощность P ≥ 0, при которой это возможно. Если подходящего маршрута нет даже при работающих всех каналах, сообщите об этом.

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

Первая строка содержит пять целых чисел n, m, k, s, t (2 ≤ n ≤ 50 000, 0 ≤ m ≤ 100 000, 1 ≤ k ≤ n − 1, 1 ≤ s, t ≤ n, s ≠ t).

Следующие m строк содержат u, v, w (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ w ≤ 10⁹). Между одной парой станций не более одного канала.

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

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

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

Пример 1. При мощности 7 подходит маршрут 1 → 3 → 5. При мощности 6 доступен маршрут 1 → 3 → 4 → 5, но он слишком длинный.

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

Алекс тестирует навигацию в музее. План музея — прямоугольная таблица из n строк и m столбцов. Клетка # занята стеной, клетка . свободна. В клетке S находится Алекс, а в клетке T — пульт управления.

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

Найдите минимальное количество шагов от S до T и число различных маршрутов такой длины. Маршруты различны, если различаются последовательности посещённых клеток. Количество маршрутов выведите по модулю 1 000 000 007.

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

Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 500, 2 ≤ nm ≤ 200 000). Далее идут n строк по m символов ., #, S, T. Символы S и T встречаются ровно по одному разу и находятся в разных клетках.

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

Выведите два целых числа: длину кратчайшего маршрута и количество таких маршрутов по модулю 1 000 000 007. Если пульт недостижим, выведите -1 0.

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

Пример 1. Можно обойти стены сверху и справа либо слева и снизу. Оба маршрута содержат пять шагов.

Пример 2. Стена полностью перекрывает путь.

Алекс распределяет n наблюдателей по двум сменам: утренней и вечерней. Каждый человек должен попасть ровно в одну смену; пустая смена допускается.

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

Посчитайте количество допустимых распределений по модулю 1 000 000 007. Смены различаются: поменять у всех людей утро на вечер означает другое распределение. Если выполнить все ограничения невозможно, выведите 0.

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

Первая строка содержит целые числа n и m (1 ≤ n ≤ 200 000, 0 ≤ m ≤ 200 000). Следующие m строк содержат пары u, v (1 ≤ u, v ≤ n, u ≠ v). Каждая неупорядоченная пара встречается не более одного раза.

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

Выведите количество допустимых распределений по модулю 1 000 000 007.

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

Пример 1. У цепочки 1–2–3 два варианта смен, у наблюдателя 4 ещё два независимых варианта.

Пример 2. Трёх наблюдателей, попарно обязанных работать в разных сменах, в две смены распределить нельзя.

Алекс руководит запуском научного центра. Нужно выполнить n работ. Работа i занимает dᵢ минут и после начала выполняется без остановок.

Для некоторых пар работ указано требование: работа u должна закончиться прежде, чем начнётся работа v. Если у работы несколько предшественников, должны завершиться все. Приступить к работе можно ровно в момент завершения последнего предшественника.

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

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

Первая строка содержит целые числа n и m (1 ≤ n ≤ 100 000, 0 ≤ m ≤ 200 000). Вторая строка содержит n целых длительностей dᵢ (1 ≤ dᵢ ≤ 10⁹). Следующие m строк содержат u, v: работа u должна завершиться перед началом v. Номера различны и лежат от 1 до n. Одинаковых упорядоченных пар нет; циклы могут встречаться.

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

Выведите минимальный момент завершения всех работ или −1.

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

Пример 1. Работы 1 и 2 начинаются одновременно. Работа 3 заканчивается в момент 9, работы 4 и 5 — в моменты 11 и 15, работа 6 — в момент 16.

Пример 2. Каждая работа в цикле ждёт завершения другой.

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

Новый кабель можно проложить между любой парой различных станций u и v. Это стоит cᵤ + cᵥ монет. Если к станции подводят несколько новых кабелей, её стоимость оплачивается за каждый из них. Работающие кабели бесплатны и сохраняются.

Найдите минимальную общую стоимость новых кабелей, после добавления которых сообщение со станции 1 сможет дойти до любой станции.

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

Первая строка содержит целые числа n и m (1 ≤ n ≤ 200 000, 0 ≤ m ≤ 200 000). Вторая строка содержит n целых чисел cᵢ (1 ≤ cᵢ ≤ 10⁹).

Следующие m строк содержат номера концов работающего кабеля u и v (1 ≤ u, v ≤ n, u ≠ v). Между одной парой станций не более одного работающего кабеля.

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

Выведите минимальную общую стоимость. Если сеть уже связна, выведите 0.

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

Пример 1. Минимальные стоимости в трёх компонентах равны 2, 4 и 9. Добавим кабели 2–5 и 2–6: (2 + 4) + (2 + 9) = 17.

Пример 2. Станции уже связаны.

Алекс должен перевезти n ящиков с экспонатами. На складе ящики стоят в очереди, массы ящиков равны a₁, …, aₙ.

За один рейс Алекс забирает несколько первых оставшихся ящиков. Менять порядок и пропускать ящики нельзя. Каждый ящик перевозится целиком, ровно один раз. Масса груза в одном рейсе не должна превышать грузоподъёмность машины C.

Алекс может сделать не более k рейсов. Найдите минимальную целую грузоподъёмность C, которой хватит, чтобы перевезти все ящики.

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

Первая строка содержит целые числа n и k (1 ≤ k ≤ n ≤ 200 000). Вторая строка содержит n целых чисел aᵢ (1 ≤ aᵢ ≤ 10⁹).

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

Выведите минимальную грузоподъёмность.

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

Пример 1. Подходят рейсы [4, 2], [7], [3, 5]. При грузоподъёмности 7 понадобятся четыре рейса.

Пример 2. Единственный рейс должен вместить все ящики.

Выберите ОДНО из предложенных ниже заданий: 13.1 или 13.2.

13.1

Используя информацию и иллюстративный материал, содержащийся в каталоге DEMO-13, создайте презентацию из трёх слайдов на тему «Леопард». В презентации должны содержаться краткие иллюстрированные сведения о внешнем виде, местах обитания, образе жизни и рационе леопардов. Все слайды должны быть выполнены в едином стиле, каждый слайд должен быть озаглавлен.

Презентацию сохраните в файле, имя которого Вам сообщат организаторы экзамена. Файл ответа необходимо сохранить в формате *.odp.

Требования к оформлению работы

1. Ровно три слайда без анимации. Параметры страницы (слайда): экран (16:9), ориентация альбомная.

2. Содержание, структура, форматирование шрифта и размещение изображений на слайдах:

• первый слайд – титульный слайд с названием презентации, в подзаголовке титульного слайда в качестве информации об авторе презентации указывается идентификационный номер участника экзамена;

• второй слайд – основная информация в соответствии с заданием, размещённая по образцу на рисунке макета слайда 2:

· заголовок слайда;
· два изображения;
· два блока текста;

• третий слайд – дополнительная информация по теме презентации, размещённая по образцу на рисунке макета слайда 3:

· заголовок слайда;
· три изображения;
· три блока текста.

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

	Макет 1-го слайда Тема презентации
	Макет 2-го слайда Основная информация по теме презентации
	Макет 3-го слайда Дополнительная информация по теме презентации

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

Размер шрифта для названия презентации на титульном слайде – 40 пунктов, для подзаголовка на титульном слайде и заголовков слайдов – 24 пункта, для подзаголовков на втором и третьем слайдах и для основного текста – 20 пунктов.

Текст не должен перекрывать основные изображения и сливаться с фоном.

13.2

Создайте в текстовом редакторе документ и напишите в нём следующий текст, точно воспроизведя всё оформление текста, имеющееся в образце.

Данный текст должен быть набран шрифтом размером 14 пунктов обычного начертания. Отступ первой строки абзацев основного текста – 1 см. Расстояние между строками текста не менее одинарного, но не более полуторного междустрочного интервала. Основной текст выровнен по ширине; заголовок текста, текст в ячейках первой и седьмой строк таблицы, первого столбца таблицы – по центру; в ячейках второго столбца – выравнивание по левому краю. Во всех ячейках таблицы применено вертикальное выравнивание по центру. В основном тексте и таблице есть слова, выделенные полужирным шрифтом, курсивом или подчёркиванием. Таблица выровнена на странице по центру горизонтали. Ширина таблицы меньше ширины основного текста.

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

Интервал (расстояние) между заголовком текста и текстом, между абзацами текста, между текстом и таблицей не менее 12 пунктов (4 мм), но не более 24 пунктов (8,5 мм). Для установки интервала не допускается использование «пустого абзаца».

Текст сохраните в файле, имя которого Вам сообщат организаторы. Файл ответа необходимо сохранить в формате *.odt.

МОСКОВСКО-ПЕТРОГРАДСКАЯ ЛИНИЯ

Вторая линия Петербургского метрополитена, также известная как Московско-Петроградская (официальное название до 1993 г.) или синяя линия, соединяет через центр города южные и северные районы Санкт-Петербурга – от Московского района до северной части Выборгского.

Единственная в Петербургском метрополитене линия, обе конечные станции которой – наземные крытые.

Файл knn.txt содержит 1500 строк: координата метка (координата — вещественная, метка: 1 или 0). Первые 1000 строк — обучающая выборка, последние 500 — тестовая.

Тестовая точка классифицируется методом K ближайших соседей: берутся \( K \) обучающих точек, ближайших к ней по расстоянию \( |x_1 - x_2| \), и метка выбирается голосованием большинства. При равенстве голосов присваивается метка 0.

Переберите нечётные значения \( K \) от 1 до 21. Для каждого вычислите точность на тестовой выборке. Найдите \( K \) с максимальной точностью (при равенстве — наименьшее).

В ответе запишите два числа через пробел: оптимальное \( K \) и достигнутую точность в процентах (округлённую до целого).

Примечание

Голосование при нечётном \( K \) не даёт равенства, но правило «при равенстве — 0» оставлено на случай совпадающих расстояний.

Прибор считает измерение «нормальным», если его значение попадает в некоторый интервал. Файл measure.txt содержит 2400 строк: значение метка (значение — вещественное от 0 до 100, метка: 1 — норма, 0 — отклонение).

Правило-интервал: метка 1, если \( L \le значение \le H \).

Переберите обе границы: \( L \) от 0 до 100 с шагом 5 и \( H \) от \( L + 5 \) до 100 с шагом 5. Найдите пару границ с максимальным числом верных классификаций. При равенстве выберите наименьшее \( L \), затем наименьшее \( H \).

В ответе запишите три целых числа через пробел: \( L \), \( H \) и число верных классификаций.

Файл signal.txt содержит 3000 строк: уровень_сигнала метка (уровень — вещественный, метка: 1 или 0). Первые 2000 строк — обучающая выборка, последние 1000 — тестовая.

Правило: метка 1, если уровень не меньше порога \( K \).

Подберите порог \( K \) с максимальной точностью на обучающей выборке, перебирая значения от 0 до 100 с шагом 0.1 (при равенстве — наименьший порог).

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

В ответе запишите два числа через пробел: точность на обучении и точность на тесте.

Банк ищет лучший одиночный признак для прогноза дефолта. Файл credit.txt содержит 2200 строк: доход долговая_нагрузка возраст метка (первые три поля — целые, метка: 1 — дефолт, 0 — нет).

Для каждого из трёх признаков рассматривается пороговое правило. Правило может быть направлено в любую сторону: «метка 1, если признак не меньше порога» или «метка 1, если признак меньше порога» — выбирается то направление и порог, что дают наибольшую точность. Пороги перебираются по всем целым от минимума до максимума значений признака.

Определите, какой признак (1 — доход, 2 — долговая нагрузка, 3 — возраст) даёт наибольшую достижимую точность на всей выборке, и саму эту точность в процентах (округлённую до целого).

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

Файл iris.txt содержит 2500 строк с данными о цветках трёх видов: длина_лепестка ширина_лепестка вид (длина и ширина — вещественные, вид: 0, 1 или 2).

Классификатор — дерево решений с двумя порогами \( P_1 \) и \( P_2 \):

• если длина лепестка меньше \( P_1 \) — вид 0;
• иначе, если ширина лепестка меньше \( P_2 \) — вид 1;
• иначе — вид 2.

Переберите \( P_1 \) от 1.0 до 5.0 с шагом 0.1 и \( P_2 \) от 0.5 до 3.0 с шагом 0.1. Найдите пару порогов с максимальным числом верно классифицированных цветков. При равенстве выберите наименьший \( P_1 \), затем наименьший \( P_2 \).

В ответе запишите три числа через пробел: \( P_1 \) (один знак после запятой), \( P_2 \) (один знак после запятой) и число верных классификаций.

Ферма сортирует ягоды по содержанию сахара. Файл berries.txt содержит 3500 строк: сахар_процент метка (сахар — вещественное число, метка: 1 — спелая, 0 — неспелая).

Первые 2500 строк — обучающая выборка, последние 1000 — тестовая.

Правило: ягода спелая, если сахар не меньше порога \( K \).

Подберите порог \( K \) с максимальной точностью на обучающей выборке, перебирая значения от 0 до 30 с шагом 0.1 (при равенстве точности — наименьший порог). Затем примените найденный порог к тестовой выборке.

В ответе запишите число ошибок классификации на 1000 тестовых ягодах.

Сервис прогнозирует отток клиентов. Файл churn.txt содержит 3000 строк: дней_без_активности число_обращений_в_поддержку метка (первые два поля — целые, метка: 1 — клиент ушёл, 0 — остался).

Можно построить классификатор по одному из двух признаков с правилом «ушёл, если признак не меньше порога». Для каждого признака отдельно подберите порог, дающий максимальную точность на всей выборке (перебирая все целые пороги от минимума до максимума значений признака).

Определите, какой признак даёт более высокую максимальную точность: 1 — «дней без активности», 2 — «число обращений». Укажите номер этого признака и достигнутую им точность в процентах (округлённую до целого).

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

Система оценивает заявки по двум показателям. Файл apps.txt содержит 2800 строк: показатель1 показатель2 класс (показатели — целые от 0 до 100, класс: 1 или 0).

Правило использует сумму двух показателей: объект относится к классу 1, если \( x_1 + x_2 \ge K \).

Переберите целые \( K \) от 0 до 200, для каждого вычислите точность на всей выборке и найдите оптимальный порог \( K \) (при равенстве — наименьший).

В ответе запишите одно целое число — оптимальный порог \( K \).

Лаборатория настраивает порог диагностического маркера. Файл marker.txt содержит 3200 строк: уровень_маркера диагноз (уровень — вещественный, диагноз: 1 — болен, 0 — здоров).

Правило: пациент считается больным, если уровень маркера не меньше порога \( M \).

Для каждого целого \( M \) от 0 до 150 посчитайте сумму ошибок двух типов: ложные срабатывания (здоров, но помечен больным) плюс пропуски (болен, но помечен здоровым). Найдите порог \( M \), минимизирующий эту сумму (при равенстве — наименьший).

В ответе запишите одно целое число — оптимальный порог \( M \).

Файл mail.txt содержит данные о 3000 письмах: процент_заглавных_букв метка (метка: 1 — спам, 0 — не спам).

Первые 2000 строк — обучающая выборка, последние 1000 — тестовая.

Правило: письмо — спам, если процент заглавных не меньше порога \( K \).

Переберите \( K \) от 0 до 100 и подберите значение с максимальной точностью на обучающей выборке (при равенстве — наименьшее \( K \)). Затем примените найденный \( K \) к тестовой выборке.

В ответе запишите количество верно классифицированных писем из 1000 тестовых.

Платёжная система выявляет мошеннические переводы по сумме. Файл payments.txt содержит 2600 строк: сумма_перевода метка (сумма — целое число рублей, метка: 1 — мошенничество, 0 — легальный перевод).

Правило: перевод считается мошенническим, если сумма не меньше порога \( A \).

Переберите значения \( A \) от 0 до 20000 с шагом 100. Для каждого посчитайте число ошибок классификации. Найдите минимальное число ошибок среди всех порогов.

В ответе запишите одно целое число — минимальное число ошибок.

Фасовочная линия отбраковывает упаковки по отклонению веса. Файл weight.txt содержит 2800 строк: отклонение_веса_г метка (отклонение — неотрицательное вещественное, метка: 1 — годная упаковка, 0 — брак).

Правило: упаковка считается годной, если отклонение веса не превышает порог \( E \).

Переберите целые \( E \) от 0 до 50, для каждого вычислите точность на всей выборке и найдите \( E \) с максимальной точностью (при равенстве — наименьшее).

В ответе запишите одно целое число — оптимальный порог \( E \).

Банк подбирает порог кредитного скоринга. Файл score.txt содержит данные о 3000 заявках. В каждой строке: скоринговый_балл решение (балл — целое от 0 до 100; решение: 1 — кредит выдан и возвращён, 0 — не возвращён).

Правило: одобрять заявку, если балл не меньше порога \( S \).

Переберите целые \( S \) от 0 до 100 и найдите максимально достижимую точность классификации на всей выборке.

В ответе запишите точность в процентах, округлённую до целого числа.