Интернет-олимпиада по информатике
Код успеха
2018
Интернет-проекты Код успеха 2018

Задания

 

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

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

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

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

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

Этапы выполнения заданий

Дата получения (начала выполнения) задания

Дата окончания выполнения задания

  1. Выполнение заданий проекта, загрузка работ через Виртуальный кабинет

11-00 (мск)
12 ноября 2018 г.

17-00 (мск)
23 ноября 2018 г.

  1. Публикация итогов проекта
 

17-00 (мск)
4 декабря 2018 г.

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

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≤105

Выход: 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→x1→…→xk→1 и n→y1→…→ym→1 считаются различными, если km или существует i такое, что xi≠yi.

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

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

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

Примеры:

stdin

stdout

1

1

9

2

30

13

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

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

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

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

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

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

Ограничения: 1≤ n≤ 104, 0 m 105, 0 ci 109, 1 xi,yi,zi 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 рубля.

 

Календарь 2018 г.

Сентябрь
Октябрь
Ноябрь
Декабрь
19 октября - 16 ноября

Онлайн-регистрация


12 - 23 ноября

Выполнение заданий


4 декабря

Подведение итогов


4 - 5 декабря

Рассылка электронных сертификатов


Новости
О сертификатах участия и дипломах

Благодарим школьников и педагогов за интерес к Интернет-олимпиаде "Код успеха"-2023.
Напоминаем, что итоги олимпиады опубликованы в разделе Итоги.
Убедительно просим скачать в Кабинетах команд и участников электронные сертификаты участия и благодарственные письма. Для победителей, призеров и дипломантов  из-за пределов Ярославской области в Кабинетах команд и участников опубликованы дипломы в электронном виде. Дипломы для команд и участников из Ярославской области (в печатном виде) будут переданы в школы.

Сводные протоколы участников и команд

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

Интернет-олимпиада «Код успеха» - 2023

16 ноября закончен прием ответов на задания Интернет-олимпиады «Код успеха» - 2023. Свои силы в решении задач попробовали участники и команды из 13 регионов России. Результаты (сводные протоколы) будут опубликованы на сайте Интернет-олимпиады «Код успеха» 30 ноября 2023 года.

Контакты: informat@edu.yar.ru