Интернет-олимпиада по информатике
Код успеха
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) без архивирования.

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

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

Пример оформления кода, использующий корректный ввод/вывод данных. Обратите внимание: перед сдачей решений на 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), не считается видимым. Георгий хочет найти количество видимых камушков. Помогите ему это сделать. 

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

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

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

Примеры:

input.txt

output.txt

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.

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

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

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

Примеры:

input.txt

output.txt

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.

Вход: файл input.txt, в первой строке записаны два целых числа 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

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

Примеры:

input.txt

output.txt

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 декабря

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


Новости
Задания Интернет-олимпиады по информатике "Код успеха"

На сайте обучающей интернет-олимпиады по информатике "Код успеха" опубликованы задания для 5-6 классов и 7-11 классов.
Доступ к системе загрузки работ (в Виртуальном кабинете) будет открыт   для  участников и команд, подавших онлайн-заявки на участие Интернет-олимпиаде до 16 ноября включительно.
Прежде, чем начать выполнение заданий:

  • Внимательно прочитайте правила участия в Интернет-олимпиаде.
  • Ознакомьтесь с техническими требованиями к работам.
Очередной тур математического турнира (командной онлайн-игры) пройдет 24 октября

Очередной тур математического турнира (командной онлайн-игры) для школьников 5-7 классов пройдет 24 октября.  Приглашаем команды школьников (5 человек) присоединиться к участию. Познакомившись с правилами участия и презентациями, вы узнаете, как интересно, необычно и высокотехнологично проходит каждый тур! Успеть принять участие в следующем туре очень просто - командные заявки принимаются до 12:00 24 октября на сайте!

Обучающая интернет-олимпиада «Код успеха»

Приглашаем  школьников Ярославской области присоединиться  к участию в Обучающей интернет-олимпиаде «Код успеха». Олимпиада проводится с 12 по 23 ноября в двух возрастных номинациях: «5-6 классы» и «7-11 классы». Допускаются как командное, так и индивидуальное участие. Регистрация команд и индивидуальных участников  - до 16 ноября включительно.

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