Окружная олимпиада(18 задач)
Региональный этап(109 задач)
Заключительный этап(97 задач)
На контрольной работе N учеников сидят в ряд. Для каждого ученика известно, какую оценку он получил бы, если бы писал эту контрольную самостоятельно (оценка — это число от 2 до 5). Однако ученики могут писать контрольную не только самостоятельно, но и списывать у своего соседа, но только если сосед пишет контрольную самостоятельно. В этом случае списывающий получит такую же оценку, какую получит тот, у кого он списал.
А именно (правила применяются строго в указанном порядке):
Определите, кто какую оценку в итоге получит.
Вводится число N (1<=N<=10) - количество учеников, и далее последовательность из N чисел, описывающая, кто на какую оценку может написать контрольную, если будет писать самостоятельно.
Выведите N чисел - оценки, которые получат ученики за контрольную.
1. Первый и пятый ученики будут писать самостоятельно. Второй спишет у первого, а четвертый — у пятого (в итоге также получат пятерки). Третьему не у кого списывать, так как его соседи будут писать работу не самостоятельно.
2. Второй и четвертый спишут у третьего, пятый — у шестого.
5 5 2 3 4 5
5 5 3 5 5
6 2 2 3 2 2 4
2 3 3 3 4 4
Рассмотрим последовательности чисел. Первая последовательность состоит из одного числа K. Каждая следующая последовательность чисел описывает предыдущую по такому правилу.
Просматриваем описываемую последовательность слева направо и разбиваем на отрезки, состоящие из подряд идущих равных чисел (причем все идущие подряд одинаковые числа всегда объединяем в один отрезок). Далее каждый такой отрезок описываем двумя числами — первое число говорит, сколько раз повторяется одно и то же число, второе число говорит, какое именно число повторяется. Записываем эти пары последовательно в соответствии с отрезками слева направо, и получаем новую последовательность (см. примеры ниже).
Например, для K=2 последовательности получатся такими:
№ | Последовательность | Как ее читать (слова в описании соответствуют числам текущей последовательности слева направо, и описывают предыдущую последовательность) |
1 | 2 | Исходная последовательность |
2 | 1 2 | Одна «двойка» |
3 | 1 1 1 2 | Одна «единица», одна «двойка» |
4 | 3 1 1 2 | Три «единицы», одна «двойка» |
5 | 1 3 2 1 1 2 | Одна «тройка», две «единицы», одна «двойка» |
6 | 1 1 1 3 1 2 2 1 1 2 | Одна «единица», одна «тройка», одна «двойка», две «единицы», одна «двойка» |
Напишите программу, которая по исходному числу K напечатает N-ую получающуюся последовательность.
Вводится число K (1 ≤ K ≤ 9) и число N (1 ≤ N ≤ 15).
Ваша программа должна печатать N-ую последовательность, полученную из начальной последовательности, состоящей из одного числа K. Числа при выводе следует разделять пробелами.
2 6
1 1 1 3 1 2 2 1 1 2
2 1
2
1 3
2 1
Про три числа (обозначенных a, b, c) известны все результаты сравнения их друг с другом. Требуется расположить эти числа в порядке возрастания.
Вводятся три строки. В первой записан результат сравнения между собой чисел a и b в следующем формате. Первый символ — всегда a, третий символ — b (соответствующие маленькие латинские буквы), а между ними записан один из символов >, < или =. Во второй строке в таком же формате записан результат сравнения a и с (первый символ всегда a, третий — c), а в третьей строке — результат сравнения b и c (первый символ всегда b, третий — c). Гарантируется, что входные данные не противоречивы.
Выведите символы a, b, c в порядке величины соответствующих им чисел — каждое следующее число должно быть больше либо равно предыдущему. Если два числа равны между собой, соответствующие переменные могут быть выведены в любом порядке. Символы должны быть выведены в одной строке без пробелов и других разделителей.
Во втором примере ответ cba также является верным. Обратите внимание, если вариантов ответа несколько — не нужно выводить их все, ваша программа должна вывести ровно один вариант ответа.
a>b a>c b>c
cba
a=b a>c b>c
cab cba
Компания Macrohard выпустила в свет новую версию операционной системы «Frames» («Рамки») и теперь стремится внедрить ее на рынок информационных технологий. Каждая фирма, заказывающая новую версию «Рамок», получает лицензионные ключи от компании Macrohard по следующим правилам:
Операционной системой заинтересовался один влиятельный человек, пожелавший установить ее на свой персональный компьютер. Вам, как работнику отдела лицензирования Macrohard, поручено сгенерировать новый ключ, который не только не повторяется с выданными ранее ключами, но и обладает новой (не используемой ранее) контрольной суммой. Требуется написать программу, которая решает эту задачу.
В первой строке входного файла содержится два натуральных числа N и P (1 ≤ N ≤ 30000, 1 ≤ P ≤ 1000), где N – число уже использованных ключей, P – число, используемое для подсчета контрольной суммы. В следующих N строках следуют ключи, которые задаются в виде
XXXXX-XXXXX-XXXXX-XXXXX-XXXXX, где X – значащий символ (цифра или буква латинского алфавита).
В выходной файл требуется вывести новый уникальный ключ в соответствии с указанным форматом, обладающий уникальной контрольной суммой. В случае, если такой ключ сгенерировать невозможно, выведите слово «Impossible».
Ввод | Вывод |
|
|
|
|
|
|
Во Флатландии с некоторых пор процветают феодальные отношения – у каждого порядочного феодала есть ровно два вассала, у непорядочных – вассалов нет совсем. Каждый феодал строит свой замок в городе на прямой, при этом:
Для удобства замки феодалов занумерованы натуральными числами по порядку слева направо, начиная с единицы, и разбиты на улицы. Улица (i, j) представляет собой последовательность подряд идущих замков, начиная с замка под номером i и заканчивая замком с номером j (i ≤ j)
Однажды в город приехал новый феодал и пожелал выкупить там замок у одного из жителей. Также ему стало интересно узнать социальный статус соседей по улице, однако, город к тому времени так разросся, что феодал уже не мог сделать этого самостоятельно. Напишите программу, которая поможет ему!
Первая строка входного файла содержит число N (1 ≤ N ≤ 30000) — высота замка единственного главного феодала в городе, который никому не подчиняется. Далее, в следующих двух строках идут числа i и j (\(0 \leq i, j < 10^{10000}\)), задающие улицу (i, j), на которой хочет приобрести замок новый феодал (гарантируется, что замки с номерами i и j находятся в черте города, i ≤ j, j – i ≤ 105).
В выходной файл требуется вывести высоты всех замков на указанной улице слева направо через пробел.
Будут оцениваться и частичные решения задачи при малых N. Частичные решения для N<20 набирают до 40 баллов, а для N<50 набирают не более 70 баллов.
Ввод | Вывод |
|
|
|
|
|
|