Сегодня мы открываем регистрацию на международный конкурс по программированию Яндекс.
Алгоритм.
В этом году мы решили не только запустить раньше, но и добавили два новых трека: трек оптимизации и машинного обучения.
Каждый участник может выбрать, в каких треках участвовать.
А теперь по порядку.
В этом году конкурс открывается алгоритмическим треком.
Он пройдет в классическом варианте с правилами tcm/time и системой «гран-при 30».
Отборочный тур стартует 17 февраля.
Все, кто решит хотя бы одну задачу, пройдут в отборочный тур и смогут побороться за стильные футболки, которые попадут в ТОП-256, и денежные призы для трех победителей трека.
Ссылка к Регистрация .
Разминка уже прошла в минувшее воскресенье, ниже вы можете найти анализ задач этого тура.
Анализ проблем А.
Время в зазеркалье Ограничение по времени 1 секунда Ограничение памяти 512Мб В офисе, где работает Бомбослав, есть стильные дизайнерские часы.
Их циферблат имеет стандартную разметку: на круге имеется 60 делений, соответствующих минутам, 12 из которых (начиная с расположенного вверх от центра круга, затем равномерно с шагом в пять делений) сделаны крупнее остальных.
, то есть они соответствуют часам.
Стильными эти часы делает тот факт, что на циферблате нет цифр, поскольку предполагается, что каждый прекрасно знает, какое деление какому значению текущего времени соответствует. Сегодня такие часы висели над рабочим местом Бомбослава.
Периодически поглядывая на них, он впервые заметил некоторую странность в направлении движения стрелок.
Присмотревшись, Бомбослав обнаружил, что над его рабочим местом действительно было зеркало, а на стене позади него - часы.
Это значит, что Бомбослав видит циферблат отраженным относительно вертикальной оси, проходящей через его центр.
Теперь он хочет научиться быстро определять настоящее текущее время, зная время, которое отображается на отраженном циферблате.
Часы устроены таким образом, что обе стрелки движутся дискретно, то есть часовая стрелка всегда указывает на одно из 12 больших делений, соответствующих текущему количеству часов, а минутная стрелка — на одно из 60 делений, соответствующих текущему количеству часов.
количество минут. Формат ввода
Единственная строка ввода содержит два целых числа 
И 
( 
, 
) — положение часовой и минутной стрелки на отраженном циферблате соответственно.
означает, что часовая стрелка направлена вертикально вверх, 
соответствуют стрелке, направленной строго вправо, 
- стрелка направлена вертикально вниз, 
- строго налево.
Аналогичные инструкции применимы и к минутной стрелке для значений 
И 
.
Выходной формат
Выведите два целых числа 
и 
( 
, 
) — реальное значение текущего времени на часах.
Решение: Рассмотрим движение «прямой» и «отраженной» стрелок.
За то время, когда «прямая» стрелка повернется на определенный угол, «отраженная» стрелка повернется на тот же угол, но в другую сторону, т. е.
суммарный угол поворота стрелок равен полному обороту.
Для каждой стрелки мы самостоятельно вычисляем ее положение.
Для часа это 12 минус текущая позиция, а для минуты 60 минус текущая позиция.
В обоих случаях необходимо не забыть заменить 12 или 60 на ноль.
Б.
Палиндромный фактор Ограничение по времени 1 секунда Ограничение памяти 512Мб Аркадий — большой поклонник использования машинного обучения в любых задачах.
Он верит в безграничную силу магии этой популярной молодой науки.
Именно поэтому Аркадий постоянно придумывает все новые и новые коэффициенты, которые можно рассчитать для различных объектов.
Напомним, что палиндром — это строка, которая читается одинаково от начала до конца и от конца к началу.
Для каждой строки в своей базе данных Аркадий хочет найти кратчайшую подстроку, состоящую как минимум из двух символов и являющуюся палиндромом.
Если таких подстрок несколько, Аркадий хочет выбрать лексикографически минимальную.
Формат ввода Единственная строка входных данных содержит одну строку из базы данных Аркадии — непустую последовательность строчных букв английского алфавита.
Длина строки не менее 2 и не превышает 200 000 символов.
Выходной формат Выведите из входных данных подстроку минимальной длины строки, состоящую как минимум из двух символов и являющуюся палиндромом.
Напомним, что среди всех таких строк Аркадий хочет найти лексикографически минимальную.
Решение: Пусть существует некоторая подстрока, являющаяся палиндромом.
Если мы удалим первый и последний символ палиндрома, оставшаяся строка также будет палиндромом.
Мы будем повторять процесс до тех пор, пока не останется строка из двух или трех букв (в зависимости от четности).
Всегда существует линейное число подстрок длиной два или три, и их общая длина также линейна, поэтому среди таких строк можно подобрать ответ с помощью наивного алгоритма.
Если ни одна из подстрок такой длины не является палиндромом, то выводим 
.
C. Разделите их всех Ограничение по времени 1 секунда Ограничение памяти 512Мб После работы Оля и Толя решили вместе сходить на стрельбище.
Пройдя вводный инструктаж и получив оружие, они оказались на огневых позициях, а напротив них находились 
цели.
Все цели можно рассматривать как фигуры, нарисованные на бесконечной плоскости, причем каждая цель представляет собой круг или прямоугольник, цели могут перекрываться и пересекаться любым образом.
Прежде чем приступить к стрельбе, Оля и Толя хотят убедиться, что смогут четко определить результаты своих выстрелов.
Для этого договорились провести прямую линию, которая разделила бы самолет с мишенями на две части.
Однако, чтобы никто не обиделся, они хотят провести прямую линию так, чтобы каждая мишень делилась ровно пополам, то есть для каждого круга и каждого прямоугольника должно быть верно, что прямая делит его на две части.
фигуры равной площади.
Когда Оля и Толя наконец закончили отрабатывать все условия разделения мишеней на две части, они начали сомневаться, что вообще можно провести такую прямую линию, и просят вас ответить на этот вопрос.
Формат ввода
Первая строка входных данных содержит целое число
( 
) — количество целей.
Каждое из следующих
строка содержит целое число 
( 
), указывая тип цели.
Если 
, тогда целью является круг, а затем следуют три целых числа 
, 
И 
, определяющие радиус и координаты центра окружности соответственно ( 
, 
).
Если 
, то целью является прямоугольник, который затем определяется восемью целыми числами 
— координаты всех четырёх вершин ( 
), перечисленные в порядке по часовой стрелке или против часовой стрелки.
Гарантируется, что эти четыре вершины образуют прямоугольник ненулевой площади.
Выходной формат Если существует линия, которая разделит каждый из существующих кругов и прямоугольников на две части одной площади, выведите «Да».
В противном случае выведите «Нет».
Решение: Чтобы решить эту задачу, нам понадобится простой геометрический факт: прямая делит круг на две равные части тогда и только тогда, когда она проходит через его центр.
Аналогично для прямоугольника прямая линия делит его на две части равной площади тогда и только тогда, когда она проходит через точку пересечения диагоналей.
В обоих случаях достаточность следует из симметрии относительно этой точки, а необходимость можно установить, проведя через эту точку линию, параллельную данной.
Теперь нам нужно только проверить, лежат ли все центры фигур, указанных во входных данных, на одной прямой.
Для удобства будем считать удвоенными координаты центров; тогда для получения центра прямоугольника достаточно сложить координаты двух противоположных вершин.
Если среди построенного множества точек не более двух разных, то ответ заведомо положительный.
В противном случае рассмотрим любую пару различных точек и проверим, что все остальные точки лежат на прямой, определяемой этой парой.
Самый удобный способ проверить это по трем точкам 
, 
И 
( 
) лежат на одной прямой — используйте векторное произведение векторов 
И 
.
Общая сложность решения: 
.
D. Задание на собеседование Ограничение по времени 3 секунды Ограничение памяти 512Мб Алексей регулярно проводит собеседования с кандидатами на должности стажеров.
И хотя он уже провел сотни собеседований, в последнее время этот процесс дается ему нелегко - кандидаты стали легко решать все проверенные и отработанные годами Алексеем задачи! Делать было нечего, и накануне очередного собеседования Алексей придумал новое задание.
Имеется числовая последовательность, на первом шаге состоящая из двух чисел 1. На каждом шаге следующего шага между каждыми двумя соседними элементами добавляется новый элемент, равный их сумме.
После первых нескольких шагов последовательность выглядит следующим образом:
1 1
1 2 1
1 3 2 3 1
1 4 3 5 2 5 3 4 1 На собеседовании Алексей хочет попросить кандидата написать программу, которая по заданному числу
определит, во сколько раз увеличится число
будет происходить последовательно
-й шаг? Алексей пока не научился решать свою проблему, но слышал, что кандидат, которого он сейчас проведет собеседование, достиг высоких результатов в спортивном программировании, поэтому он, скорее всего, легко справится с этим вопросом.
Формат ввода
Входные данные содержат одно число
( 
).
Выходной формат Выведите одно целое число, равное количеству вхождений числа.
в последовательность, описанную в условии на шаге
.
Решение: Докажем несколько лемм.
Лемма 1. Числа, оказавшиеся соседними на каком-то шаге, являются относительно простыми.
Докажем это по индукции.
База очевидна (1 и 1 взаимно просты).
Пусть это будет доказано
шаги.
Все цифры написаны 
-й шаг представляет собой сумму
два соседних
-й шаг чисел, то есть сумма двух относительно простых чисел.
Но НОД( 
,
) = НОД (
,
)=1. Лемма доказана.
Лемма 2. Нет упорядоченной пары соседних чисел 
не может произойти более одного раза в последовательности (ни на одном шаге, ни на разных).
Даже если это не так, то давайте отметим цифру 
шаг, на котором впервые произошло повторение (т. е.
повторилась та пара, которая существовала на этом или предыдущем шаге).
Пусть пара 
возник на
-м и далее 
-й шаг ( 
).
Но тогда, если 
, Что 
было построено как сумма соседей 
И 
(Если 
, Что
было построено как сумма
И 
), то есть на 
-м и далее 
Также наблюдалось повторение -шагов, что противоречит нашему предположению.
Лемма доказана.
Лемма 3. Любая упорядоченная пара взаимно простых чисел на каком-то шаге неизбежно окажется соседней.
Пусть у нас будут цифры 
, стою рядом на каком-то шагу и даю
(не теряя общий смысл).
Затем
было получено в размере
+
, то есть на предыдущем
стояли рядом друг с другом
И
.
Если 
, затем два шага назад вправо от
там был номер 
, Если 
, затем слева от
там был номер 
и так далее.
Потому что
И
относительно просты, то на каком-то шаге этот процесс, являющийся по сути разновидностью алгоритма Евклида, приведет к тому, что с одной стороны возникнет 
, а с другой - некоторые
натуральное число.
Но пара 
или 
для всех
будет соседней последовательностью на
-й шаг.
А поскольку действия восстанавливаются однозначно,
то это означает, что исходная пара
в какой-то момент она встретится как соседка.
Таким образом, каждая упорядоченная пара взаимно простых чисел встречается ровно один раз в качестве соседей в данной последовательности.
Следовательно, задача сводится к подсчету количества упорядоченных пар взаимно простых чисел, сумма которых равна
.
Потому что, если
И
относительно просты, то
И 
взаимно просты, то числу таких пар можно поставить в однозначное соответствие количество чисел, взаимно простых с
или значение функции ЭYler из
.
Вычисление количества таких чисел является известной задачей и основано на мультипликативности функции Эйлера: если 
, то взаимнопростые с
будут цифры 
.
Макет
по простым факторам во времени 
.
Е.
Резервное копирование Ограничение по времени 5 секунд Ограничение памяти 512Мб Чтобы обеспечить сохранность пользовательских данных, Аркадий постоянно придумывает и тестирует новые схемы резервного копирования.
На этот раз он пронумеровал все имеющиеся у него компьютеры с данными от 1 до
и для каждого компьютера с номером от 1 до 
назначил резервный компьютер 
.
При этом он строго следовал правилу, что номер компьютера для резервного копирования всегда больше номера самого компьютера, то есть 
.
По этой причине компьютер с номером
Компьютера для резервного копирования нет. В ходе текущего эксперимента Аркадий выбрал определенную конфигурацию значений.
и будет последовательно выключать компьютеры каждую секунду.
?Эксперимент заканчивается, когда Аркадий выключает компьютер с номером
.
Изначально каждый компьютер содержит некий блок данных размером 1. При отключении компьютера с номером
, первоначально находящийся на нем блок данных размером 1 передается на компьютер с номером 
, в данном случае, если на компьютере число
были другие блоки данных (полученные с других компьютеров при их выключении), потом они исчезают. Если компьютер
уже отключен, то блок данных с компьютера
оно никуда не передается и тоже исчезает. Аркадий хочет, чтобы эксперимент продолжался как можно дольше, но он вынужден соблюдать еще одно дополнительное ограничение: если он собирает на любом компьютере
блоков данных, то для сохранности оборудования этот компьютер необходимо немедленно выключить в течение следующей секунды.
Обратите внимание, что последняя секунда (в течение которой компьютер выключается
) не учитывается.
Формат ввода
Первая строка входных данных содержит целое число 
( 
) — количество тестовых примеров.
С последующим
описания тестовых случаев, каждое описание начинается со строки, содержащей два целых числа
И
(
, 
) — количество компьютеров, участвующих в эксперименте, и максимальное количество блоков данных на одном компьютере соответственно.
Вторая строка содержит
число 
( 
).
Выходной формат
Для каждого из
тестовые примеры выведите одно целое число — максимально возможную продолжительность эксперимента, то есть максимальное количество секунд, при котором
Теги: #Машинное обучение #Алгоритмы #спортивное программирование #Яндекс.
алгоритм
-
Защита Blu-Ray
19 Oct, 24 -
Архитектурный 3D-Рендеринг
19 Oct, 24 -
Подробности Атаки На Сайт Microsoft
19 Oct, 24
