Задания

 

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

Виртуальный кабинет

Каждая команда или индивидуальный участник получает после регистрации доступ к Виртуальному кабинету.
С помощью Виртуального кабинета команда/индивидуальный участник:

• узнает новости проекта, уточняет ключевые даты
• подает ответы на задания Интернет-олимпиады
• отправляет письма координатору
• оставить свои отзывы и пожелания организаторам проекта

Ключевые даты

Этапы выполнения заданий	Дата получения (начала выполнения) задания	Дата окончания выполнения задания
Выполнение заданий проекта, загрузка работ через Виртуальный кабинет	11-00 (мск) 12 ноября 2018 г.	17-00 (мск) 23 ноября 2018 г.
Публикация итогов проекта		17-00 (мск) 4 декабря 2018 г.
Команды и участники отправляют отзыв о проекте из Виртуального кабинета.	23 ноября 2018 г.	4 декабря 2018 г.

Задачи теоретической части

В предложенных задачах требуется дать словесное описание алгоритма решения предложенной задачи (если не оговаривается что-то другое). При проверке решений (алгоритмов) будут учитываться следующие параметры:

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

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

Задача 1. 

 В компьютере завёлся не очень злобный вирус. Раз в минуту он прерывает нормальную работу компьютера и предлагает пользователю ввести код нейтрализации. Если пользователь введёт правильный код, вирус прекращает свою работу, если код неправильный, то к коду нейтрализации вирус прибавляет или из него вычитает единицу, и вирус продолжает работу. Код нейтрализации – это трёхзначное неизвестное нам число в диапазоне от 000 до 999. Известно, что прибавление и вычитание единицы оставляет число в этом диапазоне. Может ли пользователь гарантированно остановить работу вируса, и если да, то как?

Задача 2.

При написании программы используются служебные слова (if, then, goto, begin, end, и многие другие). Список всех служебных слов задан. В трансляторе все эти слова должны быстро распознаваться. Предложите способ организации словаря всех служебных слов и способа поиска в нём нужного слова. Предложенные решения будут оцениваться как с точки зрения скорости работы, так и с точки зрения объема используемой памяти. (Все слова образованы малыми латинскими символами, длина каждого не превышает 100, слов может быть сколько угодно.)

Задача 3.

Для тестирования некоторой программы требуется сгенерировать двумерный числовой массив (таблицу) размера N×N, в котором встречаются все натуральные числа от 1 до N^2 в произвольном порядке. Изначально в массиве стоят нули. Для генерации теста разрешено использовать только одну операцию: выбрать два клетки соответствующей таблицы, отстоящие друг от друга на ход коня, и к содержимым этих клеток прибавить по единице. Опишите алгоритм, как это сделать, если это возможно. Размер таблицы задаётся.

Задачи практической части

Внимание: загрузка работ будет возможна с 12:00 13 ноября 2018 года. Загружается только исходный текст программы (файл *.pas, *.c, *.cpp) без архивирования.

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

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

Пример оформления кода, использующий корректный ввод/вывод данных. Обратите внимание: перед сдачей решений на C/C++ при использовании функции freopen следует подключать библиотеку stdio.h/cstdio. 

Ограничения на время выполнения программы по каждому из тестов: 2 секунды. Программы, не укладывающиеся во время прохождения теста в установленные ограничения или выдающие ошибку, считаются не прошедшими данный тест.

Задача 1. Видимые точки

Георгий так любит математику, что видит её практически во всём. Вот и отдыхая на пляже, он взял (N+1)x(N+1) камушков и разложил их в целочисленных точках квадрата размером NxN, находящегося в первой четверти плоскости. Левый нижний угол квадрата находится в точке (0,0), правый верхний – в точке (N,N).  Камушек, находящийся в точке (x,y) будем называть видимым, если на прямой, проведенной из (0,0) в (x,y), не лежит ни один другой камушек. Камушек, лежащий в точке (0,0), не считается видимым. Георгий хочет найти количество видимых камушков. Помогите ему это сделать. 

Вход: stdin, в первой строке записано натуральное число N.

Ограничения: 1≤N≤10⁵

Выход: stdout, содержащий единственное число – количество видимых камушков.

Примеры:

stdin	stdout
2	5
4	13
5	21

Примечание:

Ниже проиллюстрирован пример с видимыми точками в квадрате 5x5:

Задача 2. Необычное развлечение

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

Например, если n=30, то существует несколько способов получить из него единицу. Например, 30→10→1 или 30→6→3→1, или 30→1. Всего это можно сделать 13 способами.

Георгий просит вас помочь подсчитать количество способов, которыми он может получить из числа n единицу. Два способа n→x₁→…→x_k→1 и n→y₁→…→y_m→1 считаются различными, если k≠m или существует i такое, что x_i≠y_i.

Вход: stdin, в первой строке записано натуральное число n.

Ограничения: 1≤N≤2*10⁹

Выход:stdout, содержащий единственное число – количество способов получить из числа n единицу по модулю (10⁹+7) (т. е. вывести остаток от деления количества способов получить единицу на 10⁹+7).

Примеры:

stdin	stdout
1	1
9	2
30	13

Задача 3. Конструктор

Помимо математики Георгий любит собирать замки из конструкторов. В магазин завезли n конструкторов. Конструкторы пронумерованы числами от 1 до n.

У Георгия есть 2 способа получить нравящийся конструктор:

1. Купить его. Конструктор с номером i стоит c_i рублей;
2. Купить и объединить два конструктора, получив из них другой конструктор. Возможные способы компоновки конструкторов заданы тройками чисел (x, y, z). Купив конструкторы с номерами y и z, можно их объединить и получить один конструктор с номером x. Всего есть m доступных троек (x, y, z)

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

Вход: stdin, в первой строке записаны два целых числа n и m. Во второй строке содержатся n чисел c_i  – стоимости конструкторов. В следующих m строках содержится по 3 числа x_i, y_i, z_i – это означает, что конструктор номер x_i может быть скомпонован из конструкторов y_i и z_i.  

Ограничения: 1≤ n≤ 10⁴, 0≤ m≤ 10⁵, 0 ≤ c_i ≤ 10⁹, 1 ≤x_i,y_i,z_i≤ n

Выход: stdout, содержащий единственное число – минимальная сумма денег, которую потратит Георгий.

Примеры:

stdin	stdout
4 2 8 1 1 3 4 2 3 1 2 4	3
4 2 2 1 1 3 4 2 3 1 2 4	2

Примечание:

В первом тестовом примере, можно купить конструкторы номер 2 и 3, собрать из них детали для конструктора номер 4, затем купить ещё один конструктор номер 2 и собрать из имеющихся конструкторов конструктор номер 1. На это будет затрачено 1+1+1=3 рубля.