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

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

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

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

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

Задача 1

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

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

В таблице N × M хранятся оценки студентов. Номера студентов совпадает с порядковым номером строки, номера предметов совпадают с порядковым номером столбца. Нумерация начинается с 1. В остальных ячейках таблицы хранятся оценки студентов по данным предметам.
2 3 2 3
4 5 5 5
4 4 3 5
5 5 5 5
Например, в таблице выше, у студента с порядковым номером 1 следующие оценки: 2, 3, 2, 3; а у студента с порядковым номером 3, всего одна тройка по предмету под номером 3.

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

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

В первой строке число N – количество студентов, N (1 <= N <= 100).
Во второй строке число M – количество предметов (1 <= M <= 10).
В следующих N строках по M целых чисел от 2 до 5, это оценки студентов — ячейки таблицы.

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

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

Пример:

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

4
5
2 3 2 4 2
5 4 4 4 5
4 4 5 4 2
4 2 2 4 2

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

2
1 4

Задача 2

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

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

Четыре друга, Николай, Борис, Дмитрий и Максим живут в одном дворе. Одному из них 12 лет, другому 14, третьему – 16, самому старшему – 19. Они все увлекаются программированием, но каждый из них специализируется только на каком-то одном из языков программирования: Бейсик, Паскаль, Си, Хаскел. Определите возраст и любимый язык программирования Максима, если известно, что:

  1. Специалист по Хаскелу старше любителя Си.
  2. Знаток Паскаля младше специалиста по Си.
  3. Максим старше программиста на Паскале.
  4. Любитель Бейсика родился с разницей всего в 2 года от рождения специалиста по Паскалю.
  5. Юноша, пишущий на Бейсике, либо самый старший из друзей, либо самый младший.
  6. Дима не пишет на Бейсике и его возраст более чем на пару лет отличается от возраста любителя Бейсика.
  7. Не менее чем один из приятелей родился между годом рождения Максима и годом рождения Бориса.
  8. Возраст Бориса отличается на 2 года от возраста любителя Си.
В ответе сначала цифрами запишите возраст Максима, затем, через пробел, первую букву его любимого языка программирования.

Задача 3

Решением задачи является программа, написанная на любом языке программирования (7 баллов), или правильно расшифрованная строка и описание алгоритма шифрования (2 балла).
Максимальное количество баллов – 7.

Во время Великой Отечественной войны немцы часто не могли расшифровать послания партизанских отрядов. И дело было не только в сложных шифрах, а в орфографических ошибках, которые специально допускали партизаны в зашифрованных сообщениях. Это хитрость не используется в следующем задании и если вы проследите, куда переместились первые буквы слов после шифрования строки, то сможете правильно подобрать ключ к шифру.
Подберите ключ шифра (Подсказка: строка «еще один шаг» будет зашифрована еош щда еиг *н*) и напишите программу, которая позволит прочитать любую строку, для шифрования которой был использован данный ключ, например, такую:

кмзтмотнноншооатои*ге*гб*от*оа*****е*****т*****с*****я

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

Зашифрованная строка, состоящая из букв русского алфавита, пробелов и *, длиной не более 30 символов.

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

Расшифрованная строка.

Пример:

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

еош щда еиг *н*

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

еще один шаг

Задача 4

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

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

Университет «Дубна» был основан в 1994 году. В прошлом году отметил свой 20-летний юбилей. Однако, некоторые нумерологи считают, что особо выделять числа, заканчивающиеся на 5 или 0, не совсем правильно, так как этим мы демонстрируем свою зависимость от десятичной системы счисления, которая была выбрана нами случайно, под влиянием физиологии (на руках 10 пальцев). Вместе с тем, существуют интервалы времени никак не зависящие от системы счисления. Например, простое число остается таковым независимо от системы счисления, в которой оно записано.

Назовем простым юбилеем промежуток времени, измеряемый простым числом лет. Например, у Университета «простые юбилеи» были 1995, 1996, 1997 и т. д. году (1, 2, 3 года со дня основания).

Напишите программу, которая определяет количество «простых юбилеев» Университета «Дубна» от момента основания до конца третьего тысячелетия и печатает список соответствующих дат.

Задача 5

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

Максимальное количество баллов – 10: за математическое решение – 4 балла, за программу – 4 балла, дополнительные 2 балла можно получить за программную реализацию графической модели задачи.

В острый угол, имеющий градусную меру в 15°, под углом в 30° к одной из сторон в направлении к его вершине, двигаясь с постоянной скоростью, влетает материальная точка. Считая все столкновения со стенками абсолютно упругими, определить:

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

Задача 1

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

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

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

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

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

В первой строке вводится целое число N - количество сообщений (общее количество и записей и комментариев) (1 <= N <= 1000). Следующие строки содержат описание записей и комментариев, расположенные в хронологическом порядке.
Описание записи состоит из двух строк: первая строка содержит число 0; вторая строка содержит заголовок сообщения (длина не превышает 30 символов). В описании записи нет информации о порядковом номере сообщения, 0 в первой строке обозначает, что данное сообщение это запись, а не комментарий.
Описание комментария состоит из двух строк, первая содержит целое число – номер записи, ответом на которое он является, вторая строка содержит текст самого сообщения. В описании нет информации о порядковом номере самого сообщения.

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

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

Пример:

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

5
0
ИСАУ школьникам
0
ИСАУ – это интересно!
1
В ИСАУ проходят ежегодные олимпиады для школьников по информатике
0
Новые фото на сайте!
1
ИСАУ проводит бесплатные занятия по подготовке к ЕГЭ по информатике

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

ИСАУ школьникам

Задача 2

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

Максимальное количество баллов – 6: за математическое решение – 3 балла, за программу – 3 балла).

Иван Кузьмич, участник Сталинградской битвы, приехал на парад 70-летия Победы Великой Отечественной Войны в Москву. Друг его правнука Кузьмы, Василий, решил узнать возраст знаменитого фронтовика. В ответ он услышал от своего друга: «В день капитуляции Германии число прожитых прадедом недель превысило 1024, т.е. 1 килобайт. Во время парада число прожитых им дней ещё не будет превышать 32 килобайта. День недели, в который прадед празднует ближайший юбилей, совпадает с днем недели, на который приходится Парад Победы. Вася, можешь ли ты назвать дату рождения моего прадеда, если число, образованное из чисел, соответствующих номеру дня в месяце и номеру месяца его рождения, является простым?». Вася смог, а сможешь ли ты?

Выходные данные
Дата рождения Иван Кузьмича в формате: дд.мм.гггг, например 02.02.1901

Задача 3

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

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

За 20-летнюю историю в Университете сложилось много интересных традиций: регулярно проводятся такие мероприятия, как «Посвящение в студенты», «Университетская миля», дни кафедр и это еще далеко не все. Одно из таких традиционных мероприятий — фестиваль студенческого кино «Гудвин». Одна из команд решила снять фильм «Титаник». В целях экономии было решено заменить круизный лайнер двумя лодками, общий вес компании был практически равен (на самом деле чуть меньше) тому, сколько могут выдержать 2 лодки. Однако, когда все заняли свои места, одна из лодок начала тонуть, так как общий вес пассажиров превышал норму, а вторая лодка вполне могла вместить еще кого-нибудь. К счастью, это были студенты ИСАУ, и они без труда рассчитали, как необходимо распределить пассажиров, чтобы обе лодки оставались на плаву. Для это нужно, чтобы общий вес пассажиров был практически одинаковым на каждой из лодок: выражаясь математическим языком, чтобы разность между весом пассажиров на каждой из лодок стала минимальной.

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

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

В первой строке число N – количество пассажиров (1 ≤ N ≤ 20);
Во второй строке N целых чисел, разделенных пробелами — вес каждого из пассажиров, каждое из чисел от 10 до 120.

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

Одно число — минимальную разность между весом двух групп пассажиров.

Пример:

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

5
5 8 13 27 14

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

3

Задача 4

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

Максимальное количество баллов – 8: за правильно составленный и обоснованный алгоритм – 4 балла, за программу – 4 балла.

Чтобы получить зачет по очень сложному предмету двум студентам нужно в сумме ответить на 20 вопросов. Выбор вопросов происходит так: на столе разложено 20 карточек. Каждый из студентов по очереди делает свой выбор, причем за один раз можно взять от 1 до 4 карточек.

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

Задача 5

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

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

Даже в современном мире с датами связано много самых разных суеверий. Большая часть из них легко развенчивается, если вспомнить о том, что в разные времена и в разных странах существовали (и существуют) различные системы летоисчисления. До 18 века гражданский год начинался в России с 1 марта, а религиозный – с 1 сентября. И только в 1700 году Петр I перенес дату начала года на 1 января, решив сравнять отечественное летоисчисление с европейским. Кстати в России тогда шел не 1700, а 7208 год от сотворения мира.

Можно выделить математически необычные даты. Например, первый «Миг полного числового равноденствия» во втором тысячелетии был 20 февраля 2002 года в 20 часов 2 минуты: 20.02 2002 20.02. Это мгновение можно записать в виде палиндрома – строки, которая читается одинаково как слева направо, так и справа налево.

Напишите программу, которая печатает все «миги полного числового равноденствия» в нынешнем тысячелетии и их количество.

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

Нет

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

В первой строке вывести количество таких дат.
В последующих строка сами даты, каждую дату выводить с новой строки.