Задания школьного этапа областной олимпиады по информационным технологиям 2016 г.

Класс.

1.Прочитайте стихотворение. Переведите встречающиеся в нем числительные из двоичной системы счисления в десятичную.

Необыкновенная девчонка
А. Н. Стариков

Ей было тысяча сто лет,
Она в 101-ый класс ходила,
В портфеле по сто книг носила –
Все это правда, а не бред.

Когда, пыля десятком ног,
Она шагала по дороге,
За ней всегда бежал щенок
С одним хвостом, зато стоногий.

Она ловила каждый звук
Своими десятью ушами,
И десять загорелых рук
Портфель и поводок держали.

И десять темно-синих глаз
Рассматривали мир привычно,…
Но станет все совсем обычным,
Когда поймете наш рассказ.

2. За праздничным столом собрались 4 поколения одной семьи: дед, отец, сын и внук. Их возраст в различных системах счисления записывается так 88 лет, 66лет, 44 года и 11 лет. Сколько им лет в десятичной системе счисления, если через год их возраст в тех системах счисления можно будет записать как 100?

3.В Воссоединенном Королевстве было несколько городов, некоторые из которых соединены дорогами. Известно, что из каждого города можно было проехать в любой другой (двигаться можно только по дорогам, переходить с одной дороги на другую можно только в городе). Также известно, что не было кольцевых маршрутов (то есть, нельзя было проехать по нескольким разным городам и дорогам и вернуться в тот город, с которого начали путь). Города, из которых выходила только одна дорога, жители королевства называли унылыми. Во времена короля Арагорна была также построена ВКАД (всекоролевская кольцевая арагорнская дорога) – кольцевая цепь дорог, которая по одному соединила все унылые города.

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

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

4. В известной сети гипермаркетов Heap-Hop ежегодно проводится следующая акция.

В декабре при покупке любого товара стоимостью не меньше 1 000 руб., за каждую целую тысячу рублей в стоимости одного товара выдаётся купон номиналом в 500 руб. Например, если мы покупаем в декабре один товар стоимостью 1 001 руб., а второй — 2 999 руб., то получим купон в 500 руб. за первый и всего два купона за второй. В январе полученные купоны можно использовать для оплаты 20% стоимости уже всей покупки в целом. То есть вне зависимости от стоимости отдельных товаров, если в январе общая сумма покупки в нашем примере будет не меньше 7 500 руб., то 1 500 мы оплатим купонами, а если меньше, то мы не сможем использовать все купоны полностью. Но даже за покупку стоимостью меньше 500 руб. мы сможем получить скидку в 20%, отдав купон номиналом 500 руб.

Семья Бережливых давно присмотрела ряд товаров в одном из гипермаркетов этой сети. Зная условия акции, они решили распределить покупки на два месяца так, чтобы в итоге заплатить за все товары вместе как можно меньше. Младший сын Бережливых Иван взялся написать программу, которая и выдаст соответствующие рекомендации, но родители не уверены, что его программа будет находить минимально возможную сумму денег, которой можно обойтись при покупке всех необходимых товаров с учётом акции. Поэтому подобную программу предлагается написать вам.

5. Определите маску для имен группы файлов: file.doc, ddg.dll, drug.d, forma.doc.

В каталоге находятся пять файлов:

fort.docx

ford.docx

lord.doc

orsk.dat

port.doc

Определите, по какой из масок из них будет отобрана указанная группа
файлов:

fort.docx

ford.docx

lord.doc

port.doc

6.Счастливые бусы

Девочки Лиза и Алиса - лучшие подруги. Девочки очень любят делать бусы своими руками. Недавно Лиза сделала себе бусы из A бусинок, а Алиса - из B бусинок.

Девочки хотят еще больше укрепить свою дружбу, для этого они собираются сплести счастливые бусы в подарок друг другу. Бусы считаются счастливыми, если количество бусинок в подаренных девочке бусах будет кратно количеству бусинок в уже имеющихся у девочки бусах, но при этом не равно нулю.

Лиза и Алиса купили упаковку из N бусинок. Помогите им узнать, сколько есть способов разделить все эти N бусинок между девочками, чтобы сплетенные для обеих девочек бусы были счастливыми.

Формат входных данных

На вход подаются три натуральных числа N, A и B.

Формат выходных данных

Должно быть выведено одно число - количество способов разделить все N бусинок между девочками.

7. Имеется квадрат в клеточку размером 16 на 16 клеток. В его угол (на угловую клетку) поставили умного робота, умеющего делать шаги вперед, назад, вправо и влево ровно на 1 клетку. Роботу дали задание переместиться в противоположный угол квадрата, пройдя через все клетки и побывав в каждой из них ровно по 1 разу.

В прямоугольнике 3 на 2 клетки робот смог бы это сделать ровно одним способом (существует ровно один маршрут, удовлетворяющий условию).

Сколькими способами умный робот сможет выполнить свое задание в квадрате 16х16? Обоснуйте Ваш ответ!

8.Ивана Александровича Хлестакова пригласили управлять департаментом. В 1-й день ему прислали 1000 курьеров, а в каждый последующий – в 2 раза больше, чем в предыду­щий. Иван Александрович согласился тогда, когда к нему прибыли сразу не менее 30000 курьеров. Вывести на экран сообщение о том, на какой день это произошло. Определить, не пользуясь умножением и делением: Иван Александрович с ними не в ладах. (10 баллов)

Формат вывода данных:

Это произошло на …-й день.

9. Последовательность из латинских букв строится следующим образом. На первом шаге она пуста. На каждом последующем шаге последовательность удваивается, после чего к ней слева дописывается очередная буква латинского алфавита (а, b, с, ...). Ниже приведены первые шаги построения последовательности:
Шаг 1. пустая последовательность
Шаг 2. а
Шаг 3. baa
Шаг 4. cbaabaa
Шаг 5. dcbaabaacbaabaa
Задача состоит в том, чтобы по заданному числу N определить символ, который стоит на N-ом месте в последовательности, получившейся после 26-го шага (символы отсчитываются слева направо). В качестве ответа указать символ, стоящий в позиции N получившейся последовательности.

10.У Оли есть доступ к сети Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 2²¹ бит в секунду. У Маши нет скоростного доступа в Интернет, но есть возможность получать информацию от Оли по низкоскоростному телефонному каналу со средней скоростью 2¹³ бит в секунду. Маша договорилась с Олей, что та будет скачивать для нее данные объемом 8 Мбайт по высокоскоростному каналу и ретранслировать их Маше по низкоскоростному каналу. Компьютер Оли может начать ретрансляцию данных не раньше, чем им будет получен 1 Мбайт этих данных. Сколько Кбайт успеет скачать Маша к моменту окончания скачивания информации Олей?

ЗАДАНИЯ ШКОЛЬНОГО ЭТАПА ОБЛАСТНОЙ ОЛИМПИАДЫ ПО ИНФОРМАЦИОННЫМ ТЕХНОЛОГИЯМ 2016 г.

Класс

1. Для кодирования цвета фона интернет-страницы используется атрибут <bgcolor=”#XXXXXX”>, где в кавычках задаются шестнадцатеричные значения интенсивности цветовых компонент в 24-битной цветовой модели RGB. Какой цвет будет у страницы, задаваемой тегом <bgcolor=”#FFFF00”>?

2. Музыкальная запись выполнена в формате CDDA (частота дискретизации 44100 Гц, 16 бит, стерео) и имеет продолжительность 19 мин 20 cек. Сколько секунд займет передача этой записи по каналу с пропускной способностью 16000 байт/сек?

3. Программа генерирует N-символьные пароли следующим образом: в качестве символов используются десятичные цифры, а также строчные и прописные латинские буквы в любом порядке (в латинском алфавите 26 знаков). Все символы кодируются одним и тем же минимально возможным количеством бит и записываются на диск. Программа сгенерировала 128 паролей и записала их в файл подряд, без дополнительных символов. Размер полученного файла составил 1,5 Кбайта. Какова длина пароля (N)?

4. Два друга — Петя и Вася — совместно используют канал доступа в Интернет с пропускной способностью 4 Кбайт в секунду. Система балансировки нагрузки настроена таким образом, что если в данный момент времени канал использует только один человек, то скачивание файла происходит со скоростью равной пропускной способности канала, а если канал используют оба друга – пропускная способность канала поровну делится между пользователями.

Петя начал скачивать музыкальную композицию. Через 8 секунд Вася начал скачивать графический файл. Петя закончил скачивать музыкальную композицию через 34 секунды от начала скачивания своего файла.

Музыкальная композиция была оцифрована в режиме «моно» с частотой дискретизации 1024 Гц и 65536 уровнями квантования.

Графический файл содержал 8192 пикселей, кодированных с использованием палитры из 256 цветов.

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

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

Сколько секунд длится музыкальная композиция, которую скачал Петя? В ответе укажите число.

5. Дана строка s равная «информатика». Поставить в соответствие каждой строке один из следующих алгоритмов

№	Строка		№	Алгоритм
	карта			s(-3)+s(3)+s(-1)+s(0)+s(5)
	фирма			s(4)+s(1)+s(-1)+s(2)+s(5)
	комар			s(-1)+s(-5)+s(-3)+s(0)+s(5)
	нимфа			s(4)+s(-2)+s(0)+s(1)+s(-1)
	рифма			s(-4)+s(3)+s(0)+s(-3)+s(5)

6. На одном из секретных заводов осуществляется обработка радиоактивных материалов, в результате которой образуются радиоактивные отходы двух типов: типа A — особо опасные и типа B — неопасные. Все отходы упаковываются в специальные прямоугольные контейнеры одинаковых размеров, после чего эти контейнеры укладываются в стопку (один над другим) для захоронения. Стопка является взрывоопасной, если в ней подряд идут более чем два контейнера с отходами типа A.

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

Технические требования:

Имя входного файла: INPUT.TXT

Имя выходного файла: OUTPUT.TXT

Формат входных данных:

единственная строка входного файла содержит целое число N — количество контейнеров в стопке (1 <= N <= 31).

Формат выходных данных:

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

7. Сколько существует различных наборов значений логических переменных x1, x2, x3, x4, y1, y2 y3, y4, которые удовлетворяют всем перечисленным ниже условиям?
(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1
(y1 \/ y2) /\ (y2 \/ y3) /\ (y3 \/ y4) = 1
(y1 → x1) /\ (y2 → x2) /\ (y3 → x3) /\ (y4 → x4) = 1
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, x3, x4, y1, y2 y3, y4, при которых выполнена данная система равенств.
В качестве ответа Вам нужно указать количество таких наборов.

8. Имеется N городов. Для каждой пары городов (I,J) можно построить линию связи, соединяющую эти два города и не заходящую в другие города. Стоимость такой линии связи A(I,J). Вне городов линии связи не пересекаются.

Представьте алгоритм для нахождения самой дешевой линий связи, позволяющей связаться из любого города в любой другой. Результаты задайте таблицей B[1:N,1:N], где B[I,J]=1 тогда и только тогда, когда линию связи, соединяющую города I и J, следует построить.

9. По заданным IP-адресу узла и маске определите адрес сети (используется терминология сетей ТСР/IP):

IP-адрес узла: 64.128.208.194

Маска: 255.255.224.0

10. В каталоге находится 6 файлов:
asc.wma
casting.wmv
last.wma
pasta.wmvx
pasta.wri
vast.wma

Определите, по какой из перечисленных масок из этих 6 файлов будет
отобрана указанная группа файлов:
casting.wmv
last.wma
pasta.wmvx
vast.wma

Приложение 2.