7866.png
ЧЕЛЯБИНСК,ЮУРГУ,ИЕТН

Назад

images/home.png Начало
images/balloon.gif Соревнования
2009

Подразделы

Другие разделы

Дата и время

16/11/2024 15:19:01

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЗадачи очного тура олимпиады для школьников Информатика-2009

1. Мумия

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Недавно египетские археологи обнаружили неизвестную до сих пор пирамиду (см. план пирамиды на рис.). В вершине пирамиды находится одна комната, которая соединена коридорами с тремя комнатами, расположенными на уровень ниже. Каждая из этих комнат, в свою очередь, также соединяется с тремя комнатами более нижнего уровня и так вплоть до основания пирамиды.
В день окончания раскопок в пирамиде был найден древний папирус. В папирусе говорилось, что на пирамиду наложено проклятие мумии фараона: "Мумия вернется и покарает тех, кто раскопал пирамиду! Мумия возникнет в вершине пирамиды, и будет идти по коридорам к ее основанию. Вот путь мумии: …". Далее следовала строка, составленная из букв (в переводе с древнеегипетского на латинский) L, M и R. Буква L означает, что мумия пойдет в комнату уровнем ниже по левому коридору, буква R – по правому коридору, а буква M – по среднему коридору. После этого в папирусе говорилось: "Откопавший пирамиду может снять проклятие, если засыплет песком в точности ту комнату в основании пирамиды, из которой может выйти мумия."
Напишите программу, которая по заданному пути мумии определяет порядковый номер комнаты, в которой появится мумия (нумерация комнат начинается с единицы).
Формат ввода
Непустая строка, состоящая из символов L, M и R. Длина строки не превосходит 15.
Формат вывода
Вывести одно целое число — порядковый номер комнаты (нумерация комнат начинается с единицы).

Пример ввода 1

RR

Пример вывода 1

1

Пример ввода 2

RLM

Пример вывода 2

8

2. Головоломка

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Необходимо найти `N` неотрицательных целых чисел, которые можно расставить по кругу так, чтобы
  • сумма чисел была минимальна
  • сумма соседних чисел была не менее `S`: `(a_i\ +\ a_{(i\ mod\ N)+1})\ ≥\ S`
  • разность соседних чисел была не менее `D`: `|a_i\ -\ a_{(i\ mod\ N)+1}|\ ≥\ D`
Формат ввода
В первой строке ввода содержатся три целых числа — `N` (`2\ ≤\ N\ ≤\ 100`), `S` и `D` (`0\ <\ S,\ D\ ≤\ 100`).
Формат вывода
Вывести решение головоломки — `N` неотрицательных целых чисел в порядке расстановки. Если существует несколько вариантов решений с минимальной суммой, то можно вывести любой вариант.

Пример ввода

4 11 5

Пример вывода

3 8 3 8

3. 3 таракана

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

На трех различных ребрах прямоугольного параллелепипеда, имеющих общую вершину, сидят три таракана. В некоторый момент времени тараканы направились с произвольной скоростью, каждый по своему ребру, к месту встречи — общей вершине ребер. Может ли получиться так, что попарные расстояния между тараканами будут приблизительно равны трём заданным числам?
Формат ввода
В первой строке ввода содержатся три вещественных неотрицательных числа от 1 до 100 — расстояния от тараканов до места встречи. Во второй строке содержатся три вещественных числа от 1 до 100 — попарные расстояния между тараканами в произвольном порядке.
Формат вывода
Вывести три вещественных числа — расстояния для каждого из тараканов до места встречи в момент, когда попарные расстояния между тараканами будут отличаться от трех заданных чисел не более, чем на `10^{-5}`. Если существует несколько вариантов решений, то можно вывести любой вариант. Если получение заданных попарных расстояний невозможно, вывести одно число `-1`.

Пример ввода

5.0 10.0 2.5
3.5355339 3.5355339 3.5355339

Пример вывода

2.500000 2.500000 2.500000

4. NOT

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Логические выражения, содержащие отрицания, трудны для понимания, поэтому программисты, особенно начинающие, должны их избегать. Напишите программу, которая выполняет рефакторинг логического выражения на языке Паскаль, преобразуя его к виду, не содержащему операции NOT, используя правила де Моргана, удаление двойного отрицания и замену операций отношения на инверсные.
Логическое выражение в этой задаче имеет следующий синтаксис:
выр ::= выр1 | выр4
выр1 ::= выр2 | выр1 «OR» выр2
выр2 ::= выр3 | выр2 «AND» выр3
выр3 ::= «(» выр «)» | «NOT» выр3
выр4 ::= идент «=» идент | идент «<>» идент | идент «>» идент | идент «<» идент | идент «>=» идент | идент «<=» идент
идент ::= «A» | «B» | … | «Z»
Для удаления отрицания используются следующие правила:
NOT(A OR B) `→` NOT(A) AND NOT(B)
NOT(A AND B) `→` NOT(A) OR NOT(B)
NOT(NOT A) `→` A
NOT(A<B) `→` A>=B
NOT(A>B) `→` A<=B
NOT(A<=B) `→` A>B
NOT(A>=B) `→` A<B
NOT(A=B) `→` A<>B
NOT(A<>B) `→` A=B
Формат ввода
В первой строке ввода логическое выражение, соответствующее указанному синтаксису. Между лексемами могут быть пробелы. Длина строки не превышает 200 символов. Строчные буквы в записи выражений не используются.
Формат вывода
Вывести логическое выражение после удаления отрицаний. Других преобразований в логическом выражении кроме вышеуказанных делать нельзя. Скобки должны использоваться только там, где они необходимы для указания порядка выполнения операций. Самый низкий приоритет в языке Паскаль у операций сравнения, выше у операции OR, еще выше у операции AND. Пробелы в выходном логическом выражении должны отсутствовать.

Пример ввода

NOT((A>=B) OR (C<X) AND (D<>X))

Пример вывода

(A<B)AND((C>=X)OR(D=X))
loading