В ответе запишите целое число.

1 Задания отборочного этапа олимпиады года для 9 и 10 класса Отборочный этап 9 и 10 класса. 1 тур (приведен один из вариантов заданий) 1. Системы счисления (1 балл) [Умножитель] Задано следующее неравенство: х х 143 Определите максимально возможное основание позиционной системы счисления Х, при котором будет выполняться неравенство, если известно, что Y и Z являются двухразрядными числами в этой системе счисления. В ответе укажите целое число. Ответ: 8 2. Системы счисления (2 балла) [Остатки] Определите количество натуральных чисел меньших , для которых выполняется условие: в записях числа в пятеричной и пятнадцатеричной системах счисления в младшем разряде стоит цифра 2. В ответе запишите целое число. Ответ: Количество информации (2 балла) [Социальная сеть] Любой пост в некоторой социальной сети может содержать изображение и текст. При оформлении текста комментария используется моноширинный шрифт с фиксированной шириной знакоместа в пикселях. Это значит, что любой символ, включая знак препинания или пробел, по ширине занимает одинаковое количество пикселей, учитывающее, в том числе, межсимвольный промежуток. Длина строки соответствует ширине изображения опубликованного в посте. Василий решил опубликовать фотографию, сделанную со смартфона, и добавить к ней текстовый комментарий. Он подобрал изображение шириной 512 и высотой 384 точки. Определите количество строк в комментарии, если известно, что: 1. Василий использовал максимально возможное количество символов в каждой строке. 2. Для кодирования текста используется двухбайтная кодировка. 3. Ширина одного знакоместа 8 пикселей. 4. Изображения имеет глубину цвета 16 бит. 5. Информационный объем поста 386 КБайт. 6. Никакой дополнительной информации кроме картинки и комментария Василия в сообщении не содержится. В ответе напишите целое число. Ответ: Кодирование информации (3 балла) [RLE-кодирование] На предприятии собираются изделия. Каждое изделие состоит из деталей нескольких видов. Каждому виду деталей присвоен буквенный индекс (А, В, С ). В процессе сборки несколько деталей одного вида могут попадать в сборку подряд, такая последовательность деталей называется комплект. Комплекту присваивается код, состоящий из буквы, соответствующей индексу детали из которой составлен комплект, и числа, соответствующего количеству деталей в комплекте. Например, комплект из 23-х деталей с индексом А будет иметь код А23. В сборке могут встретиться несколько комплектов деталей одного вида, но не подряд. Для описания последовательности сборки изделия, коды комплектов записывают последовательно, в соответствии с порядком сборки. Для удобства записи, одиночная деталь участвующая в сборке тоже обозначается как комплект, например В1. В результате, последовательность: 3 детали А, 5 деталей С, 1 деталь В, 6 деталей А. Будет записана как А3С5В1А6. Минимальное количество бит, которые потребуются для хранения последовательности сборки изделия, зависит от количества комплектов в изделии, максимального количества деталей в любом из комплектов и максимального количества видов деталей. Индексы деталей кодируются одинаковым минимально возможным количеством бит. Для кодирования количества деталей в комплектах, так же используется одинаковое минимально возможное количество бит. Определите максимально возможное количество деталей одного типа в составе комплектов изделия, если известно, что: 1. Максимальное количество различных видов деталей в изделии Комплектов в изделии Для хранения информации о полном составе такого изделия требуется 24 байт. В ответе запишите целое число. Ответ: Основы логики. Упрощение логического выражения (2 балла) [Шиворот-навыворот] Упростите логическое выражение или укажите его результат (при его однозначности). Результат упрощения может содержать только операции инверсии, конъюнкции и дизъюнкции. (A not B and C) (C and not B A) Комментарий по вводу ответа: операнды вводятся большими латинскими буквами; логические операции обозначаются, соответственно как not, and и or. Скобки используются только для изменения порядка выполнения операций. Если порядок выполнения операций очевиден из их приоритетов дополнительное использование скобок считается ошибкой. При однозначном ответе истинный ответ обозначается как 1, а ложный как 0. Пример записи ответа: (A or not B) and C Ответ: A or B or not C A or not C or B B or A or not C B or not C or A not C or A or B not C or B or A

2 6. Основы логики (1 балл) [Цветные круги] На рисунке приведена аддитивная цветовая схема, принятая в большинстве световых аппаратных устройств, в том числе в мониторах: Выражения R, G и B истины для всех точек красного, зеленого и синего кругов соответственно, включая области их пересечения с другими кругами. Выберете те логические выражения, которые являются истинными только для области закрашенной черным цветом. Для доступа к ответам нажмите «Ответить». 1. R and not G and B or R and G and not B 2. R and not G and B or B and G and R 3. R and (G xor B) 4. B and G and not R or not G and B and R 5. not (not R or (not G xor not B)) Ответ: Основы логики (2 балла) [Неразлучные друзья] Коля, Вася, Петя, Саша и Дима учатся в одной школе. Каждый из них дружит ровно с двумя из перечисленных мальчиков. Дружба любых двух мальчиков всегда взаимна. Определите, с кем кроме Коли дружит Саша, если известно, что все приведенные высказывания истинны: Если Коля дружит с Васей, то и Петя дружит с Васей. Если Петя дружит с Димой, то Саша дружит с Колей. Если Вася дружит с Петей, то и Дима дружит с Петей. Если Коля дружит с Сашей, то Вася дружит с Колей. В ответе запишите первую букву имени мальчика, с которым может еще дружить Саша. Ответ: Д 8. Алгоритмизация и программирование (1 балл) [Быстрый перевод] Дана блок-схема фрагмента программы, обрабатывающей одномерный массив. Какое значение приобретет переменная S после завершения выполнения этого фрагмента, если на вход подали целочисленный массив A из 18 элементов, приведенный ниже? Несколько элементов массива, обозначенных символом # не известны. Индексация элементов массива начинается с единицы. Операция DIV возвращает целую часть от деления. В ответе укажите целое число. A 2, 4, #, 2,16, #, 4,16, #, 4,128, #, 8,128, #, 8, 512,# 2

3 Ответ: Алгоритмизация и программирование (2 балла) [Разделитель] Дан фрагмент программы: Бейсик Паскаль Алгоритмический INPUT n WHILE n <> 0 m=n MOD X PRINT m n=n \ X WEND readln(n); while n <> 0 do begin m:=n mod X; write(m); n:=n div X; end; 3 ввод n нц пока n <> 0 m:=mod (n,x) вывод m n:=div (n,x) кц Функции MOD, mod вычисляют остаток от деления первого аргумента на второй. Функции \, div вычисляют целую часть от деления первого аргумента на второй. Чему было равно значение целой положительной переменной X перед началом выполнения этого фрагмента, если при выполнении фрагмента в переменную n записали число 31, а после завершении выполнения фрагмента на экране было записано «111»? Если таких значений несколько в ответе укажите минимальное из них. В ответе напишите целое число. Ответ: Алгоритмизация и программирование (3 балла) [Переобувка] Сороконожка решила отремонтировать сапоги. Сороконожка имеет 40 ног и, соответственно, у нее 20 пар обуви. Все сапоги требуют ремонта.

4 В обувной мастерской есть подмастерье, который умеет быстро снимать и надевать сапог клиенту, затрачивая на каждую операцию ровно по 30 секунд. Также в мастерской есть два мастера. Первый ремонтирует сапог за 3 минуты, Второй ремонтирует сапог за 2 минуты. Подмастерье снимает сапог и он сразу попадает к свободному мастеру (первый снятый сапог попадает ко Второму мастеру). Если оба мастера заняты, то очередной сапог ложится на стол, стоящий между мастерами и как только один из мастеров заканчивает ремонт предыдущего сапога, он может взять очередной сапог со стола. Если есть хотя бы один отремонтированный сапог, подмастерье не снимает новый сапог, пока не оденет все отремонтированные. Если совпадает время завершения ремонта сапога мастером и завершение операции снимания или надевания сапога подмастерьем, подмастерье видит отремонтированный сапог и начинает его надевать. Подмастерье снимает обувь с сороконожки все время, кроме тех случаев, когда надевает отремонтированный сапог или пока не закончатся неотремонтированные сапоги. Определите максимальное количество ног сороконожки, которые одновременно могут оказаться без сапог. В ответе напишите целое число. Ответ: 15 Отборочный этап 9 и 10 класса. 2 тур (приведен один из вариантов заданий) 1. Технологии хранения, поиска и сортировки информации (3 балла) [Мобильный трафик] На мобильном устройстве необходимо отобразить прайс-лист магазина таблицу, имеющую следующие столбцы: Артикул Наименование Цвет Цена Количество Любая строка начинается со значения в столбце, оно формируется автоматически на мобильном устройстве и имеет значение соответствующее порядковому номеру строки. Далее в строке отображаются значения для остальных столбцов. На сервере есть база данных, которая имеет следующую конфигурацию: Таблица «Изделие» ID_Изделия 10 цифр Таблица «Цвет» Артикул 12 цифр ID_Цвета 10 цифр Наименование 25 букв Цвет 25 букв Таблица «Остатки» ID_Изделия 10 цифр ID_Цвета 10 цифр Количество 5 цифр Цена 7 цифр Существует два сценария работы мобильного приложения: 1. На сервер отправляется запрос пользователя, по которому формируются строки прайс-листа. Затем все сформированные строки передаются мобильному приложению. При передаче строк каждый передаваемый символ (буква или цифра) кодируется 2-мя байтами. Для значения каждого столбца всегда используется указанное в конфигурации количество символов и не меньше. Таким образом, длина каждой передаваемой строки соответствует суммарному количеству символов указанному для столбцов. Никакой дополнительной информации не передается. 2. Мобильное приложение полностью получает содержимое таблиц базы данных в указанной конфигурации и самостоятельно формирует прайс-лист по запросу пользователя. При передаче символы (буквы или цифры) всех полей, в том числе ключевых кодируются 2-мя байтами. Определите, какое число строк было в таблице «Цвет», если известно, что таблица «Изделие» содержала ровно 21 строку (количество уникальных наименований изделий), каждое изделие доступно во всех цветах, указанных в таблице «Цвет», в таблице «Остатки» содержится по одной строке для каждой комбинации наименования изделия и его цвета. В прайс-лист вошло ровно по одной строке для каждого цвета каждого наименования изделия и при этом, по первому сценарию на мобильное приложение было передано на 8190 байт больше данных, чем при работе по второму сценарию. При расчетах объема передачи никакие данные, кроме указанных в сценариях, не учитывались. В ответе укажите целое число, соответствующее количеству строк в таблице «Цвет». Ответ: 6 2. Технологии хранения, поиска и сортировки информации (2 балла) [Букинист] В базе данных библиотеки хранятся записи о книгах. В том числе в каждой из них есть указание о годе издания (с 1900 до 2015), количестве страниц (от 10 до 1 000) и количестве авторов (один или несколько). Известно количество записей, получаемых в ответ на ряд запросов к этой базе: 1. Книга написана одним автором 44 записи. 2. Книга с количеством страниц не менее записей. 3. Книга с количеством страниц менее 500 и написана одним автором 11 записей. 4. Книга с количеством страниц не менее 500 и выпущена не ранее 1950 года 35 записей. 5. Книга написана несколькими авторами, с количеством страниц не менее 500 страниц и выпущена не ранее 1950 года 20 записей. Сколько записей будет получено в результате запроса: Книга написана несколькими авторами, с количеством страниц не менее 500 страниц и выпущена до 1950 года. В ответе напишите целое число. 4

5 Ответ: Технологии обработки информации в электронных таблицах (1 балл) [Где логика?] Дан фрагмент таблицы в режиме отображения формул: Ячейку D2 скопировали во все ячейки диапазона D3:D9. Ячейку E2 скопировали во все ячейки диапазона E3:E9. Ячейку F2 скопировали во все ячейки диапазона F3:F9. Определите, на какие ячейки были установлены ссылки в формуле в ячейке E2 до копирования, если: 1. Х1, Х2, Х3 указывают на разные ячейки диапазона A2:C2. 2. если последовательность 1 и 0 полученных в диапазоне ячеек F2:F9 представить в виде двоичного восьмиразрядного числа, у которого самым старшим разрядом является значение указанное в ячейке F9, а младший соответствует значению ячейки F2 и перевести в десятичную систему счисления, то оно будет иметь значение 178. В ответе запишите, без пробелов и запятых, сначала значение Х1, затем Х2, затем Х3. Ответ: С2В2А2 4. Технологии обработки информации в электронных таблицах (1 балл) [Буратино спекулянт] Для анализа курса акций часто применяют специальный вид графиков, который называется «Японские свечи». Каждая «свеча» состоит из чёрного либо белого тела и верхней/нижней тени (иногда говорят фитиль). Верхняя и нижняя граница тени отображает максимум и минимум цены за соответствующий период. Границы тела отображают цену открытия и закрытия периода торгов, по которому строится эта «свеча». При этом если цена закрытия оказалась больше, чем цена открытия, то тело «свечи» белое, а если наоборот черное. Обычно такой график строится за определенный период, например 10 дней, а каждая «свеча» обозначает результаты отдельного торгового дня. Входными данными для построения каждой «свечи» является последовательность чисел, в которой каждое число обозначает цену, по которой была осуществлена сделка. Первое число в последовательности является ценой открытия торгов в этот день, а последнее ценой закрытия торгов. Приведен график курса акций компании «Папа Карло» за 10 дней. По оси абсцисс указаны номера дней, а по оси ординат цены в «золотых» за одну акцию. 14 Папа Карло Буратино решил заработать на акциях компании «Папа Карло». У него есть 6 золотых. Он может один раз в течение указанных 10 дней купить максимальное количество акций на имеющиеся у него 6 золотых. Например, в первый день он может купить 1-ну акцию по цене от 4 до 6 золотых, а во второй день 2 акции по цене 3 золотых за штуку, или 1-ну по цене от 4 до 6 золотых. В течение последующих 2-х дней с момента покупки, но не в день 5

6 покупки, он может один раз продать все купленные акции по любой цене в течение торгового дня. Покупка и продажа проходит только при целочисленных значениях стоимости акции. Определите, в какой день ему выгоднее всего купить акции и в какой продать, что бы получить максимальную выгоду. В ответе укажите без пробелов и запятых, два числа, сначала номер дня покупки, затем номер дня продажи. Ответ: Телекоммуникационные технологии (2 балла) [Domain Name System] Система DNS - Domain Name System (Система доменных имен) предназначена для отображения друг на друга пространства IP адресов и доменных символьных имен. Когда в адресной строке браузера пользователь указывает доменное имя, например система DNS определяет соответствующий ему IP-адрес , и уже по IP адресу пользовательский компьютер устанавливает соединение с Web-сервером В приведенном примере найденный IP-адрес является адресом компьютера «www», находящегося в домене «yandex», который в свою очередь находится в домене «ru», который в свою очередь находится в корневом домене «.». Обратите внимание, что на самом деле доменное имя заканчивается на «.» - « Символ «.» в конце имени обычно опускают, но система DNS «дописывает» эту точку автоматически. Данные DNS хранятся распределенно на DNS-серверах. Адреса корневых «.» DNS-серверов известны заранее. На одном DNS-сервере может храниться информация о доменных именах в одном или нескольких доменах. DNS-сервер содержит записи об именах компьютеров в обслуживаемом им домене и адресах DNS-серверов дочерних (вложенных) доменов. DNS-сервера работают в двух режимах - рекурсивном и нерекурсивном. В рекурсивном режиме DNS-сервер сам опрашивает все необходимые DNS-сервера и возвращает запросившему (это может быть компьютер или другой DNS-сервер) ответ о соответствии доменного имени и IP адреса. В нерекурсивном режиме DNS-сервер возвращает запросившему (это может быть компьютер или другой DNS-сервер) IP адрес следующего DNS сервера, которому следует отправить запрос. Рассмотрим пример. Существует клиентский компьютер (С1), у которого в параметрах конфигурации IP указан IPадрес его DNS-сервера (D1). От С1 к D1 поступает запрос на разрешение имени « Предположим что кэширование (сохранение результатов предыдущих запросов) полностью отсутствует. DNS-сервер D1 рекурсивный. Он, получив запрос от С1 и обращается к корневому «.» DNS-серверу с запросом об адресе « (1). Корневой DNSсервер «.» нерекурсивный, он вернет D1 адрес DNS-сервера домена «RU.» (назовем его D2) (2). D1 отправит D2 запрос об адресе « (3). D2 тоже нерекурсивный. В ответ он отправит D1 адрес DNS-сервера домена «YANDEX.RU.» (назовем его D3) (4). D1 отправит D3 запрос об адресе « (5) и получит от него искомый IP адрес (6). На последнем этапе D1 передаст С1 ответ. Таким образом, для сервера D1 суммарное количество запросов и ответов, которые он совершил и получил для того, чтобы подготовить ответ клиентскому компьютеру C1 оказалось равно 6. Студенты Иван и Петр изучают сетевые технологии. В среде моделирования они собрали прототип системы DNS. В их модели за каждый домен отвечает отдельный DNS-сервер. Кэширование отсутствует. В модель добавлены клиентский компьютер C1 и обслуживающий его DNS сервер D1. Клиентский компьютер запросил IP-адрес по доменному имени «dataserver.dom3.dom2.dom1.local.» Разрешение имени произошло успешно. Определите суммарное количество запросов и ответов, которые совершил и получил сервер D1 при разрешении имени, при условии, что нерекурсивными оказались только сервера доменов «.», «local» и «dom1». При подсчете не учитывать диалог между D1 и С1. В ответ укажите целое число. Ответ: 8 6. Операционные системы, множественный выбор ответа (1 балл) [Двойной выбор] Есть различные способы формально описать правила формирования последовательности идущих подряд символов для их выделения среди других последовательностей символов, например для поиска имен файлов в каталоге. Наиболее распространенными способами являются регулярные выражения и маски файлов. Для задания регулярных выражений приняты следующие обозначения: с Любой неспециальный символ с соответствует самому себе. Специальными символами будем считать только символы [, ], , *, +, -,? эти символы не могут по условию данной задачи встретится в тексте. [. ] Любой символ из. ; допустимы диапазоны типа а-z (последовательно идущие символы в алфавите); возможно объединение диапазонов, например [a-z0-9] и сочетание диапазонов и отдельных символов [a-z0-9

#]. r* Ноль или более вхождений символа r, может применяться и для диапазонов, например [a-z#]* означает ноль или более вхождений любых символов из диапазона от a до z или символа # в любом порядке. r+ Одно или более вхождений символа r, может применяться и для диапазонов, например [a-z>]+ означает одно или более вхождений любых символов из диапазона от a до z или символа > в любом порядке. r? Ноль или одно вхождение символа r, может применяться и для диапазонов, например означает ноль или одно вхождение любого символа из диапазона от a до z или r1r2 За символом или диапазоном r1 следует символ или диапазон r2. < >Число вхождений предыдущего выражения. Например, выражение [0-9] соответствует подстроке из пяти десятичных цифр. 6