Командная олимпиада по программированию

Архив задач в формате MS-WORD: Скачать [25035 байт, архив Rar].

Архив решений задач Жюри: Скачать [5235 байт, архив Rar].

Имена входных файлов ко всем задачам - INPUT.TXT.
Имена выходных файлов у всех задач - OUTPUT.TXT.
Временные ограничения ко всем задачам 10 секунд.

ЗАДАЧИ:

Задача A. Подстроки.

Подстрокой данной строки называется непустая последовательность идущих подряд символов этой строки. Например, для строки "abcdabcda" строки "a", "bcda", "abcdabcd" будут являться её подстроками, а строки "aс", "bbcda", "abcabcd" не будут. При этом одна и та же подстрока может входить в одну строчку несколько раз (т.е. несколько последовательностей из подряд идущих символов строки могут оказаться совпадающими). Например, подстрока "aa" входит в строку "aaaaa" 4 раза, а подстрока "b" в строку "ababab" - 3 раза.

Найдите самую часто встречающуюся подстроку в строке.

Формат входных данных: Во входном файле записана единственная строка длиной до 255 символов и состоящая из маленьких букв латинского алфавита.

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

Примеры:

ababab

ab

bcdebcd

bcd

b

b

Задача B. Триангуляция.

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

Формат входных данных: На первой строчке входного файла записано целое число N (1 <= N <= 100) - количество вершин многоугольника. Далее следуют N строк. На каждой из них записано по 2 целых числа - координаты вершин многоугольника. Вершины заданы в порядке обхода по часовой стрелке. Координаты многоугольника лежат в пределах от -1000 до 1000.

Формат выходных данных: Выведите число M - количество треугольников, на которые удалось разрезать данный многоугольник. Число M не должно превосходить 10000. Затем должны следовать M строк по 6 целых чисел в каждой - координаты вершин одного из треугольников, входящих в разбиение, вначале Х-координата 1-ой вершины, затем её Y-координата, затем X-координата 2-ой вершины, затем Y-координата 2-ой, затем X- и Y-координаты 3-ей. Числа разделяйте пробелами. Если решений несколько, допускается вывести любое.

Примеры:

3
0 0 0 1 1 0

1
0 0 0 1 1 0

4
0 0 0 1 1 1 1 0 

2
0 0 1 1 1 0
0 0 1 1 0 1

4
0 0 1 0 0 -1 -1 1

2
0 0 1 1 0 -1
0 0 -1 1 0 -1

Задача C. Мальчики и девочки.

Петя хочет отметить свой день рождения, но при этом не знает, кого бы ему пригласить. У Пети среди знакомых есть N мальчиков и M девочек, и он знает кто из них с кем знаком. (Конечно, если X знаком c Y, то и Y знаком с X).

Во-первых, Петя не хочет приглашать на вечеринку никого, кто не знал бы хоть кого-то из остальных приглашённых. Во-вторых, он хочет, чтобы все собравшиеся люди перезнакомились бы без его участия, то есть для любых двух людей X и Y нашлась бы такая цепочка людей A1, A2, :, An (возможно пустая), что X знает A1, A1 знает A2, A2 знает A3, :, An-1 знает An, и An знает Y. В-третьих, он хочет пригласить как можно больше народу. Кроме того, известно, что ни одна пара мальчиков не знакома друг с другом, и не одна пара девочек не знакома друг с другом тоже.

Помогите ему!!!

Формат входных данных: На первой строчке входного файла записаны целые числа N и M (1 <= M, N <= 100). Далее следует N строк по M чисел, причем в I-ой строке в J-ом столбце стоит 0, если I-ый мальчик не знаком с M-ой девочкой, и 1, если знаком.

Формат выходных данных: Выведите в первой строчке целые числа A и B - количества приглашённых мальчиков и девочек. Во второй строчке выведите A чисел - номера приглашенных мальчиков. В третьей строчке выведите B чисел - номера приглашённых девочек. Числа разделяйте пробелами. Если решений несколько, допускается вывести любое.

Примеры:

3 2
0 1
1 0
0 1

2 1
1 3
2

3 2
0 1
1 1
0 1

3 2
1 2 3
1 2

3 2
0 0
0 0
0 0

0 0

Задача D. Треугольник.

Петя занялся отлавливанием ошибок в школьном задачнике по геометрии. На это его подвигла следующая задача: "Дан треугольник с длинами медиан 3, 6 и 9. Найти длины его сторон." С чего начинается решение задачи? Правильно, с ответов. Петя заглянул в ответ и увидел: 10, 8 и 2. Какой же этот треугольник?

Как оказалось, в задачнике содержится большое количество задач (на много вариантов) вида: "Дан треугольник с длинами медиан m1, m2 и m3. Найти длины его сторон." Теперь Петя мечтает найти все такие задачи с некорректным условием.

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

Формат входных данных: Во входном файле записаны 3 целых числа от 1 до 1000 - длины медиан из текста задачи.

Формат выходных данных: Выведите YES, если треугольник с данными длинами медиан существует, и NO, если нет.

Примеры:

3 6 9 

NO

100 200 299

YES

100 200 300

NO

Задача E. Моделирование компьютера.

Представьте себе новую машину КОМП. В ней есть центральный процессор, исполняющий команды, 8192 ячеек памяти, 1 регистр общего назначения с названием Х, и флаг нуля С.

Ячейки памяти пронумерованы целыми числами от 0 до 8191. В каждой ячейке памяти, а также в регистре, может быть записано 16-битное беззнаковое целое число. Диапазон значений для таких чисел - от 0 до 2¹⁶ - 1. Флаг нуля (С) может быть установлен, либо сброшен. Также в процессоре есть 13-битовый регистр IP, который в каждый момент времени содержит номер ячейки памяти, в которой будет находиться следующая исполняемая процессором команда.

Процессор исполняет команды поочередно. Вначале процессор смотрит на адрес ячейки памяти, записанной в регистре IP. Затем он читает содержимое этой ячейки к себе во внутреннюю память и разбивает 16-битное беззнаковое число на 3 старших бита - код команды и 13 младших битов - операнд. Далее действия процессора зависят от того, что записано в старших 3-х битах ячейки, т.е. какой код команды.

В случае выполнения команд с кодами 2 - 7 устанавливается новое значение флага нуля С: если в результате выполнения арифметического действия, указанного в команде, получается 0, то флаг устанавливается, иначе он сбрасывается.

Программа, записанная в памяти компьютера КОМП, исполняется до тех пор, пока в результате какого-то бы то ни было действия не возникнет переполнения. Действия, приводящие к переполнению:

• Прибавление 1 к регистру IP, если в нём уже записано 8191.
• Сложение, если результат сложения больше 65535.
• Вычитание, если результат вычитания меньше 0.

Когда возникает переполнение, процессор печатает 2 числа: количество исполненных им с момента запуска команд, включая ту, которая привела к останову и значение регистра А. Команда, вызвавшая переполнение не ведёт ни к каким изменениям в значениях регистров или ячеек памяти.

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

Формат входных данных: Во входном файле на первой строчке записаны значения регистров А и IP в момент запуска программы. На второй строке будет записано 0, если в момент запуска флаг 0 С сброшен, и 1, если установлен. Затем на третьей и далее строчках будут записаны 8192 чисел - значения ячеек памяти в порядке их нумерации.

Формат выходных данных: Выведите 2 числа - ответ к задаче. Разделяйте числа пробелами. Гарантируется, что программа, описанная во входном файле, не будет требовать выполнения более 100000 операторов.

Примеры:

Задача F. Простая магия.

Петя нашел на дне реки старинный сосуд. "Джинн", - подумал он. Но это был не джинн. В запечатанном сосуде была одна записка. В записке говорилось, что тот, кто найдет 3030 простых чисел, обретет власть над миром. Петя принялся за дело. За первый день он проверил на простоту числа до 100, на второй день - узнал, что такое программирование, на третий - написал свою первую программу. Через месяц Петя уже написал программу, которая находит простые числа до 1020. После этого все застопорилось. Никак не удавалось Пете усовершенствовать свою программу. А тут вот что еще произошло. Найденные простые числа Петя печатал на бумаге и складывал листы в стопочку. А для надежности прижимал их сверху сосудом, найденным в реке. И оказалось, что сосуд мешает выполнению плана. На верхнем листе, прижатом сосудом, половина чисел исчезала. Увидев это, Петя даже расплакался. Ведь его последняя программа работала трое суток. И теперь, чтобы восстановить утраченные примерно 100 чисел, нужно запускать программу заново. Попробуйте помочь Пете, написав свою программу, восстанавливающую утраченные числа.

Формат входных и выходных данных: Во входном файле записаны два целых числа в диапазоне от 2 до 31 000 000 000. Второе число больше первого. Все простые числа между этими двумя нужно найти и вывести в порядке возрастания в выходной файл. Известно, что простых чисел в заданном диапазоне от 0 до 160 штук. (Если 0 - должен получиться пустой выходной файл.)

Примеры:

2 10

3
5
7

30000000000 30000000030

30000000001
30000000013

Задача G. Путь программиста.

Журнал "Труженики села", № 12, 2020 год.

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

К.: Василий Хакерович, у наших читателей есть много вопросов к Вам, но самый частый вопрос - как Вы дошли до такой жизни.

В.: Да очень просто. Шел, шел, ..., и дошел. Главное - не отступать от принципов.

К.: Каких принципов?

В.: Да всех. Во всем должны быть принципы. И от них отступать нельзя. А если принципов нет, их нужно придумать.

К.: У Вас это всегда получалось?

В.: Если мне нужно отступить от принципов, я не отступаю от них, а меняю принципы.

К.: Замечательно. Не могли бы Вы привести какой-нибудь пример из Вашей жизни, когда Вам пришлось менять принципы.

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

К.: Тяжелая это работа программиста... Василий, наших читательниц волнует вопрос, женаты ли Вы.

В.: Хороший вопрос. Нет. В наше время, когда компьютерные науки ушли далеко вперед, трудно найти женщину, простите, тетю, понимающую тебя.

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

В.: Я практик, поэтому все мои работы носят прикладной характер. Ну, могу, например, упомянуть мое эссе "Команда ИДИ_НА в различных языках программирования".

К.: Да, Вы многим известны как практик. Вы попали в Книгу Рекордов Хольстена, как обладатель рекордного числа дипломов в различных конкурсах. Расскажите, пожалуйста, о самых запомнившихся победах.

В.: Запоминаются все победы. Но расскажу я вот о какой. Лет десять назад я участвовал в конкурсе, который проводила компания Volt & Watt Ltd. После изобретения знаменитого Real Computer и создания Real Language.(RL). Кстати, кто не знает, язык RL - действительно лучший язык, а на 48-разрядном компьютере RC лучшего языка просто быть не может. На конкурс нужно было представить программу, которая наиболее полно раскрывает возможности языка RL. Ох, и сложный же был конкурс... Я писал программу целую неделю, и, хоть это была моя первая программа на языке RL, я за нее получил четыре диплома: "Experienced Senselessness Maker", "Short-Spoken Hanger", "Tough Dependable Real Typist", "A mAn that obeyS the_Principles OfCoding".

К.: Наверное, Вам наиболее дорог последний диплом?

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

К.: Например?

В.: Например, не ставить лишних пробелов, не вставлять пустых строк, смещать содержимое блока ровно на две позиции, называть программу однобуквенным именем.

К.: Очень интересно. Это - одна из Ваших многочисленных побед . А не могли бы Вы вспомнить какое-нибудь поражение?

В.: Поражений у меня не было, скорее, разочарование.

К.: Да?

В.: Да, пожалуй, самое большое разочарование связано с той же самой программой. (У меня, вообще, не много программ.) Примерно год назад я чистил свой винчестер, и он выстрелил. Шутка. Я чистил свой жесткий диск и решил зашифровать эту программу. Ну и забыл пароль.

К.: И теперь эта программа утеряна?

В.: Видимо, да. Я помню, что в пароле было 6 символов. И эту программу я просто по-xor-ил. Первый байт программы с первым байтом пароля, второй - со вторым,... шестой - с шестым, седьмой - опять с первым, и так далее.

К.: Простите мне, тетке, а что значит по-xor-ил?

В.: Применил побитовую операцию xor - "исключающее или". Если каждый нулевой бит в байте означает "UNREAL", а каждый единичный бит - "REAL", таблица этой операции выглядит так:

К.: М-да...

В.: Вот что, пользуясь случаем, я объявляю, что подарю один из своих дипломов тому, кто сможет восстановить программу. Правда, по-моему это невозможно.

К.: Ловлю Вас на слове. Итак, объявляем конкурс среди читателей журнала...

Формат входных и выходных данных: Во входном (не текстовом!) файле дана закодированная программа. Эта программа содержит строку заголовка, begin, строку с командой WriteLn с произвольным текстом и end. Раскодировать программу и вывести ее в выходной файл. (В примерах символами '$', '@' и '!' обозначены, соответственно, символы с кодами 13, 10 и 19. Переводы строки сделаны для удобства, в исходных файлах переводы строк выполняются лишь в соответствии с символами '$' и '@').

Примеры:

program A;$@
begin$@
  WriteLn('Phys-Math Lyceum # 30')$@
end.$@

program A;$@
begin$@
  WriteLn('Phys-Math Lyceum # 30')$@
end.$@

pRoGrAm A;$@
BEGIN$*  WriTeLn('phys-Math LyCeum #!0')$@
end.$@

PRoGrAM A;$@
bEGIN$@
  WriteLn('Phys-MAth Lyceum #30')$@
End.$@

Задача H. Муха.

Как хочется пить... Мысли путаются... Но надо ползти. Я уже не помню - зачем, не помню - почему, но надо ползти - вперед. Черная труба раскалилась. Лап я не чувствую уже давно, как странно, но теперь это меня даже не волнует... Только вперед. Может быть, я - последний. Это не имеет значения... Пить... Я должен доползти! Вперед... Длина трубы - X. Толщина - Y... Почему снизу нет тени? Или есть?.. Везде солнце... Я выбрал угол A - я еще жив. Я доползу. Главное не поворачивать... Почему я не пополз вдоль оси, ведь было бы короче? Нет, там нет тени... Сколько мне надо проползти? Длина - X, толщина - Y, я ползу под углом A... Как сложно посчитать... Пить... Почему она черная?.. Я ведь знал... Скоро ночь... Я успею, я должен успеть!.. Сколько же осталось?..

Формат входных и выходных данных: Во входном файле записано три числа: длина (X), толщина (Y) трубы в миллиметрах и угол (A) в градусах, под которым ползет муха. 0< X, Y <=1000000, -89<=A<=89. Вывести в выходной файл одно число - путь, пройденный мухой, если она проползла всю трубу, никуда не сворачивая, с точностью до 4 знаков после запятой.

Примеры:

1 1 0

1

100 1 45

141.4214

Задача I. Кегельбан.

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

Шар бросается в плоскости XY из начала координат вдоль оси X в положительном направлении. Считается, что кегля - вертикальная прямая. Радиус шара - 1. Расстояние между любыми двумя кеглями больше 1. При отражении шар изменяет направление на обратное симметрично относительно перпендикуляра к его поверхности в точке касания. Ваша задача определить количество различных кегель, которых коснулся шар, при этом всего касаний не более 100.

Формат входных данных: На первой строке входного файла записано количество кегель N (0 ≤ N ≤ 100). Далее на N строках через пробел записаны координаты кегель - вещественные числа x и y (-100 ≤ x, y ≤ 100).

Формат выходных данных: Выведите единственное число в выходной файл - количество разных кегель, которых коснулся шар.

Примеры:

0

0

1
3 0

1

4
4 0.5
3 2
1 -2
5 -1

2

Задача J. Раскрытие скобок.

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

Формат входных данных: В первой строчке входного файла записано выражение вида (x1+x2+...+xn)*(y1+y2+...+yk). Все переменные обозначаются маленькими буквами латинского алфавита. В каждой из сумм переменные не повторяются. Пробелы и символы табуляции во входном файле не встречаются.

Формат выходных данных: В выходной файл следует выдать сумму одночленов вида XY, 2XY или X^2. Порядок, в котором записываются сомножители и слагаемые: сначала выписываются квадраты в алфавитном порядке, затем разнобуквенные слагаемые тоже в алфавитном порядке.

Примеры:

(a+b)*(a+b)

a^2+ b^2+2ab

(s)*(s)

s^2

(a)*(z)

az

Трансляция олимпиады, монитор соревнований, а также протокол сдачи решений осуществляется на сайте Физико-математического лицея № 30: