23 и 26 марта онлайн, на платформе IT.Mail.Ru совместно с Codeforces, прошли два отборочных раунда олимпиады по программированию «Технокубок-2016» для учащихся 8–11-х классов. Больше полутора тысяч участников со всей России и СНГ боролись за возможность встретиться на московской площадке. 300 лучших прошли в финал, который состоится 17 апреля в МГТУ им. Н. Э. Баумана и МФТИ.
В апреле им представится возможность вновь проявить себя и побороться за привлекательные призы: iPad mini 2, iPod nano, iPod shuffle. Помимо приземлённых материальных наград, а также непременного почёта и уважения, победители первого Технокубка (диплом I степени) получат целых восемь дополнительных баллов при поступлении на программы бакалавриата и специалитета в МФТИ и МГТУ им. Н. Э. Баумана, а призёры (диплом II и III степени) — шесть дополнительных баллов. Ребята уже сейчас смогут познакомиться с ведущими IT-специалистами, а в дальнейшем, возможно, решат совмещать обучение в одном из лучших технических вузов Москвы с дополнительными образовательными программами Технопарка и Технотрека.
Для участников этого года и тех, кто хотел бы подготовиться к будущим Технокубкам, представляем разбор задач.
Профиль горного хребта схематично задан в виде прямоугольной таблицы из символов «.» (пустое пространство) и «*» (часть горы). Каждый столбец таблицы содержит хотя бы одну «звёздочку». Гарантируется, что либо любой из символов «*» находится в нижней строке матрицы, либо непосредственно под ним находится другой символ «*».
Пример изображения горного хребта
Маршрут туриста проходит через весь горный хребет слева направо. Каждый день турист перемещается вправо — в соседний столбец в схематичном изображении. Конечно, каждый раз он поднимается в самую верхнюю точку горы (или опускается), которая находится в соответствующем столбце.
Считая, что изначально турист находится в самой верхней точке в первом столбце, а закончит свой маршрут в самой верхней точке в последнем столбце, найдите две величины:
Решение. Для решения данной задачи насчитаем высоту каждой горы и сохраним её в массиве h[], где h[j] равно высоте j-й горы. Для этого обойдём заданную матрицу, и, если элемент, стоящий в строке i и в столбце j (строки и столбцы 0-индексированы), равен звёздочке, обновим высоту j-й горы: h[j]?=?max(h[j],?n?–?i). Осталось просто проитерироваться по столбцам от 0 до m – 2 включительно и, если текущий столбец равен j, обновить величину максимального подъёма или максимального спуска величиной |h[j?+?1]?–?h[j]|.
Вася купил стол, у которого n ножек. Каждая ножка состоит из двух частей, которые соединяются друг с другом. Каждая часть может быть произвольной положительной длины, но гарантируется, что из всех 2n частей возможно составить n ножек одинаковой длины. При составлении ножки любые две части могут быть соединены друг с другом. Изначально все ножки стола разобраны, а вам заданы длины 2n частей в произвольном порядке.
Помогите Васе собрать все ножки стола так, чтобы все они были одинаковой длины, разбив заданные 2n части на пары правильным образом. Каждая ножка обязательно должна быть составлена ровно из двух частей, не разрешается использовать как ножку только одну часть.
Решение. Для решения данной задачи сначала посчитаем длину одной собранной ножки стола и сохраним её в переменную len (len?=?sum/n, где sum — это суммарная длина всех частей, а n — количество ножек стола). Сохраним длины всех частей ножек в массив a[] и отсортируем его по возрастанию. Затем переберём части ножек переменной i от 0 до n?–?1 включительно и будем выводить в ответ пары вида (a[i],?len?–?a[i]).
Вам задано прямоугольное клетчатое поле, состоящее из n строк и m столбцов. Поле содержит цикл из символов «*», такой, что:
Ниже изображены несколько примеров допустимых циклов:
Все клетки поля, отличные от цикла, содержат символ «.». Цикл на поле ровно один. Посещать клетки, отличные от цикла, Роботу нельзя.
В одной из клеток цикла находится Робот. Эта клетка помечена символом «S». Найдите последовательность команд для Робота, чтобы обойти цикл. Каждая из четырёх возможных команд кодируется буквой и обозначает перемещение Робота на одну клетку:
Робот должен обойти цикл, побывав в каждой его клетке ровно один раз (кроме стартовой точки — в ней он начинает и заканчивает свой путь).
Найдите искомую последовательность команд, допускается любое направление обхода цикла.
Решение. Сначала найдём стартовую позицию Робота, сохраним её и присвоим значение стартовой позиции звёздочке. Так как по условию задана ломаная без самопересечений и самокасаний, верен следующий алгоритм: если есть соседняя с текущей клетка, в которой стоит звёздочка, перейдём в соседнюю клетку, значение которой равно звёздочке, и присвоим её значение точке (при этом выведем букву, соответствующую направлению, в котором мы перешли). При этом соседняя клетка должна быть отлична от той, из которой мы пришли в текущую клетку. Если нет соседней клетки с звёздочкой, значит, мы обошли всю ломаную и нужно закончить работу программы.
На координатной прямой сидит n собачек, i-я собачка находится в точке xi. Кроме того, на прямой есть m мисок с едой, для каждой известна её координата на прямой uj и время tj, через которое еда в миске остынет и станет невкусной. Это значит, что если собачка прибежит к миске в момент времени, строго больший tj, то еда уже остынет и собачка кушать её не станет.
Считая, что каждая собачка бежит со скоростью 1, найдите максимальное количество собачек, которые смогут покушать. Считайте, что собачки побегут к тем мискам, на которые вы им укажете. Из одной миски не могут кушать две или более собачки.
Собачки могут обгонять друг друга, то есть, если одна из них остановится покушать, другая может пройти мимо неё, чтобы попасть к другой миске.
Решение. Если представить каждую миску в виде отрезка [uj?–?tj,?uj?+?tj], то i-я собачка сможет поесть из j миски, если uj?–?tj ? xi ? uj?+?tj.
Будем решать задачу жадно. Рассмотрим самую левую собачку и те миски, из которых она может поесть. Если таких мисок нет, то собачка не сможет покушать. В противном случае из мисок, доступных самой левой собачке, выберем для неё миску с самым левым правым концом. Далее не будем рассматривать эту собачку и эту миску и продолжим аналогично наши рассуждения.
Легко видеть, что такая жадность приводит к оптимальному ответу:
По этой задаче можно было попробовать написать другие жадности, но многие будут неправильными.
Для того чтобы это реализовать, отсортируем собачек и миски (по левому концу) слева направо. Будем идти слева направо, обрабатывая события «появилась миска» (в этом случае добавим её правый конец в какую-нибудь структуру данных) и «появилась собачка» (нужно для собачки в структуре данных найти самый левый подходящий правый конец).
Сложность: O(nlogn) или O(n) в зависимости от структуры данных (*set* или queue).
Решение на С++
Дано целое неотрицательное число k и n неотрицательных целых чисел a1,?a2,?...,?an. Записывая некоторые из этих чисел друг за другом в произвольном порядке и, возможно, используя какие-то из них несколько раз (а какие-то вообще не используя), требуется составить кратчайшее (наименьшее по количеству цифр) число, делящееся на k, или определить, что это невозможно.
Решение. Заметим, что при построении ответа нам в любой момент важен только лишь остаток от деления текущего его префикса на k. Действительно, если текущий префикс ответа имеет остаток от деления на k, равный r, то при приписывании к префиксу числа ai этот остаток станет равным остатку от деления на k числа r • 10li?+?ai (li — количество цифр в записи числа ai).
Тогда, очевидно, нас интересует получать любой остаток от деления такой операцией, используя минимальное количество цифр в записи. Конечно, остаток 0 мы можем получить сразу, используя пустой префикс, поэтому для остатка 0 нас будет интересовать второй по величине ответ.
Всё описанное выше позволяет нам построить граф на k вершинах (от 0 до k?–?1, соответственно остаткам), рёбра в котором определяются числами ai: из вершины v в вершину
длины li, означающее, что с помощью дописывания li цифр мы можем из префикса с остатком v получить префикс с остатком u. Легко заметить, что некоторые ai в этом графе будут соответствовать одним и тем же рёбрам (сейчас их nk) — это числа с одинаковой длиной десятичной записи и остатком от деления на k, поэтому стоит оставить лишь уникальные по такому критерию числа (их будет не больше 10k), и тогда количество рёбер не будет превышать 10k2.
Теперь всё, что от нас требуется, — найти длину кратчайшего непустого пути из вершины 0 в саму себя же в построенном графе. Чтобы избежать столь неприятной цикличности, давайте просто добавим дополнительную вершину k, имеющую те же исходящие рёбра, что и вершина 0, считая, что такой остаток может иметь лишь пустой префикс. Теперь задача сводится к нахождению кратчайшего пути из вершины k в вершину 0, что можно решить алгоритмом Дейкстры за O(k2). Однако, в силу специфичности задачи, решение алгоритмом Форда — Беллмана (с правильными отсечениями, конечно) также проходит все тесты, хоть в теории и имеет столь большие O(k3).
Восстановление ответа в задаче довольно стандартно, за исключением хранения дополнительного числа для каждой вершины, образовавшего ребро, по которому был осуществлён нужный в кратчайшем ответе переход.
Решение алгоритмом Дейкстры
Поликарп мечтает стать программистом и фанатеет от степеней двойки. Среди двух чисел ему больше нравится то, которое делится на бoльшую степень числа 2.
По заданной последовательности целых положительных чисел a1,?a2,?...,?an требуется найти r — максимальную степень числа 2, на которую делится хотя бы одно из чисел последовательности. Кроме того, требуется вывести количество чисел ai, которые делятся на r.
Решение. Для решения данной задачи нужно воспользоваться фактом, что степени двойки быстро растут и максимальная степень двойки, на которую может делиться число, не превосходящее 109, равна 29. Поэтому нужно просто проитерироваться по заданным числам, найти максимальную степень двойки, на которую делится текущее число, и обновить ответ этой максимальной степенью.
Есть n-подъездный дом, в каждом подъезде по m этажей, и на каждом этаже каждого подъезда ровно k квартир. Таким образом, в доме всего n • m • k квартир. Они пронумерованы естественным образом от 1 до n • m • k, то есть первая квартира на первом этаже в первом подъезде имеет номер 1, первая квартира на втором этаже первого подъезда имеет номер k?+?1 и так далее. Особенность этого дома состоит в том, что он круглый. То есть если обходить его по часовой стрелке, то после подъезда номер 1 следует подъезд номер 2, затем подъезд номер 3 и так далее до подъезда номер n. После подъезда номер n снова идёт подъезд номер 1.
Эдвард живёт в квартире номер a, а Наташа — в квартире номер b. Переход на один этаж вверх или вниз по лестнице занимает 5 секунд, переход от двери подъезда к двери соседнего подъезда — 15 секунд, а переход в пределах одного этажа одного подъезда происходит мгновенно. Также в каждом подъезде дома есть лифт. Он устроен следующим образом: он всегда приезжает ровно через 10 секунд после вызова, а чтобы переместить пассажира на один этаж вверх или вниз, лифт тратит ровно одну секунду. Посадка и высадка происходят мгновенно.
Помогите Эдварду найти минимальное время, за которое он сможет добраться до квартиры Наташи. Считайте, что Эдвард может выйти из подъезда только с первого этажа соответствующего подъезда (это происходит мгновенно). Если Эдвард стоит перед дверью какого-то подъезда, он может зайти в него и сразу окажется на первом этаже этого подъезда (это также происходит мгновенно). Эдвард может выбирать, в каком направлении идти вокруг дома.
Решение. Для решения данной задачи нужно было аккуратно реализовать то, что написано в условии. Основная сложность заключалась в определении номера подъезда и номера этажа по номеру квартиры. Это можно было сделать следующим образом: если в доме n подъездов, в каждом подъезде по m этажей, а на каждом этаже по k квартир, то квартира с номером a находится в подъезде номер (a?–?1)?/?(m?•?k) и на этаже номер ((a?–?1)%(m?•?k))?/?k, причём эти номера 0-индексированы, что удобно для дальнейших вычислений. После определения номеров подъездов и этажей нужно было рассмотреть два случая: когда номера подъездов Эдварда и Наташи равны (тогда нужно было выбрать, что оптимальнее — доехать на лифте или подняться/спуститься по лестнице) и когда эти номера различны (тут нужно было не забыть, что дом круглый, и выбрать нужное направление).
На тренировку по подготовке к соревнованиям по программированию пришли n команд. Тренер для каждой команды подобрал тренировку, комплект задач для i-й команды занимает ai страниц. В распоряжении тренера есть x листов бумаги, у которых обе стороны чистые, и y листов, у которых только одна сторона чистая. При печати условия на листе первого типа можно напечатать две страницы из условий задач, а при печати на листе второго типа — только одну. Конечно, на листе нельзя печатать условия из двух разных комплектов задач. Обратите внимание, что при использовании листов, у которых обе стороны чистые, не обязательно печатать условие на обеих сторонах, одна из них может остаться чистой.
Вам предстоит определить максимальное количество команд, которым тренер сможет напечатать комплекты задач целиком.
Решение. Сначала отсортируем заданные размеры комплектов задач в неубывающем порядке. Затем нужно начать перебирать комплекты задач, начиная с наименьшего. Если мы не можем напечатать текущий комплект, то никакой следующий комплект мы гарантированно не сможем напечатать, поэтому нужно вывести ответ и закончить алгоритм. В противном случае нужно напечатать текущий комплект, увеличить ответ на единицу и перейти к следующему комплекту. Каждый комплект оптимально печатать следующим образом. Пусть x — это оставшееся количество двусторонних листов, y — оставшееся количество односторонних листов, а a — это количество страниц в текущем комплекте задач. Если x?=?0 и y?=?0, то напечатать текущий комплект мы точно не сможем. Если a нечётно и y?>?0, напечатаем одну страницу на одностороннем листе и уменьшим a и y на единицу, иначе, если a нечётно и x?>?0, напечатаем одну страницу на двустороннем листе (который больше использовать не будем) и уменьшим a и x на единицу. Теперь a — это всегда чётное число. Поэтому выгодно сначала по максимуму использовать для печати двусторонние листы, а если их не хватает — односторонние. Если и односторонних листов не хватает, то текущий комплект распечатать мы не сможем.
Память компьютера состоит из n ячеек, которые выстроены в ряд. Пронумеруем ячейки от 1 до n слева направо. Про каждую ячейку известно, свободна она или принадлежит какому-либо процессу (в таком случае известен процесс, которому она принадлежит).
Для каждого процесса известно, что принадлежащие ему ячейки занимают в памяти непрерывный участок. С помощью операций вида «переписать данные из занятой ячейки в свободную, а занятую теперь считать свободной» требуется расположить все принадлежащие процессам ячейки в начале памяти компьютера. Другими словами, любая свободная ячейка должна располагаться правее (иметь больший номер) любой занятой.
Вам необходимо найти минимальное количество операций переписывания данных из одной ячейки в другую, с помощью которых можно достичь описанных условий. Допустимо, что относительный порядок ячеек в памяти для каждого из процессов изменится после дефрагментации, но относительный порядок самих процессов должен остаться без изменений. Это значит, что если все ячейки, принадлежащие процессу i, находились в памяти раньше всех ячеек процесса j, то и после перемещений это условие должно выполняться.
Считайте, что номера всех процессов уникальны, хотя бы одна ячейка памяти занята каким-либо процессом.
Решение. Для решения данной задачи нужно сформировать массив, который будет равен памяти компьютера после дефрагментации. Для этого, например, можно запомнить про каждый процесс (в порядке слева направо) количество ячеек, которые он занимает. Верно следующее утверждение: пока дефрагментация не закончена, всегда будет две такие ячейки с номерами pos1 и pos2 в памяти компьютера, что ячейка pos1 пуста, а ячейка pos2 занята процессом, который по окончании дефрагментации должен находиться в ячейке номер pos1. Таким образом, ответ на задачу — это количество таких ячеек в памяти, которые должны быть заняты каким-то процессом после окончания дефрагментации, причём до начала дефрагментации либо эти ячейки пусты, либо в них записаны другие процессы (отличные от тех, которые должны быть записаны после дефрагментации).
Вдоль дороги стоят n путешественников. Дорога представляет собой прямую, размерами путешественников можно пренебречь, считая их точками.
Водитель автобуса Василий, благодаря мобильному приложению, знает для каждого путешественника точку xi, в которой тот стоит. Кроме того, он знает расстояние di, которое i-й путешественник хочет проехать на автобусе. Таким образом, i-й путешественник планирует выйти из автобуса в точке xi?+?di. Теперь Василий хочет выбрать, кого из путешественников он подвезёт, а кого оставит пылиться у дороги.
Василий решил, что сегодня он должен хорошо заработать, поэтому нужно перевезти в точности a путешественников. В автопарке есть автобусы любых видов. Чем больше мест в автобусе, тем дороже стоит его аренда.
Помогите Василию определить минимальное количество пассажирских мест в автобусе, которых будет достаточно для перевозки ровно a путешественников. Ни в какой момент времени в автобусе не может быть путешественников больше, чем количество пассажирских мест в автобусе. Василий сам может решить, какое конкретно подмножество из a путешественников он перевезёт на автобусе.
Считайте, что автобус всегда едет слева направо (от меньших координат к большим) и начинает свой путь левее самого левостоящего путешественника. Если в одной точке какой-то путешественник должен выйти из автобуса, а другой войти, считайте, что сначала произойдёт выход одного путешественника из автобуса, а затем другой путешественник сможет зайти в автобус.
Решение. Изначально отсортируем всех путешественников по их начальным позициям в неубывающем порядке, а при равенстве позиций — отсортируем по дистанциям, которые путешественникам нужно преодолеть, также в неубывающем порядке. Затем необходимо бинарным поиском подобрать минимальное количество мест в автобусе, которых будет достаточно для перевозки a путешественников.
Целевая функция бинарного поиска должна работать следующим образом. Пусть mid — количество мест в автобусе. Тогда найдём cnt — максимальное количество путешественников, которых мы сможем подвезти на таком автобусе. Это можно сделать с помощью set’a, в котором мы будем хранить позиции выходов путешественников, которые зашли в автобус, и их индексы.
Переберём всех путешественников слева направо (в том порядке, в котором они были отсортированы). Пока в set’е есть путешественники, которые выйдут из автобуса не позднее момента, когда зайдёт текущий путешественник, удалим позиции их выходов из set и добавим их индексы в отдельный вектор ans. В противном случае, если самая дальняя позиция выхода путешественника в set’е больше, чем потенциальная позиция выхода текущего путешественника, заменим в set’е самого дальневыходящего путешественника на текущего.
После того как мы переберём всех путешественников, добавим индексы всех оставшихся в set’е путешественников в ans. Если размер вектора ans меньше a, сдвинем в mid левую границу бинарного поиска, иначе сдвинем в mid правую границу бинарного поиска. После бинарного поиска запустим ещё раз целевую функцию от ответа и выведем индексы путешественников из вектора ans.
В первом отборочном раунде приняло участие 929 человек. Лучший результат показал Владислав Макеев (Москва, Россия). Второе и третье место заняли Ростислав Величко (Ставрополь, Россия) и Роман Горбунов (Москва, Россия).
Второй отборочный раунд собрал 686 человек. С большим отрывом первое место в рейтинговой таблице занял Влад Мосько (Гомель, Белоруссия). Второе и третье место — Назарбек Алтыбай (Актобе, Казахстан) и Владимир Романов (Москва, Россия).
Мы ещё раз поздравляем всех финалистов и ждём новых участников в следующем году.
В апреле им представится возможность вновь проявить себя и побороться за привлекательные призы: iPad mini 2, iPod nano, iPod shuffle. Помимо приземлённых материальных наград, а также непременного почёта и уважения, победители первого Технокубка (диплом I степени) получат целых восемь дополнительных баллов при поступлении на программы бакалавриата и специалитета в МФТИ и МГТУ им. Н. Э. Баумана, а призёры (диплом II и III степени) — шесть дополнительных баллов. Ребята уже сейчас смогут познакомиться с ведущими IT-специалистами, а в дальнейшем, возможно, решат совмещать обучение в одном из лучших технических вузов Москвы с дополнительными образовательными программами Технопарка и Технотрека.
«Технокубок — важная социальная инициатива: благодаря олимпиаде талантливые юные программисты получат дополнительную возможность поступить в ведущие технические вузы страны. Мы планомерно работаем над тем, чтобы дать студентам и школьникам как можно больше возможностей набрать знания и практику, необходимые для работы в крупной компании или для того, чтобы начать разрабатывать собственный проект. На это ориентированы наши образовательные проекты с вузами (Технопарк, Техносфера и Технотрек), наши IT-чемпионаты, а теперь этот список пополнит и Технокубок», — Дмитрий Dmitry21 Волошин, директор департамента исследований и образования Mail.Ru Group.
Для участников этого года и тех, кто хотел бы подготовиться к будущим Технокубкам, представляем разбор задач.
A. Наибольший подъём
Профиль горного хребта схематично задан в виде прямоугольной таблицы из символов «.» (пустое пространство) и «*» (часть горы). Каждый столбец таблицы содержит хотя бы одну «звёздочку». Гарантируется, что либо любой из символов «*» находится в нижней строке матрицы, либо непосредственно под ним находится другой символ «*».
...........
.........*.
.*.......*.
**.......*.
**..*...**.
***********
Пример изображения горного хребта
Маршрут туриста проходит через весь горный хребет слева направо. Каждый день турист перемещается вправо — в соседний столбец в схематичном изображении. Конечно, каждый раз он поднимается в самую верхнюю точку горы (или опускается), которая находится в соответствующем столбце.
Считая, что изначально турист находится в самой верхней точке в первом столбце, а закончит свой маршрут в самой верхней точке в последнем столбце, найдите две величины:
- наибольший подъём за день (равен 0, если в профиле горного хребта нет ни одного подъёма),
- наибольший спуск за день (равен 0, если в профиле горного хребта нет ни одного спуска).
Решение. Для решения данной задачи насчитаем высоту каждой горы и сохраним её в массиве h[], где h[j] равно высоте j-й горы. Для этого обойдём заданную матрицу, и, если элемент, стоящий в строке i и в столбце j (строки и столбцы 0-индексированы), равен звёздочке, обновим высоту j-й горы: h[j]?=?max(h[j],?n?–?i). Осталось просто проитерироваться по столбцам от 0 до m – 2 включительно и, если текущий столбец равен j, обновить величину максимального подъёма или максимального спуска величиной |h[j?+?1]?–?h[j]|.
Пример решения
int n, m;
int h[N];
char c;
void solve() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> c;
if (c == '*') {
h[j] = max(h[j], n - i);
}
}
}
int maxU = 0, maxD = 0;
for (int i = 0; i < m - 1; i++) {
int diff = h[i + 1] - h[i];
if (diff > 0) {
maxU = max(maxU, diff);
} else {
maxD = max(maxD, -diff);
}
}
cout << maxU << ' ' << maxD << endl;
}
B. Собери стол
Вася купил стол, у которого n ножек. Каждая ножка состоит из двух частей, которые соединяются друг с другом. Каждая часть может быть произвольной положительной длины, но гарантируется, что из всех 2n частей возможно составить n ножек одинаковой длины. При составлении ножки любые две части могут быть соединены друг с другом. Изначально все ножки стола разобраны, а вам заданы длины 2n частей в произвольном порядке.
Помогите Васе собрать все ножки стола так, чтобы все они были одинаковой длины, разбив заданные 2n части на пары правильным образом. Каждая ножка обязательно должна быть составлена ровно из двух частей, не разрешается использовать как ножку только одну часть.
Решение. Для решения данной задачи сначала посчитаем длину одной собранной ножки стола и сохраним её в переменную len (len?=?sum/n, где sum — это суммарная длина всех частей, а n — количество ножек стола). Сохраним длины всех частей ножек в массив a[] и отсортируем его по возрастанию. Затем переберём части ножек переменной i от 0 до n?–?1 включительно и будем выводить в ответ пары вида (a[i],?len?–?a[i]).
Пример решения
int n, len, sum;
int a[N];
int main() {
cin >> n;
for (int i = 0; i < 2 * n; i++) {
cin >> a[i];
sum += a[i];
}
len = sum / n;
sort(a, a + 2 * n);
for (int i = 0; i < n; i++) {
cout << a[i] << ' ' << len - a[i] << endl;
}
}
C. Путь Робота
Вам задано прямоугольное клетчатое поле, состоящее из n строк и m столбцов. Поле содержит цикл из символов «*», такой, что:
- цикл можно обойти, посетив каждую его клетку ровно один раз, перемещаясь каждый раз вверх/вниз/вправо/влево на одну клетку;
- цикл не содержит самопересечений и самокасаний, то есть две клетки цикла соседствуют по стороне тогда и только тогда, когда они соседние при перемещении вдоль цикла (самокасание по углу тоже запрещено).
Ниже изображены несколько примеров допустимых циклов:
Все клетки поля, отличные от цикла, содержат символ «.». Цикл на поле ровно один. Посещать клетки, отличные от цикла, Роботу нельзя.
В одной из клеток цикла находится Робот. Эта клетка помечена символом «S». Найдите последовательность команд для Робота, чтобы обойти цикл. Каждая из четырёх возможных команд кодируется буквой и обозначает перемещение Робота на одну клетку:
- «U» — сдвинуться на клетку вверх,
- «R» — сдвинуться на клетку вправо,
- «D» — сдвинуться на клетку вниз,
- «L» — сдвинуться на клетку влево.
Робот должен обойти цикл, побывав в каждой его клетке ровно один раз (кроме стартовой точки — в ней он начинает и заканчивает свой путь).
Найдите искомую последовательность команд, допускается любое направление обхода цикла.
Решение. Сначала найдём стартовую позицию Робота, сохраним её и присвоим значение стартовой позиции звёздочке. Так как по условию задана ломаная без самопересечений и самокасаний, верен следующий алгоритм: если есть соседняя с текущей клетка, в которой стоит звёздочка, перейдём в соседнюю клетку, значение которой равно звёздочке, и присвоим её значение точке (при этом выведем букву, соответствующую направлению, в котором мы перешли). При этом соседняя клетка должна быть отлична от той, из которой мы пришли в текущую клетку. Если нет соседней клетки с звёздочкой, значит, мы обошли всю ломаную и нужно закончить работу программы.
Пример решения
int n, m, sx, sy;
char a[N][N];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
char dir[] = {'U', 'D', 'L', 'R'};
void solve()
{
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
{
cin >> a[i][j];
if (a[i][j] == 'S') {
sx = i, sy = j;
}
}
}
a[sx][sy] = '*';
int px = -1, py = -1;
while (true) {
bool wasMove = false;
for (int i = 0; i < 4; i++) {
int nx = sx + dx[i];
int ny = sy + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
continue;
}
if (a[nx][ny] != '*') {
continue;
}
if (nx == px && ny == py) {
continue;
}
a[nx][ny] = '.';
px = sx, py = sy;
sx = nx, sy = ny;
cout << dir[i];
wasMove = true;
break;
}
if(wasMove) {
break;
}
}
puts("");
}
D. Собачки и миски
На координатной прямой сидит n собачек, i-я собачка находится в точке xi. Кроме того, на прямой есть m мисок с едой, для каждой известна её координата на прямой uj и время tj, через которое еда в миске остынет и станет невкусной. Это значит, что если собачка прибежит к миске в момент времени, строго больший tj, то еда уже остынет и собачка кушать её не станет.
Считая, что каждая собачка бежит со скоростью 1, найдите максимальное количество собачек, которые смогут покушать. Считайте, что собачки побегут к тем мискам, на которые вы им укажете. Из одной миски не могут кушать две или более собачки.
Собачки могут обгонять друг друга, то есть, если одна из них остановится покушать, другая может пройти мимо неё, чтобы попасть к другой миске.
Решение. Если представить каждую миску в виде отрезка [uj?–?tj,?uj?+?tj], то i-я собачка сможет поесть из j миски, если uj?–?tj ? xi ? uj?+?tj.
Будем решать задачу жадно. Рассмотрим самую левую собачку и те миски, из которых она может поесть. Если таких мисок нет, то собачка не сможет покушать. В противном случае из мисок, доступных самой левой собачке, выберем для неё миску с самым левым правым концом. Далее не будем рассматривать эту собачку и эту миску и продолжим аналогично наши рассуждения.
Легко видеть, что такая жадность приводит к оптимальному ответу:
- Если самая левая собачка может поесть, то нет смысла ей не есть, поскольку этим мы убираем одну миску и ухудшим ответ на единицу.
- Рассмотрим те миски, из которых может поесть самая левая собачка. Все эти миски будут доступны и остальным собачкам, кроме тех, у которых правая граница находится слишком далеко влево. Таким образом, если мы хотим взять какую-либо миску (а мы уже поняли из пункта 1, что это стоит сделать), то выгоднее будет взять миску с самым левым правым концом, так мы не ухудшим выбор для собачек справа.
По этой задаче можно было попробовать написать другие жадности, но многие будут неправильными.
Для того чтобы это реализовать, отсортируем собачек и миски (по левому концу) слева направо. Будем идти слева направо, обрабатывая события «появилась миска» (в этом случае добавим её правый конец в какую-нибудь структуру данных) и «появилась собачка» (нужно для собачки в структуре данных найти самый левый подходящий правый конец).
Сложность: O(nlogn) или O(n) в зависимости от структуры данных (*set* или queue).
Решение на С++
Пример решения
const int N = 200200;
int n, m;
int x[N];
int u[N], t[N];
bool read() {
if (!(cin >> n >> m)) return false;
forn(i, n) assert(scanf("%d", &x[i]) == 1);
forn(i, m) assert(scanf("%d%d", &u[i], &t[i]) == 2);
return true;
}
pti segs[N];
void solve() {
forn(i, m) segs[i] = mp(u[i] - t[i], u[i] + t[i]);
sort(x, x + n);
sort(segs, segs + m);
int ans = 0;
multiset<int> z;
for (int i = 0, j = 0; i < n; ) {
if (j < m && segs[j].x <= x[i]) {
z.insert(segs[j].y);
j++;
} else {
auto it = z.lower_bound(x[i]);
i++;
if (it != z.end()) {
ans++;
z.erase(it);
}
}
}
cout << ans << endl;
}
E. Собери число
Дано целое неотрицательное число k и n неотрицательных целых чисел a1,?a2,?...,?an. Записывая некоторые из этих чисел друг за другом в произвольном порядке и, возможно, используя какие-то из них несколько раз (а какие-то вообще не используя), требуется составить кратчайшее (наименьшее по количеству цифр) число, делящееся на k, или определить, что это невозможно.
Решение. Заметим, что при построении ответа нам в любой момент важен только лишь остаток от деления текущего его префикса на k. Действительно, если текущий префикс ответа имеет остаток от деления на k, равный r, то при приписывании к префиксу числа ai этот остаток станет равным остатку от деления на k числа r • 10li?+?ai (li — количество цифр в записи числа ai).
Тогда, очевидно, нас интересует получать любой остаток от деления такой операцией, используя минимальное количество цифр в записи. Конечно, остаток 0 мы можем получить сразу, используя пустой префикс, поэтому для остатка 0 нас будет интересовать второй по величине ответ.
Всё описанное выше позволяет нам построить граф на k вершинах (от 0 до k?–?1, соответственно остаткам), рёбра в котором определяются числами ai: из вершины v в вершину
длины li, означающее, что с помощью дописывания li цифр мы можем из префикса с остатком v получить префикс с остатком u. Легко заметить, что некоторые ai в этом графе будут соответствовать одним и тем же рёбрам (сейчас их nk) — это числа с одинаковой длиной десятичной записи и остатком от деления на k, поэтому стоит оставить лишь уникальные по такому критерию числа (их будет не больше 10k), и тогда количество рёбер не будет превышать 10k2.Теперь всё, что от нас требуется, — найти длину кратчайшего непустого пути из вершины 0 в саму себя же в построенном графе. Чтобы избежать столь неприятной цикличности, давайте просто добавим дополнительную вершину k, имеющую те же исходящие рёбра, что и вершина 0, считая, что такой остаток может иметь лишь пустой префикс. Теперь задача сводится к нахождению кратчайшего пути из вершины k в вершину 0, что можно решить алгоритмом Дейкстры за O(k2). Однако, в силу специфичности задачи, решение алгоритмом Форда — Беллмана (с правильными отсечениями, конечно) также проходит все тесты, хоть в теории и имеет столь большие O(k3).
Восстановление ответа в задаче довольно стандартно, за исключением хранения дополнительного числа для каждой вершины, образовавшего ребро, по которому был осуществлён нужный в кратчайшем ответе переход.
Решение алгоритмом Дейкстры
Пример решения
for (int i = 0; i < n; ++i) {
int x;
assert(scanf("%d", &x) == 1);
any[x % k][length(x)] = x;
}
p10[0] = 1;
for (int i = 0; i + 1 < P; ++i)
p10[i + 1] = (p10[i] * 10) % k;
for (int i = 0; i <= k; ++i) {
d[i] = int(1e9);
p[i] = -1;
used[i] = false;
}
d[k] = 0;
while (true) {
int v = -1;
for (int i = 0; i <= k; ++i)
if (!used[i] && (v == -1 || d[v] > d[i]))
v = i;
if (v == -1)
break;
if (v == 0)
break;
used[v] = true;
for (int r = 0; r < k; ++r)
for (int l = 0; l < P; ++l)
if (any[r][l] != -1) {
int to = (v * p10[l] + r) % k;
if (d[to] > d[v] + l) {
d[to] = d[v] + l;
p[to] = v;
w[to] = any[r][l];
used[to] = false;
}
}
}
if (p[0] == -1) {
puts("NO");
} else {
puts("YES");
vector <int> res;
int v = 0;
do {
res.push_back(w[v]);
v = p[v];
} while (v != k);
reverse(res.begin(), res.end());
for (auto x: res)
printf("%d", x);
}
A. Любимые числа Поликарпа
Поликарп мечтает стать программистом и фанатеет от степеней двойки. Среди двух чисел ему больше нравится то, которое делится на бoльшую степень числа 2.
По заданной последовательности целых положительных чисел a1,?a2,?...,?an требуется найти r — максимальную степень числа 2, на которую делится хотя бы одно из чисел последовательности. Кроме того, требуется вывести количество чисел ai, которые делятся на r.
Решение. Для решения данной задачи нужно воспользоваться фактом, что степени двойки быстро растут и максимальная степень двойки, на которую может делиться число, не превосходящее 109, равна 29. Поэтому нужно просто проитерироваться по заданным числам, найти максимальную степень двойки, на которую делится текущее число, и обновить ответ этой максимальной степенью.
Пример решения
int n, x;
int main() {
cin >> n;
int ans = -1, cnt = 0;
for (int i = 0; i < n; i++) {
cin >> x;
int cur = 1, power = 0;
while (true) {
cur *= 2;
if (x % cur) break;
power++;
}
if (ans < power) {
ans = power;
cnt = 1;
} else if (ans == power) {
cnt++;
}
}
cout << ans << ' ' << cnt << endl;
}
B. Этажи
Есть n-подъездный дом, в каждом подъезде по m этажей, и на каждом этаже каждого подъезда ровно k квартир. Таким образом, в доме всего n • m • k квартир. Они пронумерованы естественным образом от 1 до n • m • k, то есть первая квартира на первом этаже в первом подъезде имеет номер 1, первая квартира на втором этаже первого подъезда имеет номер k?+?1 и так далее. Особенность этого дома состоит в том, что он круглый. То есть если обходить его по часовой стрелке, то после подъезда номер 1 следует подъезд номер 2, затем подъезд номер 3 и так далее до подъезда номер n. После подъезда номер n снова идёт подъезд номер 1.
Эдвард живёт в квартире номер a, а Наташа — в квартире номер b. Переход на один этаж вверх или вниз по лестнице занимает 5 секунд, переход от двери подъезда к двери соседнего подъезда — 15 секунд, а переход в пределах одного этажа одного подъезда происходит мгновенно. Также в каждом подъезде дома есть лифт. Он устроен следующим образом: он всегда приезжает ровно через 10 секунд после вызова, а чтобы переместить пассажира на один этаж вверх или вниз, лифт тратит ровно одну секунду. Посадка и высадка происходят мгновенно.
Помогите Эдварду найти минимальное время, за которое он сможет добраться до квартиры Наташи. Считайте, что Эдвард может выйти из подъезда только с первого этажа соответствующего подъезда (это происходит мгновенно). Если Эдвард стоит перед дверью какого-то подъезда, он может зайти в него и сразу окажется на первом этаже этого подъезда (это также происходит мгновенно). Эдвард может выбирать, в каком направлении идти вокруг дома.
Решение. Для решения данной задачи нужно было аккуратно реализовать то, что написано в условии. Основная сложность заключалась в определении номера подъезда и номера этажа по номеру квартиры. Это можно было сделать следующим образом: если в доме n подъездов, в каждом подъезде по m этажей, а на каждом этаже по k квартир, то квартира с номером a находится в подъезде номер (a?–?1)?/?(m?•?k) и на этаже номер ((a?–?1)%(m?•?k))?/?k, причём эти номера 0-индексированы, что удобно для дальнейших вычислений. После определения номеров подъездов и этажей нужно было рассмотреть два случая: когда номера подъездов Эдварда и Наташи равны (тогда нужно было выбрать, что оптимальнее — доехать на лифте или подняться/спуститься по лестнице) и когда эти номера различны (тут нужно было не забыть, что дом круглый, и выбрать нужное направление).
Пример решения
int n, m, k, a, b;
int main() {
cin >> n >> m >> k >> a >> b;
a--, b--;
int p1 = a / (m * k), p2 = b / (m * k);
int f1 = (a % (m * k)) / k, f2 = (b % (m * k)) / k;
if (p1 == p2) {
cout << min(abs(f1 - f2) + 10, abs(f1 - f2) * 5) << endl;
} else {
if(p1 > p2) swap(p1, p2);
cout << min((p2 - p1) * 15, (p1 + n - p2) * 15) + min(f1 * 5, 10 + f1) + min(f2 * 5, 10 + f2) << endl;
}
}
C. Печать условий
На тренировку по подготовке к соревнованиям по программированию пришли n команд. Тренер для каждой команды подобрал тренировку, комплект задач для i-й команды занимает ai страниц. В распоряжении тренера есть x листов бумаги, у которых обе стороны чистые, и y листов, у которых только одна сторона чистая. При печати условия на листе первого типа можно напечатать две страницы из условий задач, а при печати на листе второго типа — только одну. Конечно, на листе нельзя печатать условия из двух разных комплектов задач. Обратите внимание, что при использовании листов, у которых обе стороны чистые, не обязательно печатать условие на обеих сторонах, одна из них может остаться чистой.
Вам предстоит определить максимальное количество команд, которым тренер сможет напечатать комплекты задач целиком.
Решение. Сначала отсортируем заданные размеры комплектов задач в неубывающем порядке. Затем нужно начать перебирать комплекты задач, начиная с наименьшего. Если мы не можем напечатать текущий комплект, то никакой следующий комплект мы гарантированно не сможем напечатать, поэтому нужно вывести ответ и закончить алгоритм. В противном случае нужно напечатать текущий комплект, увеличить ответ на единицу и перейти к следующему комплекту. Каждый комплект оптимально печатать следующим образом. Пусть x — это оставшееся количество двусторонних листов, y — оставшееся количество односторонних листов, а a — это количество страниц в текущем комплекте задач. Если x?=?0 и y?=?0, то напечатать текущий комплект мы точно не сможем. Если a нечётно и y?>?0, напечатаем одну страницу на одностороннем листе и уменьшим a и y на единицу, иначе, если a нечётно и x?>?0, напечатаем одну страницу на двустороннем листе (который больше использовать не будем) и уменьшим a и x на единицу. Теперь a — это всегда чётное число. Поэтому выгодно сначала по максимуму использовать для печати двусторонние листы, а если их не хватает — односторонние. Если и односторонних листов не хватает, то текущий комплект распечатать мы не сможем.
Пример решения
int n, x, y;
int a[N];
bool can(int a)
{
if (a % 2) {
if (y > 0) a--, y--;
else if (x > 0) a--, x--;
else return false;
}
if (x * 2 >= a) {
x -= a / 2;
return true;
}
a -= 2 * x, x = 0;
if (y >= a) {
y -= a;
return true;
}
return false;
}
int main() {
cin >> n >> x >> y;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
int ans = 0;
for (int i = 0; i < n; i++)
if(can(a[i])) ans++;
else break;
cout << ans << endl;
}
D. Дефрагментация памяти
Память компьютера состоит из n ячеек, которые выстроены в ряд. Пронумеруем ячейки от 1 до n слева направо. Про каждую ячейку известно, свободна она или принадлежит какому-либо процессу (в таком случае известен процесс, которому она принадлежит).
Для каждого процесса известно, что принадлежащие ему ячейки занимают в памяти непрерывный участок. С помощью операций вида «переписать данные из занятой ячейки в свободную, а занятую теперь считать свободной» требуется расположить все принадлежащие процессам ячейки в начале памяти компьютера. Другими словами, любая свободная ячейка должна располагаться правее (иметь больший номер) любой занятой.
Вам необходимо найти минимальное количество операций переписывания данных из одной ячейки в другую, с помощью которых можно достичь описанных условий. Допустимо, что относительный порядок ячеек в памяти для каждого из процессов изменится после дефрагментации, но относительный порядок самих процессов должен остаться без изменений. Это значит, что если все ячейки, принадлежащие процессу i, находились в памяти раньше всех ячеек процесса j, то и после перемещений это условие должно выполняться.
Считайте, что номера всех процессов уникальны, хотя бы одна ячейка памяти занята каким-либо процессом.
Решение. Для решения данной задачи нужно сформировать массив, который будет равен памяти компьютера после дефрагментации. Для этого, например, можно запомнить про каждый процесс (в порядке слева направо) количество ячеек, которые он занимает. Верно следующее утверждение: пока дефрагментация не закончена, всегда будет две такие ячейки с номерами pos1 и pos2 в памяти компьютера, что ячейка pos1 пуста, а ячейка pos2 занята процессом, который по окончании дефрагментации должен находиться в ячейке номер pos1. Таким образом, ответ на задачу — это количество таких ячеек в памяти, которые должны быть заняты каким-то процессом после окончания дефрагментации, причём до начала дефрагментации либо эти ячейки пусты, либо в них записаны другие процессы (отличные от тех, которые должны быть записаны после дефрагментации).
Пример решения
int n;
int a[N], need[N];
int szneed;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
if (a[i] != 0) need[szneed++] = a[i];
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (need[i] != 0 && need[i] != a[i]) ans++;
}
cout << ans << endl;
}
E. Автобус
Вдоль дороги стоят n путешественников. Дорога представляет собой прямую, размерами путешественников можно пренебречь, считая их точками.
Водитель автобуса Василий, благодаря мобильному приложению, знает для каждого путешественника точку xi, в которой тот стоит. Кроме того, он знает расстояние di, которое i-й путешественник хочет проехать на автобусе. Таким образом, i-й путешественник планирует выйти из автобуса в точке xi?+?di. Теперь Василий хочет выбрать, кого из путешественников он подвезёт, а кого оставит пылиться у дороги.
Василий решил, что сегодня он должен хорошо заработать, поэтому нужно перевезти в точности a путешественников. В автопарке есть автобусы любых видов. Чем больше мест в автобусе, тем дороже стоит его аренда.
Помогите Василию определить минимальное количество пассажирских мест в автобусе, которых будет достаточно для перевозки ровно a путешественников. Ни в какой момент времени в автобусе не может быть путешественников больше, чем количество пассажирских мест в автобусе. Василий сам может решить, какое конкретно подмножество из a путешественников он перевезёт на автобусе.
Считайте, что автобус всегда едет слева направо (от меньших координат к большим) и начинает свой путь левее самого левостоящего путешественника. Если в одной точке какой-то путешественник должен выйти из автобуса, а другой войти, считайте, что сначала произойдёт выход одного путешественника из автобуса, а затем другой путешественник сможет зайти в автобус.
Решение. Изначально отсортируем всех путешественников по их начальным позициям в неубывающем порядке, а при равенстве позиций — отсортируем по дистанциям, которые путешественникам нужно преодолеть, также в неубывающем порядке. Затем необходимо бинарным поиском подобрать минимальное количество мест в автобусе, которых будет достаточно для перевозки a путешественников.
Целевая функция бинарного поиска должна работать следующим образом. Пусть mid — количество мест в автобусе. Тогда найдём cnt — максимальное количество путешественников, которых мы сможем подвезти на таком автобусе. Это можно сделать с помощью set’a, в котором мы будем хранить позиции выходов путешественников, которые зашли в автобус, и их индексы.
Переберём всех путешественников слева направо (в том порядке, в котором они были отсортированы). Пока в set’е есть путешественники, которые выйдут из автобуса не позднее момента, когда зайдёт текущий путешественник, удалим позиции их выходов из set и добавим их индексы в отдельный вектор ans. В противном случае, если самая дальняя позиция выхода путешественника в set’е больше, чем потенциальная позиция выхода текущего путешественника, заменим в set’е самого дальневыходящего путешественника на текущего.
После того как мы переберём всех путешественников, добавим индексы всех оставшихся в set’е путешественников в ans. Если размер вектора ans меньше a, сдвинем в mid левую границу бинарного поиска, иначе сдвинем в mid правую границу бинарного поиска. После бинарного поиска запустим ещё раз целевую функцию от ответа и выведем индексы путешественников из вектора ans.
Пример решения
int n, a;
vector<pair<pair<int, int>, int > > v;
set<pair<int, int> > s;
vector<int> ans;
int ok (int x) {
s.clear();
ans.clear();
for (int i = 0; i < n; i++) {
int l = v[i].first.first, r = v[i].first.second;
while (!s.empty() && s.begin()->first <= l) {
ans.push_back(s.begin()->second);
s.erase(s.begin());
}
if ((int)s.size() + 1 <= x) s.insert(mp(r, v[i].second));
else {
s.insert(make_pair(r, v[i].second));
set<pair<int, int> > :: iterator it = s.end();--it;
s.erase(it);
}
}
while (!s.empty()) {
ans.push_back(s.begin()->second);
s.erase(s.begin());
}
return (int)ans.size();
}
int main() {
cin >> n >> a;
v.resize(n);
for (int i = 0; i < n; i++)
cin >> v[i].first.first >> v[i].first.second, v[i].first.second += v[i].first.first, v[i].second = i;
sort(v.begin(), v.end());
int l = 0, r = a;
while (r - l > 1) {
int mid = (l + r) / 2;
if(ok(mid) >= a)
r = mid;
else
l = mid;
}
ok(r);
cout << r << endl;
for (int i = 0; i < a; i++)
cout << ans[i] + 1 << ' ';
cout << endl;
}
Лучшие результаты
В первом отборочном раунде приняло участие 929 человек. Лучший результат показал Владислав Макеев (Москва, Россия). Второе и третье место заняли Ростислав Величко (Ставрополь, Россия) и Роман Горбунов (Москва, Россия).
Второй отборочный раунд собрал 686 человек. С большим отрывом первое место в рейтинговой таблице занял Влад Мосько (Гомель, Белоруссия). Второе и третье место — Назарбек Алтыбай (Актобе, Казахстан) и Владимир Романов (Москва, Россия).
Мы ещё раз поздравляем всех финалистов и ждём новых участников в следующем году.