Олимпиады ИСАУ для школьников

Институт системного анализа и управления Университета "Дубна"

Задачи очного тура олимпиады ИСАУ для учащихся 9 - 10 классов

Если вы участвуете в олимпиаде дистанционно: решение нужно прислать в pdf-файле, который может содержать отсканированное с бумажного носителя решение или решение, оформленное с помощью любого программного продукта, например, текстового редактора. Если решением задачи является программный код, то на проверку нужно отправить непосредственно файл с кодом.

Задача 1

Максимальное количество баллов – 5.

Самюэл Финли Бриз Морзе подавал большие надежды как художник и был профессором живописи в Нью-Йоркском университете. Именно там в 1835 впервые была продемонстрирована первая машина, способная передавать сигналы по проводам, создателем которой был Морзе. В дальнейшем, работая над ее усовершенствованием, им же была составлена специальная азбука. Надо заметить, что исходная таблица "кода Морзе" разительно отличалась от ее современного представления, которая появилась лишь в 1939 году.

Ниже зашифрованы аббревиатуры названия кафедр Института САУ (справочная информация приведена далее):
1) • • • • — • • —
2) • • —
3) • —• • • • — — • • •

Справочная информация:
А • —
В • — —
И • •
Р • —•
С • • •
Т —
У • • —

Расшифруйте названия кафедр (1 балл)
Сколько вариантов расшифровки каждого из слов можно составить? Перечислите их.(2 балла)

Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т.д.) можно закодировать, используя код азбуки Морзе длиной не менее четырёх и не более пяти сигналов (точек и тире)? (2 балла)

Задача 2

Максимальное количество баллов – 5.

У исполнителя Арифметик две команды, которым присвоены номера:
1. прибавь 2,
2. умножь на 3.
Первая из них увеличивает число на экране на 2, вторая утраивает его. Например, 21211 – это программа умножь на 3 прибавь 2 умножь на 3 прибавь 2 прибавь 2, которая преобразует число 1 в число 19.
Запишите порядок команд в программе преобразования числа 3 в число 69, содержащей не более 5 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них.

Задача 3

Максимальное количество баллов – 6.

Напишите программу кодирующую слово, введенное пользователем азбукой Морзе. Между буквами слова добавьте символ "пробел".

Входные данные:
слово
Выходные данные:
слово, закодированное азбукой Морзе

Пример:
Входные данные:
школа
Выходные данные:
---- -.- --- .-.. .-

Задача 4

Максимальное количество баллов – 5.

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

Входные данные:
ширина открытки длина открытки
ширина конверта длина конверта
Выходные данные
да или нет

Пример 1:
входные данные:
2 1
1 3
выходные данные:
да

Задача 5

Максимальное количество баллов – 6.

Для того, чтобы найти максимальное из двух чисел, совсем не обязательно использовать условный алгоритм: Наибольшее из чисел a и b можно вычислить: max = (a + b) / 2 + |a - b| / 2;
Возможно ли, не используя условного алгоритма (и циклических алгоритмов), определить, делится ли число n на m?
Напишите программу, определяющую делится ли число n на m.
Входные данные
два натуральных числа n и m.
Выходные данные
1 если n делится на m нацело.
Любое другое цело число, если нет.

Задачи очного тура олимпиады ИСАУ для учащихся 11 классов

Если вы участвуете в олимпиаде дистанционно:
решение нужно прислать в pdf-файле, который может содержать отсканированное с бумажного носителя решение или решение, оформленное с помощью любого программного продукта, например, текстового редактора.
Если решением задачи является программный код, то на проверку нужно отправить непосредственно файл с кодом.

Задача 1

Максимальное количество баллов – 3.

Кто-то из студентов ИСАУ решил опробовать полученные знания по сетевой безопасности на практике и «взломал» сеть Университета. В процессе выяснения обстоятельств случившегося обозначилось, что здесь замешаны 9 человек. Все они были приглашены к директору ИСАУ Черемисиной Е.Н., где состоялся разговор:

  • Володя: «Это сделал Саша»
  • Аня: «Володя лжет!»
  • Егор: «Маша взломала!»
  • Саша: «Аня говорит неправду!»
  • Рома: «Сеть взломали либо Маша, либо Нина…»
  • Маша: «Это я взломала!»
  • Нина: «Маша не взламывала сеть!»
  • Коля: «Ни Маша, ни Нина этого не делали»
  • Олег: «Нина не взламывала сети!»
Так кто взломал сеть, если известно, что из этих девяти высказываний истинны только три?

Задача 2

Максимальное количество баллов – 7.

Рассмотрим алгоритм для шифрования слов.

Текст, который необходимо зашифровать, назовем исходной последовательностью символов.
Зашифрованный текст будет представлять собой последовательность символов такой же длины, как и исходная последовательность.
Индексация последовательностей начинается с 1.
В качестве ключа для шифрования задается числовая последовательность LMN (три различные цифры от 1 до 5).
Алгоритм шифрования состоит из следующих шагов:

  1. Находится символ, который расположен на расстоянии L символов от начала исходной последовательности. Если L больше длины исходной последовательности, то для определения требуемого индекса отсчет продолжается с начала последовательности пока не будет найден искомый символ. (Например, в последовательности «abc» при L=5 будет определен символ «b» )
    Этот символ становится последним символом последовательности зашифрованного текста и удаляется из исходной последовательности (при этом длина исходной последовательности уменьшается на 1).
  2. Также как в пункте 1 находится и переносится в зашифрованный текст символ, расположенный на расстоянии M от начала исходной последовательности.
  3. Также как в пункте 1 находится и переносится в зашифрованный текст символ, расположенный на расстоянии N от начала исходной последовательности.
  4. Пункты 1-3 повторяются до тех пор, пока исходная последовательность не станет пустой.
Используя заданный алгоритм с ключом 123 зашифруйте строку: Информатика (2 балла)

Напишите программу для шифрования текста по данному алгоритму с ключом 123. (5 балла)

Входные данные:
исходная строка

Выходные данные
Зашифрованная строка

Задача 3

Максимальное количество баллов – 9.

Известно, что текст зашифрован по алгоритму из задачи 2: С–ИУчАуйлиышвр.олбдб..уядгуепщ.фоосрснеоаила
Пробел заменяется символом "." (точка), первое слово в тексте: ИСАУ.
Какой текст зашифрован (ответ обоснуйте)? (4 балла)
Напишите программу, для расшифровки данной строки. (+ 5 баллов)

Входные данные:
нет

Выходные данные:
расшифрованная строка

Задача 4

Максимальное количество баллов – 4.

Документ объёмом 20 Мбайт можно передать с одного компьютера на другой двумя способами:
1. Сжать архиватором, передать архив по каналу связи, распаковать.
2. Передать по каналу связи без использования архиватора.

Какой способ быстрее и насколько, если:
средняя скорость передачи данных по каналу связи составляет 2^20 (2 в 20 степени) бит в секунду;
объём сжатого архиватором документа равен 20% исходного;
время, требуемое на сжатие документа, – 5 секунд, на распаковку – 1 секунда?

Задача 5

Максимальное количество баллов – 7.

В недрах нашей планеты располагаются нефтегазовые месторождения. Если в месторождении присутствует полые области, то в них скапливаются различные газы, которые испаряются из нефти. Набор различных газов полости может достигать 50 наименований и у каждого нефтегазового месторождения свой газовый набор. Это углеродные соединения (С1, С2, С3 и пр.), и азотные структуры (N2, NC5, NC4), и различные углеводородные соединения (CH4, C2H6, C3H8) и прочие.
Каждый из газов имеет определенную мольную массу. Различная масса веществ создает слоистую структуру, в которой легкие газы располагаются выше тяжелых газов. При бурении скважин, а также при других физических воздействий, вещества смешиваются в общую структуру, в которой нарушена последовательность от легких к тяжелым. Со временем структура восстанавливается, причем в самом начале распределяются самые легкие и самые тяжелые вещества. Следующим этапом распределяются менее легкие и менее тяжелые по сравнению с предыдущими. И так далее, пока общая структура не будет находится в балансе.
Напишите программу, моделирующую распределение элементов вещества на каждом этапе процесса восстановления равновесия. Самые легкие веществе расположить слева, самые тяжелые - справа.

Входные данные: количество компонентов
компонент и их мольная масса
Последовательность веществ после бурения скважин через пробел

Пример:
5
CH4 57
C20 75
C1 11
C4 2
IC4 37,5
CH4 C20 C1 C4 IC4

Выходные данные:
Поэтапное расположение веществ в процессе равновесия:
CH4 C20 C1 C4 IC4
CH4 C4 C20 C1 IC4
C4 CH4 C1 C20 IC4
C4 C1 CH4 IC4 C20
C4 C1 IC4 CH4 C20