Информатика

Скажем, что последовательность строк t₁ , ..., t_k является путешествием длины k , если для всех i > 1 t_i является подстрокой t_{i - 1} строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t₁ , ..., t_k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u₁ , ..., u_{k + 1} , такие, что s = u₁t₁u₂ t₂ ... u_k t_k u_{k + 1} . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .

Входные данные
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .

Во второй строке содержится строка s , состоящая из n строчных английских букв.

Выходные данные
Выведите одно число — наибольшую длину путешествия по строке s .

Примечание
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .

Во втором примере подходящим вариантом будет { bb , b } .

Примеры

№	Входные данные	Выходные данные
1	7 abcdbcc	3
2	4 bbcb	2

Напишите программу подсчёта количества элементов последовательности натуральных чисел, запись которых в восьмеричной системе счисления четырёхзначна и оканчивается на цифру 5. В ответе запишите количество искомых элементов.

Программа получает на вход натуральные числа. Количество введённых чисел неизвестно, но не превышает 1000. Последовательность чисел заканчивается числом 0 (0 – признак окончания ввода, не входит в последовательность).

Программа должна напечатать только одно число – количество искомых элементов последовательности.

Пример работы программы

Входные данные	Выходные данные
485 557 893 3029 4125 0	3

*Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: — символ «?» означает ровно одну произвольную цифру; — символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300425. Найдите все натуральные числа, принадлежащие интервалу [10⁸; 10⁹], которые соответствуют маске ?*61*49 и имеют ровно три натуральных делителя. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа запишите его второй по величине делитель.

*Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: — символ «?» означает ровно одну произвольную цифру; — символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300425. Найдите все натуральные числа, принадлежащие интервалу [5·10⁸; 10⁹], которые соответствуют маске ?*88*81 и имеют ровно три натуральных делителя. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа запишите его второй по величине делитель.

*Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: — символ «?» означает ровно одну произвольную цифру; — символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300425. Найдите все натуральные числа, принадлежащие интервалу [3·10⁸; 6·10⁸], которые соответствуют маске ?*26*89 и имеют ровно три натуральных делителя. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа запишите его второй по величине делитель.

*Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы: — символ «?» означает ровно одну произвольную цифру; — символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность. Например, маске 123*4?5 соответствуют числа 123405 и 12300425. Найдите все натуральные числа, принадлежащие интервалу [10⁸; 2·10⁸], которые соответствуют маске ?*29*61 и имеют ровно три натуральных делителя. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа запишите его второй по величине делитель.

Дано клетчатое поле N x M, все клетки поля изначально белые. Автомат умеет:

закрасить клетку (i,j) в черный цвет.
для клетки (i,j) узнать её ближайших белых соседей по вертикали и горизонтали.
Дана последовательность команд для автомата. Требуется выполнить эти команды в указанной последовательности, и для каждой команды запроса ближайших белых соседей указать результат ее выполнения.

Входные данные
Сначала вводятся размеры поля N и M (1 ≤ N ≤ 20, 1 ≤ M ≤ 50000), затем количество команд K (1 ≤ K ≤ 10⁵), а затем сами команды. Команды записаны по одной в строке в следующем формате:

Color i j — окраска клетки (i,j) в черный цвет;
Neighbors i j — нахождение белых соседей для БЕЛОЙ клетки (i,j).

1 ≤ i ≤ N, 1 ≤ j ≤ M.

Выходные данные
На каждый запрос Neighbors требуется вывести сначала количество ближайших белых соседей (или 0, если ни с одной из сторон белых клеток не осталось), а затем их координаты (соседей можно перечислять в произвольном порядке). Если запросов Neighbors нет, ничего выводить не надо.

Примеры

№	Входные данные	Выходные данные
1	5 5 6 Color 4 2 Neighbors 4 3 Color 2 3 Color 3 3 Neighbors 4 3 Neighbors 5 1	4 4 1 4 4 3 3 5 3 4 4 1 4 4 1 3 5 3 2 5 2 4 1

Назовем подпоследовательностью массива a непустой массив b такой, что он может быть получен из массива a удалением нескольких (возможно, никаких) элементов массива a. Например, массив [1,3]  является попоследовательностью массива [1,2,3] , но [3,1]  не является.

Назовем подотрезком массива a непустой массив b такой, что он может быть получен путем удаления нескольких (возможно, никаких) первых и последних элементов массива a. Например, [1,2]  является подотрезком массива [1,2,3] , а [1,3]  не является. Несложно заметить, что у массива длины n ровно  \( {n(n+1) \over 2}\)  подотрезков.

Назовем массив a длины n возрастающим , если для любого 1 ≤ i ≤ n выполняется a_i ≤ a_i+1.

Монотонностью массива назовем количество его возрастающих подотрезков.

Дан массив a длины n. Посчитайте сумму монотонностей по всем его подпоследовательностям. Так как ответ может быть очень большим, выведите его по модулю 10⁹+7.

Входные данные
В первой строке задано целое число n (1 ≤ n ≤ 200000) — длина массива a.
Во второй строке заданы n целых чисел (1 ≤ a_i ≤ 200000) — элементы массива a.

Выходные данные
Выведите одно целое число — сумму монотонностей всех подпоследовательностей по модулю 10⁹+7.

Примечание
В первом тестовом примере у массива есть 7 подпоследовательностей:

• У массива [1]  есть ровно один подотрезок и он является возрастающим.
• У массива [2]  есть ровно один подотрезок и он является возрастающим.
• У массива [3]  есть ровно один подотрезок и он является возрастающим.
• У массива [1,2]  есть три подотрезка ([1], [2], [1,2] ) и все они являются возрастающими.
• У массива [1,3]  есть три подотрезка ([1], [3], [1,3] ) и все они являются возрастающими.
• У массива [3,2]  есть три подотрезка ([3], [2], [3, 2] ), но только два из них ([3]  и [2] ) являются возрастающими.
• У массива [1,3,2]  есть шесть подотрезков ([1], [3], [2], [1,3], [3,2], [1,3,2] ) и четыре из них ([1], [3], [2], [1,3] ) являются возрастающими.

Во втором тестовом примере все возрастающие подотрезки всех подпоследовательностей имеют длину 1.

Примеры

№	Входные данные	Выходные данные
1	3 1 3 2	15
2	3 6 6 6	12

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

13.1

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

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

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

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

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

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

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

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

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

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

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

[Изображение]

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

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

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

13.2

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

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

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

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

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

---

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

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

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

Информация о линии
Открытие первого участка	29 апреля 1961 г.
Длина, км	30,1
Количество станций	18
Время поездки, мин.	47
Среднесуточная перевозка пассажиров, тыс. человек/сутки	772,4
Подвижной состав
Максимальное число вагонов в составе поезда	6
Тип	«Юбилейный»

Файл 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 тестовых.