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

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

Олимпиада по программированию для учащихся 9 — 10 классов

Олимпиада по программированию для учащихся 11 классов


Задачи для 9 - 10 класса

Задача 1

Результатом решения задачи является ответ и его обоснование.

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

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

Самые первые USB-флеш-накопители (или просто флешки) появились в 2000 году и обладали 8 Мб памяти, а стоили 50$. Как раз на такую флешку и пытался сохранить свои 5 презентаций школьник по имени Максим, однако 8 Мб памяти было недостаточно.
Все файлы презентаций имели равный размер. Каждый слайд презентации состоял из текста и одного фонового изображения (и тексты, и фоновые изображения отличаются на каждом слайде).
Изначально в презентации использовались в качестве фонов цветные изображения, кодированные с помощью 24- битной цветовой палитры. Для сокращения объема файла презентации школьник решил заменить фоновые изображения их версиями, кодированными с использованием 8-ми битной палитрой (количество точек в изображении не менялось), в результате файл с презентацией стал занимать 2048 Кбайт.
Однако и этого было не достаточно, так как презентации все еще не помещались на флешку. Тогда было решено совсем убрать фоны, в результате объем каждой презентации стал 1024 КБайт.

Каков был исходный размер файла презентации, если в ней 32 слайда? (При записи в файл с презентацией изображений не используется сжатие и не записывается никакой дополнительной информации об изображениях, кроме собственно кодов их пикселей).
И какое максимальное количество таких презентаций могло поместиться на флешку с объемом памяти 8 Мб?

В ответе укажите целое число Кбайт и количество презентаций.


Задача 2

Решением задачи является программа, написанная на любом языке программирования.

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

Первые таблицы умножения появились примерно за 2000 лет до нашей эры. Знак умножения ввёл в 1631 году Уильям Отред (Англия) в виде косого крестика. До него использовали чаще всего букву M, были и другие символы: символ прямоугольника или звёздочка. А символ точки предложил Лейбниц в конце 18 века (Хотя этот символ встречался и в работах 16 — 17 века).

А если бы умножение, так и не было изобретено? Возможно ли написать программу, которая будет вычислять площадь прямоугольника с заданными сторонами, не используя операцию умножения?

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

Длины сторон прямоугольника (от 1 до 1000), записанные через пробел.

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

Единственное число — площадь прямоугольника с заданными сторонами.

ПРИМЕР:
Выходные данные:

5 6

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

30


Задача 3

Результатом решения задачи является ответ и его обоснование.

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

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

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

Через два дня, в среду, этот же студент написал в «Вконтакте»: в понедельник я пошел в Университет, но получать повышенную стипендию не буду.

Какие из представленных ниже высказываний могут быть ложны, а какие однозначно истины и почему, если все сказанное студентом истинно (то есть, если студент пошел в Университет в дождь, то он заболел).
1. Он не сдал экзамен.
2. В понедельник шел дождь.
3. Если он пробовал сдать экзамен, то в понедельник было сухо.
4. Экзамена по математическому анализу не было.
5. Он не заболел и не сдал экзамен.


Задача 4

Решением задачи является программа, написанная на любом языке программирования.

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

29 марта 2015 года в ИСАУ день открытых дверей. Программа этого праздника обычно очень насыщенная и интересная. Именно в День открытых дверей награждаются победителей олимпиад ИСАУ для школьников. Подготовка к этому дню начинается почти за год и каждый день на счету.

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

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

Входная строка содержит два целых числа: номер месяца и номер дня в этом месяце через пробел.

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

Программа должна вывести количество дней, оставшихся до 29 марта. Если введены неверные данные, нужно вывести число -1.

ПРИМЕР 1:
Выходные данные:

3 1

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

29


ПРИМЕР 2:
Выходные данные:

2 1

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

57


Задачи для 11 класса

Задача 1

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

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

Максимальное количество баллов – 5 (не зависимо от способа решения задачи).

Двоичным счислением люди интересуются давно. Особенно им увлекались с конца XVI до начала XIX века. Лейбниц, которому принадлежит сама идея, считал двоичную систему простой, удобной и красивой. Он говорил, что «При сведении чисел к простейшим началам, каковы 0 и 1, везде появляется чудесный порядок». Однако, о системе забыли практически на 200 лет. Вернулись к ней только в 1931 году, когда были продемонстрированы некоторые возможности практического применения двоичного счисления.

Очевидно, что запись числа в двоичной системе почти всегда длиннее чем в десятичной. Определите наибольшее число, двоичное представление которого, можно записать в строчку тетради, если в одну клетку можно записать одну цифру, а клеток в строке 23.


Задача 2

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

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

Современные компьютеры могут выполнять арифметические действия с достаточно большими целыми числами (максимальное число целого типа 18446744073709551615), а всего 20 лет назад диапазон был ограничен 65536, что меньше в несколько сотен триллионов раз (10 в 14 степени раз).

Но как быть, если нужно выполнить арифметические операции над числами, разрядность которых больше 20 (т.е. число будет больше, чем 18446744073709551615)? Один из способов, это представить число в виде массива, элементы которого цифры данного числа.
Напишите программу для поиска максимального из трех чисел, состоящих из 20 разрядов.

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

Три числа, перечисленные через пробел. Разрядность каждого не более 25. Числа не равны.

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

Наибольшее из трех заданных чисел.

ПРИМЕР:
Выходные данные:

1234 12345678901234567890 123123123123123

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

12345678901234567890


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

32345678901234567890 12345678901234561111 12345678901234567890

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

32345678901234567890


Задача 3

Результатом решения задачи является ответ и его обоснование.

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

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

В ИСАУ студенты имеют возможность подрабатывать непосредственно в университете, например, в отделе обеспечения работы компьютерных классов или в центре дистанционного обучения.
Студент второго курса устроился в отдел обеспечения работы компьютерных классов и получил свое первое самостоятельное задание: установить на новый компьютер драйвера от периферийных устройств. Друзья, конечно, дали ему много бесценных советов.
Причем, половина каждого совета была правильной, а другая половина ложь. Вот эти советы:

- Первым можно установить только сканер, а внешний жесткий диск – предпоследним.
- Никогда не ставь третьим принтер, не нужно ставить последней музыкальную клавиатуру.
- Монитор устанавливай обязательно вторым, а четвертым – внешний жесткий диск.
- Монитор необходимо устанавливать вторым, а сканер только третьим.
- Музыкальную клавиатуру можно поставить пятой, а первым – принтер.

Смогли бы вы разобраться в таких советах и восстановить точную последовательность установки драйверов? В ответе укажите подряд первые буквы устройств в том порядке, в котором необходимо устанавливать для них драйвера, а также логическое обоснование полученного ответа.
( В – внешний жесткий диск, К – музыкальная клавиатура, М – монитор, П – принтер, С – сканер).


Задача 4

Решением задачи является программа, написанная на любом языке программирования.

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

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

Университет «Дубна» образован 27 сентября 1994 года, в прошлом году был двадцатилетний юбилей. Обычно заседание Института САУ назначается на пятницу и проходит в деловой и конструктивной обстановке, несмотря на то, что некоторые из них (пятница 13 число) в народе называют «черными».
Сколько черных пятниц прошло с момента образования Университета «Дубна» по сегодняшний день (1 марта 2015 года)?

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

нет

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

количество "черных пятниц".