Во время юбилейной воронежской олимпиады организаторы решили сводить участников на экскурсию в музей олимпиадного движения. Педагогический опыт организаторов подсказал им, что для сохранения порядка участников решили строить парами. Но дело в том, что некоторые участники не хотят идти друг с другом. Это привело к тому, что мероприятие сорвалось. Для решения этой проблемы представитель спонсора опросил всех участников и узнал, кто с кем не хочет идти.
Итак, у организаторов есть список участников, и для каждого участника — список тех, с кем он не хочет быть в паре. Необходимо посчитать максимальное количество пар, которые можно создать. Оценив сложность задачи, председатель оргкомитета решил привлечь программиста. А что делать с другими участниками, он будет решать в индивидуальном порядке.
Первая строка входного файла содержит целое число N — количество участников (1£ N £ 100). В следующих N строках описываются антипатии участников. Участники нумеруются от 1 до N, и каждому участнику соответствует одна строка в следующем формате. Первое число в (i+1)-й строке — целое число Mi — количество участников в списке антипатий i-того участника, а затем заданы Mi чисел — номера этих участников. Предполагается, что антипатии взаимны. Все числа в строках разделяются пробелами.
В выходной файл необходимо вывести одно целое число — максимальное число пар.
Входной файл: input.txt | Выходной файл: output.txt |
4 1 4 1 4 1 4 3 1 2 3 | 1 |
Натуральное число назовем внутренне возрастающим, если цифры этого числа оказываются упорядоченными по неубыванию при просмотре разрядов в порядке от старших к младшим. Таковыми, например, являются числа 111, 123, 15, 1123. Оргкомитет Воронежской олимпиады решил, что для создания оптимистического настроения у участников все числа в задачах и в итоговых протоколах должны быть «внутренне возрастающими».
Для того, чтобы проверить, выполнимо ли решение Оргкомитета, Вам требуется посчитать количество «внутренне возрастающих» чисел в диапазоне [10, N], где N — заданное натуральное число.
Входной файл содержит одно натуральное число N (10 < N < 109).
В выходном файле должно содержаться единственное натуральное число – количество «внутренне возрастающих» чисел в диапазоне [10, N].
Входной файл: input.txt | Выходной файл: output.txt |
11 | 1 |
100 | 45 |
20 | 9 |
В связи со случаями нахождения задач финального тура в интернете через GPRS организаторы олимпиады решили, что на территории Воронежского ГУ будет установлена система мобильной связи, основанная на самостоятельно разработанных протоколах. Аппараты для этой системы будет поставлять новый спонсор Воронежской олимпиады – китайская компания Dypa (Digital Yellow Phone Automatics). Сотрудничество решили начать с разработки нового протокола сжатия для факсов. Перед представителями Оргкомитета встала задача улучшить коэффициент сжатия.
После некоторых раздумий было решено попробовать такой вариант: страница разбивается на строки и каждая строка сжимается отдельно. Сжатая строка представляется в виде набора из точек Pi (1£i£n) и отрезков Lj(1£j£m). Для того чтобы восстановить изображение, нужно вычислить симметрическую разность всех отрезков и точек. То есть строка S будет отрисовываться по следующему правилу:
S = L1 + L2 + ... + Ln + P1 + P2 + ... +Pm,
где операция ‘+ ‘ — это симметрическая разность, которая определяется следующим образом
A+B = (AÈB)\(AÇB).
Другими словами, на белую строку последовательно накладываются черные отрезки и точки. При наложении отрезка на строку точки, попавшие под отрезок, инвертируются. То же самое происходит при наложении одной точки на строку.
Учитывая, что основным принципом китайского партнёра является «экономия на всём», Ваша задача - определить минимальный объем памяти, необходимый для хранения строки длиной до 2048 точек, при условии, что для хранения одного отрезка требуется 23 бита, а для точки —12 бит.
В первой строке входного файла записано одно целое число N — количество чёрных точек (0 < N £ 2048) в исходном изображении. В следующих N строках файла приводятся позиции чёрных точек по одной на строке в строго возрастающем порядке. Номера позиций могут начинаться с нуля и не превосходят 2047.
В выходной файл нужно выдать одно целое число — количество бит в сжатом представлении изображения.
Входной файл: input.txt | Выходной файл: output.txt |
1 99 | 12 |
2 0 2047 | 24 |
6 1 2 4 5 7 8 | 47 |
Другой спонсор Воронежской олимпиады, игровая компания «Бяка» представила новую игру «Frog Quest». В одном из эпизодов Лягушка (ну, почти царевна) увидела, куда попала стрела, пущенная Иваном-Царевичем. А попала она на островок, и добраться до этого островка лягушка может только лишь, прыгая по кочкам. Кочки расположены на прямой и имеют целочисленные координаты xi (i = 0, ... , N). Лягушка делает один прыжок в секунду. Она прыгает только вперед. Длина ее прыжка по сравнению с предыдущим может увеличиваться не более чем на Amax. В начальный момент времени (t = 0) она находится на кочке с координатой x0 = 0 и имеет нулевую скорость. За конечное время претендентка на царский трон должна попасть точно на островок с координатой xN (конечная скорость значения не имеет). При этом лягушка должна успеть подобрать стрелу до появления Ивана-Царевича (ну, чтобы он ее в жены взял). Время его прихода ей известно.
Для того, чтобы иметь ускорение Amax = 1, лягушке необходимо проглотить одного волшебного комара, Amax = 2 – соответственно, двух комаров и т.д. Ее задача состоит в том, чтобы, потратив как можно меньше волшебных комаров (их запас у нее весьма скромный), добраться до стрелы за время, не большее заданной величины T.
В первой строке входного файла записаны через пробел два числа N и Т (0 £ N£ 60 , 0 < T £ 200). В последующих N строках записаны упорядоченные по возрастанию целые числа — координаты кочек x1, x2, …, xN (1£ xi £ 109, 1£ i £ N).
В выходной файл нужно вывести одно число – минимально возможное значение ускорения Amax.
Входной файл: input.txt | Выходной файл: output.txt |
10 3 1 2 3 4 7 8 9 11 14 18 | 3 |
При разработке системы автоматизации судейства для воронежской олимпиады было поставлено следующее техническое задание: порядок участника в итоговом списке определяется его результатом, который представляет собой положительное целое число, не превосходящее 32000. Результат участника не зависит от количества решённых им задач и определяется председателем жюри — для этого он просто делает drag'n'drop имени участника в соответствующую точку списка. Ваша задача состоит в том, чтобы написать функцию, вызываемую из обработчика drag'n'drop. Эта функция изменяет результаты указанного участника и, возможно, каких-то еще участников так, чтобы выполнялись следующие условия:
- указанный участник должен встать на указанное место в списке, отсортированном по результатам;
- при этом можно изменить результаты некоторых других участников;
- количество участников, результаты которых изменяются, должно быть минимизировано;
- результат участника (как указанного, так и любого другого) не должен становиться меньше 1 или больше 32000;
- результаты участников должны быть уникальны.
Каждая строка входного файла, кроме последней, задает результат и имя одного участника. Результат представляет собой целое число в диапазоне от 1 до 32000, имя — произвольную строку длиной не более 255 символов. Результаты, показанные участниками, попарно различны. Имена участников уникальны. Количество участников не превосходит 255.
Последняя строка входного файла имеет тот же формат, но смысл ее иной: число означает требуемый порядковый номер участника в итоговом протоколе, а строка — его имя. Этого участника необходимо поместить на указанное место в сортированном списке, изменив результаты минимального числа участников. Требуемый порядковый номер участника не превосходит количества всех участников. Возможны две ситуации:
1. Участник с таким именем присутствует в списке — тогда его нужно переместить на указанное место (сравнение заголовков производится побайтово, с учетом регистра букв и всех пробелов.
2. Участник с таким именем отсутствует — в этом случае его нужно добавить в указанное место. Отметим, что количество старых участников не превосходит 254.
В выходной файл записывается одно целое число — минимальное количество участников, результаты которых необходимо изменить.
Входной файл: input.txt | Выходной файл: output.txt |
20 Воронежский Гений Гениевич (ВГУ) 21 Иванов Иван (ВГУ) 22 Петричев Дмитрий (МГУ) 25 DCRush (СарГУ) 3 Сам Лам Мер(ВГУ) | 1 |
Объяснение: результирующий список должен выглядеть так:
20 Воронежский Гений Гениевич (ВГУ)
21 Иванов Иван (ВГУ)
22 Сам Лам Мер (ВГУ)
23 Петричев Дмитрий (МГУ)
25 DCRush (СарГУ)
При создании системы автоматизации поиска ошибок в задачах воронежской олимпиады (модуль автоматической проверки правильных решений от участников) программисты столкнулись со следующей проблемой. Многие программы при своем исполнении занимают процессор не все время, а иногда исполнение прерывают и освобождают процессор на время работы с иными устройствами компьютера. Пока уже исполняемые программы освобождают процессор на время работы с иными устройствами компьютера, возможно параллельное исполнение других программ. Порядок запуска программ не имеет значения. Но программы не должны ждать освобождения процессора, когда он им станет опять необходим.
Разумным казалось просто выполнять задачи последовательно. Однако в этом случае работа системы оказывается совсем не эффективной, так как очень часто возможно параллельное исполнение программ. Вам предлагается разобраться с ситуацией, когда необходимо выполнить всего две такие задачи, причем затратив на их выполнение наименьшее время. Временем выполнения набора задач называется количество тактов, прошедших с момента начала исполнения первой запущенной задачи и до момента конца исполнения всего множества задач.
Во входном файле описываются требования двух задач к расписанию их исполнения. В первой строке заданы два натуральных числа: 1£ N1, N2 £ 100 – количество раз, которые первая и вторая задача соответственно работают с процессором.
Затем заданы натуральные числа 0 < ai £ 109, i = 1, ... , 2*N1–1, соответствующие требованиям первой задачи. А именно, при запуске первой задачи сначала ей требуется a1 тактов работы процессора, потом она ровно на a2 тактов процессор освобождает, возвращается для работы с процессором на a3 тактов, освобождает его на a4 и так далее. Затем во входном файле заданы натуральные числа 0 < bi £ 109, i = 1, ..., 2*N2 – 1, соответствующие аналогичным требованиям второй задачи
В выходном файле должно содержаться единственное натуральное число – минимальное возможное время выполнения заданных двух задач.
Ограничения
Известно, что время выполнения любой из этих задач при отсутствии других составило бы не более 109 тактов процессора.
Входной файл: input.txt | Выходной файл: output.txt |
2 1 10 30 10 40 | 90 |
2 1 10 30 10 30 | 50 |
3 3 10 10 10 10 10 10 10 10 10 10 | 60 |