Хабрахабр

Мобильный Яндекс.Блиц: разбираем задачи

Третий конкурс состоялся совсем недавно — поздравляем победителей! В 2018 году мы провели три конкурса Яндекс.Блиц — по машинному обучению, мобильной разработке и фронтенду. Кандидатам на позицию мобильного разработчика в Яндексе пригодится опыт решения таких задач. Мы тем временем хотим вернуться ко второму из них, где предлагались задачи на стыке алгоритмов и написания софта для Android/iOS. Почитайте подробные разборы некоторых из них.

Задача «Газоснабжение»

Ввод

Вывод

Ограничение времени

Ограничение памяти

стандартный ввод или input.txt

стандартный вывод или output.txt

15 секунд

15 мегабайт

Ника разрабатывает приложение для топ-менеджеров одной крупной газовой компании, которое поможет им планировать добычу.

На каждое месторождение продается отдельная лицензия — лицензии стоят s1 … si … sn. Компания рассматривает n месторождений, которые удалены от магистрали на d1 … di … dn километров и могут дать v1 … vi … vn единиц газа.

В этом компании помогает подрядчик, который умеет прокладывать m разных видов труб. Чтобы соединить месторождения с магистралью, нужно построить трубопроводы. Их можно комбинировать друг с другом как угодно. Трубы отличаются друг от друга длиной (l1 … li … lm) и ценой (p1 … pi … pm).

У компании есть k монет, и она хочет получить как можно больше газа.

Сколько компания сможет добыть, если даст подрядчику оптимальные распоряжения?

Трубопровод может быть длиннее, чем расстояние от месторождения до магистрали.

Формат ввода

Первая строка содержит целое число k ≤ 105.

Вторая строка содержит целое число n ≤ 15.

Следующие n строк содержат по три целых числа di ≤ 100, vi ≤ 100 и si ≤ 100.

Числа разделены пробелом.

Следующая строка содержит целое число m ≤ 15.

Числа разделены пробелом. Следующие m строк содержат по два целых числа li ≤ 100 и pi ≤ 100.

Формат вывода

Единственная строка с ответом.

Примеры

Ввод

Вывод

116
3
58 7 50
81 71 56
52 57 31
3
47 9
1 25
18 61

57

Разбор

Пусть имеется класс объектов Deposit (месторождение) с параметрами $ Dd_$ (удаленность), $Dv_{i}$ (объем добычи) и $Ds_{i}$ (стоимость лицензии). Для начала определимся с обозначениями. Также имеется класс объектов Pipeliner с параметрами $PPl_{j}$ (длина трубы, которую подрядчик может построить) и $PPp_{j}$ (цена этой трубы), индексируем через j. Индексировать объекты этого типа будем переменной i. Предполагается, что нет, и приведенный пример это явно показывает. У участников блица много раз возникал вопрос, можно ли один вид трубы использовать дважды. Так что по условию этой задачи, приняв $D_{i} = {0, 1}$ (выбираем месторождение или нет) и $PP_{j} = {0, 1}$ (выбираем подрядчика или нет), можно составить задачу линейного программирования:

$ \sum\limits_{i} D_{i} * Dv_{i} \rightarrow max \\ \sum\limits_{i} D_{i} * Ds_{i} + \sum\limits_{j} PP_{j} * PPp_{j} \leq k \\ \sum\limits_{i} D_{i} * Dd_{i} \leq \sum\limits_{j} PP_{j} * PPl_{j} \\ D_{i} = {0, 1}, PP_{j} = {0, 1} $

Однако по условию задачи от нас требуется вернуть только максимальный объем добычи (то есть значение целевой функции) и не требуется указывать, какие месторождения и каких подрядчиков нужно выбрать. Решить ее можно, например, симплекс-методом. После правильного построения таблицы достаточно найти в ней максимальное значение, которое и будет ответом. Вкупе с ограничениями в условии задачу можно решить методом динамического программирования, построив таблицу dp[length][money], где length — длина трубопровода, money — деньги. Ограничений задачи по памяти достаточно для построения.

Задача «Башни и AI»

Ввод

Вывод

Ограничение времени

Ограничение памяти

стандартный ввод или input.txt

стандартный вывод или output.txt

1 секунда

64 мегабайта

Правила игры простые. Артем разрабатывает искусственный интеллект, играющий в состязательную мобильную игру.

На своем ходу игрок может разломать одну из башен так, что получится несколько башен поменьше. Перед игроками имеется n башен высотой c1 … ci … cn. Например, башню высотой 7 можно разбить на (1, 2, 4), но не на (1, 3, 3). Игроки боятся запутаться в башнях, поэтому они договорились об ограничении: после разделения не должно получиться двух башен одинаковой высоты. Высота — всегда целое число.

Проигрывает тот, кому не остается башен, которые можно разрушить.

Чтобы оценить работу ИИ, Артему нужно знать, должен ли робот выиграть, если оба игрока действуют оптимально. У Артема есть очень умный друг, который играет оптимально, — именно с ним сражается искусственный интеллект Артема. Помогите ему с этим.

Он сыграет с ИИ k партий. Человек всегда ходит первым.

Формат ввода

Первая строка содержит целое число k < 500.

Далее следуют k блоков по две строки.

В первой строке каждого блока целое число 0 < n ≤ 50.

Числа разделены пробелами. Во второй строке каждого блока n целых чисел 0 < ci ≤ 50.

Формат вывода

k строк, каждая из которых содержит значение true или false в зависимости от того, победит ли в партии человек.

Примеры

Ввод

Вывод

2
1
4
2
1 1

false
false

Разбор

Предлагаемая игра в башни — равноправная конечная игра для двух игроков, в которой невозможно сыграть вничью.

Для читателей, знакомых с теорией игр, очевидно, что любая из равноправных игр двух игроков на самом деле эквивалентна игре «ним», а значит и наша игра тоже. Следовательно, победа конкретного игрока в игре определяется состоянием игры и порядком ходов двух игроков.

Вот краткое описание ним-игры (ссылка на источник — перейдите по ней для детального ознакомления):

За один ход игрок может взять из какой-нибудь одной кучки любое ненулевое число камней и выбросить их. Есть несколько кучек, в каждой из которых по нескольку камней. все кучки пусты. Соответственно, проигрыш наступает, когда ходов больше не осталось, т.е.

За один ход разрешается строго уменьшить любое из чисел (если в результате число станет нулём, то оно удаляется из набора). Итак, состояние игры "ним" однозначно описывается неупорядоченным набором натуральных чисел.

Решение ним-игры состоит в нахождении xor-суммы от размера кучек, и только если эта сумма отлична от нуля, можно однозначно утверждать, что мы находимся в выигрышном состоянии.

Как только функция, задающая отображение состояний нашей игры на ним-игру, будет найдена, решение задачи сведется к решению ним-игры, которое уже известно. Дальше нам на помощь приходит теорема Шпрага-Гранди, которая гласит, что состояние U любой равноправной игры двух игроков можно сопоставить кучке ним-игры размера X.

Задача «Индикация рейтинга»

Ввод

Вывод

Ограничение времени

Ограничение памяти

стандартный ввод или input.txt

стандартный вывод или output.txt

1 секунда

64 мегабайта

Она решила обозначать рейтинги заведений с помощью семиконечных звезд. Галя разрабатывает агрегатор отзывов.

Звезда должна быть нарисована по следующим правилам: Система отрисовки на вход получает прямоугольник высотой h и шириной w, левый верхний угол которого расположен в точке (x, y).

  1. Размеры звезды определяются шириной или высотой прямоугольника — тем, что меньше. (См. рисунки.)
  2. Если одно из измерений прямоугольника больше, чем соответствующее измерение звезды, звезда должна быть отцентрирована по этому измерению.
  3. Звезда повернута острием вверх.

Помогите Гале их рассчитать. Система отрисовки ожидает от кода Гали координаты вершин звезды.

В системе координат ось X направлена слева направо, ось Y сверху вниз. Чтобы построить семиконечную звезду, Галя берет внешний контур фигуры, полученной соединением вершин правильного семиугольника через одну. Программа Гали не падает, получив на вход некорректные значения ширины и высоты.

Формат ввода

Единственная строка содержит целые числа x, y, w и h, разделенные пробелами.

Пример: запись 150 0 50 100 обозначает прямоугольник шириной 50 точек, высотой 100 точек и с левым верхним углом в точке (150, 0).

Формат вывода

Числа должны быть округлены до целых. Единственная строка, содержащая 28 чисел, разделенных пробелами, — координаты вершин звезды начиная с верхней и далее по часовой стрелке. Посмотрите пример вывода и иллюстрацию к задаче, прежде чем приступать к решению.

Пример: вывод трех точек (1, 2), (3, 4), (5, 6) должен выглядеть так: 1 2 3 4 5 6.

Примеры

Ввод

Вывод

0 0 100 100

50 1 65 21 90 21 85 45 100 64 78 75 72 99 50 88 28 99 22 75 0 64 15 45 10 21 35 21

Примечания

  • Требуемая точность — 10 значащих цифр.

  • Система координат: ось Х направлена слева направо, ось Y сверху вниз:

  • Ожидаемый порядок вершин:

Примеры вписанных звезд:

Разбор

Решение задачи сводится к трем этапам: построить эталонную звезду с нужной ориентацией в пространстве, отмасштабировать получившиеся точки, вычислить и применить смещение.

Точки внешних вершин рассчитываются с помощью тривиальной тригонометрии, а вот с внутренними задача чуть сложнее. Построение звезды
Проще всего будет построить звезду, вписанную в окружность с единичным радиусом с центром в начале координат. Более простой способ — найти пересечения отрезков, соединяющих внешние вершины. Их можно найти как минимум двумя способами. Проще всего это сделать сначала, например, для 5-конечной звезды, и обобщить на N-конечную с произвольным промежутком между соединяемыми вершинами. Более сложный — найти формулу для вычисления радиуса вписанной окружности из радиуса описанной окружности.

Таким образом, нам нужно отмасштабировать полученные точки так, чтобы расстояние от самой левой до самой правой не превышало заданную ширину, а расстояние от самой верхней до самой нижней не превышало заданную высоту. Масштабирование
Во всех вариантах дается размер, в который нам нужно вписать звезду. Так как мы предусмотрительно строили эталонную звезду с центром в начале координат, достаточно просто умножить координаты каждой точки на выбранный коэффициент. Берем коэффициенты масштабирования для приведения ширины и высоты к нужным значениям, и выбираем меньший из них.

Входные данные всех вариантов можно свести к ограничивающему прямоугольнику с заданной координатой верхнего левого угла. Смещение
Осталось последнее: переместить наши точки так, чтобы звезда находилась в заданных рамках. Аналогично поступаем и с x-координатой, только берем не самую верхнюю точку, а самую левую. Тут все просто: берем самую верхнюю точку из получившихся на прошлом этапе, считаем разницу ее y-координаты с y-координатой верхнего левого угла, и смещаем все точки по вертикали на полученное значение. Остался последний штрих: отцентрировать звезду в этом прямоугольнике.

Дальнейшие действия зависят от того, какой коэффициент мы выбрали на предыдущем этапе:

  • если масштабировали по высоте — берем разницу между шириной прямоугольника и расстоянием от самой левой до самой правой точки;
  • если масштабировали по ширине — берем разницу между высотой прямоугольника и расстоянием от самой верхней до самой нижней точки.

Ответ получен. Делим полученное значение на 2 и смещаем точки по соответствующему измерению.

Задача «Вращение и масштабирование круга»

Ввод

Вывод

Ограничение времени

Ограничение памяти

стандартный ввод или input.txt

стандартный вывод или output.txt

1 секунда

64 мегабайта

Она хочет дать пользователю возможность двумя пальцами поворачивать круг на экране и менять его размер, вот так: Вика разрабатывает графический редактор для смартфонов и планшетов.

Размер фигуры меняется пропорционально длине отрезка. Фигура поворачивается на тот же угол, на который поворачивается соединяющий пальцы отрезок. Изначально круг имеет координаты (x, y) и радиус r. Сначала осуществляется поворот фигуры, а затем изменение ее размеров. Помогите Вике рассчитать конечные координаты центра круга и его радиус. Дан список тач-событий, описывающих жест пользователя. Круг вращается относительно точки (a, b).

Первый палец, который приложил пользователь, получает id 0, второй — id 1 и т. Описание тач-события содержит id пальца, координаты и тип события. д.

Пример:
0 337 490 ACTION_DOWN — это значит, что с пальцем 0 в точке (337, 490) произошло событие ACTION_DOWN.

Тач-события бывают следующих типов:

  • ACTION_DOWN — пользователь приложил к экрану первый палец в заданной точке.
  • ACTION_POINTER_DOWN — пользователь приложил к экрану второй палец в заданной точке.
  • ACTION_MOVE — пользователь переместил палец в заданную точку.
  • ACTION_POINTER_UP — пользователь переместил второй палец в заданную точку и отпустил его.
  • ACTION_UP — пользователь переместил первый палец в заданную точку и отпустил его.
  • ACTION_CANCEL — пользователь прервал жест.

Формат ввода

Вторая строка содержит числа a и b, разделенные пробелами. Первая строка содержит числа x, y и r, разделенные пробелами. Следующие несколько строк содержат последовательные тач-события.

Формат вывода

Числа разделены пробелами. Единственная строка с координатами и радиусом.

Пример

Ввод

Вывод

252 194 78
445 559
0 337 490 ACTION_DOWN
1 599 490 ACTION_POINTER_DOWN
1 576 564 ACTION_MOVE
1 552 590 ACTION_MOVE
0 407 375 ACTION_MOVE
1 505 615 ACTION_MOVE
1 482 620 ACTION_MOVE
0 477 360 ACTION_MOVE
1 435 616 ACTION_MOVE
1 411 607 ACTION_MOVE
0 547 386 ACTION_MOVE
1 364 548 ACTION_POINTER_UP
0 571 387 ACTION_UP

831 704 73

Примечания

При выводе результата необходимо все значения с плавающей точкой округлить до целочисленного значения по правилам математического округления.

Разбор

Для поворота фигуры нам необходимо высчитать угол поворота, который можно получить, по следующей формуле:
a = atan2(prevTouchX2 — prevTouchX1, prevTouchY2 — prevTouchY1) — atan2(currentTouchX2 — currentTouchX1, currentTouchY2 — currentTouchY1). Несмотря на то, что жест кажется сложным, его можно разделить на две составляющие: поворот и масштабирование.

После того, как мы повернули фигуру, нам остается отмасштабировать ее. Получив угол поворота, нужно повернуть саму фигуру, что сводится к повороту каждой точки фигуры на угол поворота. Необходимо запомнить расстояние между первым и вторым пальцем при получении события ACTION_POINTER_DOWN для второго пальца, после чего, отслеживая расстояние между первыми двумя пальцами, можно рассчитывать коэффициент, на который и нужно масштабировать фигуру. Масштабирование фигуры реализуется достаточно тривиально.

Задача «Строительство дорог»

Ввод

Вывод

Ограничение времени

Ограничение памяти

стандартный ввод или input.txt

стандартный вывод или output.txt

1 секунда

64 мегабайта

Он начинает с периметра — башен, соединённых прямыми лазерными стенами. В мобильной игре главный герой строит базу на далёкой планете. С точки зрения обороны базы нет смысла ставить три и более соседних башен на одну прямую. Архитекторы из штаба присылают ему план, на котором отмечены n башен, имеющие координаты (x1, y1) … (xi, yi) … (xn, yn). Штабные архитекторы, однако, иногда располагают башни именно так, поэтому игроку приходится самому убирать лишние промежуточные башни.

Он хочет построить k дорог между башнями — дорога может соединять любые две не соседние башни, но не может пересекать другую дорогу или стену. Покончив с периметром, герой начинает обустраивать базу изнутри. Из одной башни может выходить сколько угодно дорог.

Чтобы выбрать оптимальный план строительства дорог, герой поручает им перебрать все возможные варианты. У героя есть p роботов-дорожников. Если перед очередной итерацией оказывается, что не рассмотренных вариантов осталось меньше, чем роботов, лишние роботы освобождаются и отправляются на кухню готовить обед. Роботы начинают работать одновременно и раз за разом одновременно приносят уникальные варианты расположения дорог. Оставшиеся роботы доделывают последние варианты и отключаются.

Если оказывается, что можно проложить дорогу снаружи от базы, герой объявляет базу небезопасной и улетает с планеты.

Сколько роботов будут работать на кухне?

Формат ввода

Числа разделены пробелами. Первая строка содержит три целых числа 4  ≤  n  ≤  107, 1 ≤ k ≤ n и простое число 105 < p < 11 × 104.

Числа разделены пробелами. Следующие n строк содержат по два целых числа 0  < x i, yi  <  109.

Формат вывода

Если база не безопасна, вывести −1. Единственная строка с ответом.

Пример 1

Ввод

Вывод

4 1 101363
0 0
1 0
1 1
0 1

101361

Ими будут заниматься два робота, а остальные отправятся на кухню: p – 2 = 101 361. Есть два способа проложить единственную дорогу: (0, 0) — (1, 1) и (1, 0) — (0, 1).

Пример 2

Ввод

Вывод

4 1 101363
1 0
2 0
0 1
1 2

-1

Герой признаёт базу небезопасной, ответ −1. Тут можно построить дорогу между (1, 0) — (0, 1), а это снаружи базы.

Пример 3

Ввод

Вывод

4 1 101363
0 0 1 0
2 0
0 1

101363

Ни одной дороги проложить не получится поэтому все роботы сразу отправятся на кухню: p = 101 363. Башни (0, 0), (1, 0) и (2, 0) стоят на одной прямой, поэтому среднюю башню (1, 0) герой строить не будет.

Разбор

Разобьем решение задачи на три шага.

Многоугольник является выпуклым, если все его вершины располагаются по одну сторону от линии, несущей любое ребро. Первый шаг — для входного набора данных вершин определим, является ли многоугольник выпуклым, и если является, то сколько у него реальных вершин. Если выражение равно 0, то вершины лежат на одной прямой и по условию задачи башня, стоящая в средней вершине, исчезает, уменьшая общее количество башен. Для каждой тройки смежных вершин $ (x_{i-1}, y_{i-1}), (x_{i}, y_{i}), (x_{i+1}, y_{i+1}) $ построим пару векторов $ab = ( (x_{i-1}, y_{i-1}), (x_{i}, y_{i}) ) и bc = ( (x_{i}, y_{i}), (x_{i+1}, y_{i+1}) )$, и посчитаем знак выражения ab.x bc.y — bc.x ab.y. Если для всех троек вершин знак произведения — 0 или всегда одинаков, то переходим ко второму шагу, если нет, считаем базу небезопасной и выводим ответ -1.

Количество способов построения k непересекающихся диагоналей внутри выпуклого N-угольника равно $ V = 1/(k+1){N-3\choose k}{N+k-1\choose k} $, нам же нужно посчитать выражение p — V mod p, где p — простое. Второй шаг.

как $ a * p^e $, где наибольший общий делитель — a, и p gcd(a, p) = 1. Представим N!

$ {n\choose r} = (n!)/(r!(n-r)!) = a_{1}*p^{e_{1}}/a_{2}*p^{e_{2}}*a_{3}*p^{e_{3}} = (a_{1}/a_{2}*a_{3})*p^{e_{1}-e_{2}-e_{3}} $

Если $ e_{1}-e_{2}-e_{3} > 0 $, значит, выражение без остатка делится на p и ответом в задаче будет число p.

Для случая $ e_{1}-e_{2}-e_{3} > 0 $ = 0 ответом будет $a_{1}/a_{2}*a_{3}$ mod p.

При вычислении учитываем, что ab mod p = (a mod p ) (b mod p) mod p, а $k^{-1}$ mod p = $(k)^{p-2}$ mod p для простых p.

Для расчета выражения $ e_{1}-e_{2}-e_{3} $ представим n! Третий шаг. Итого, n mod p = ($(p-1)!^k$k (n mod p)!)mod p, где k = floor(n/p). как 12p(p+1)...2p(2p+1)..., при этом (p+1)...(2p-1) mod p = 12...(p-1)=(p-1)!..

Задача «Суперпростой планировщик»

Ввод

Вывод

Ограничение времени

Ограничение памяти

стандартный ввод или input.txt

стандартный вывод или output.txt

10 секунд

224 мегабайта

На их выполнение требуется  t1 … ti … tn единиц времени, причем к началу di-й единицы времени i-я задача должна быть выполнена. Имеется n задач, которые нужно выполнить на процессоре смартфона.

В первом потоке за единицу времени расходуется единица энергии, во втором — полторы единицы энергии, в третьем — еще в полтора раза больше, чем во втором, и т. Чтобы успеть, задачи можно выполнять в нескольких потоках, однако каждый новый поток создает все большую нагрузку на батарею. д.

Одновременно выполнять разные кусочки задачи в разных потоках нельзя. Задачи можно дробить по единицам времени: вначале частично выполнить одну, потом перейти к другой, потом вернуться к первой.

После того как задача распределена, перенести ее в другие слоты планировщик не может. Планировщик получает задачи по одной; получив задачу, он сразу выделяет для нее временные слоты.

Сколько энергии потребуется на выполнение всех задач, если распределить их оптимально?

Формат ввода

Числа разделены пробелами. Первая строка содержит целое число 1 < n ≤ 3 × 103.
Следующие n строк содержат по два целых числа 0 ≤ ti ≤ 104 и 0 ≤ di ≤ 104.

Формат вывода

Точность — восемь знаков после запятой. Единственная строка с ответом.

Пример

Ввод

Вывод

5
2 2
1 1
3 4
1 10
1 2

10.25000000

Разбор

При планировании задачи мы берем минимальное значение потребляемой энергии k=1 и, начиная от дедлайна задачи, перебираем все слоты временного отрезка. Так как по условию задачи нам достаточно посчитать только количество потребляемой энергии, нам подойдет способ решения путем подсчета количества потребляемой энергии для каждой единицы времени.

При достижении начала временного отрезка нам необходимо увеличить коэффициент к в 1,5 раза и повторить перебор временных слотов, начиная с дедлайна и до тех пор, пока задача не будет полностью запланирована. Если значение энергопотребления слота меньше значения коэффициента (к) и этот временной слот не использовался при планировании задачи, то занимаем этот слот для выполнения задачи путем увеличения коэффициента слота на к. По завершении планирования всех задач остается только посчитать итоговое энергопотребление, сложив полученные коэффициенты каждой единицы времени.

Задача «Разрушимые объекты»

Ввод

Вывод

Ограничение времени

Ограничение памяти

стандартный ввод или input.txt

стандартный вывод или output.txt

2 секунды

64 мегабайта

Игра находится на стадии разработки, так что пока все сделано очень просто: разрушаемый объект представляет собой n-угольник с вершинами в точках (x1, y1)...(xi, yi)...(xn, yn). В 2D-игре можно разрушать объекты. Затем то же самое проделывается с получившимися многоугольниками. Алгоритм берет вогнутую вершину с наименьшим номером и соединяет ее с ближайшей не соседней вершиной — так, чтобы длина соединительного отрезка была минимальной. Все повторяется до тех пор, пока не останутся только выпуклые многоугольники — это и есть осколки, которые увидит игрок.

Например, имеется многоугольник с вершинами [0 1 2 3 4], причем вершина 1 вогнутая и ближе всего к ней находится вершина 3 Алгоритм соединит вершины 1 и 3, получив фигуры с вершинами [1 2 3] и [0 1 3 4].

Вершины с развернутым углом между ребрами приравниваются к выпуклым. Алгоритм проводит соединительные отрезки так, что они целиком лежат внутри многоугольников. Если можно построить отрезок до нескольких равноудаленных вершин, алгоритм выбирает ту, у которой меньше номер.

Чему равна сумма длин всех отрезков, построенных для разрушения объекта?

Формат ввода

Следующие n строк содержат по два целых числа x и y. Первая строка содержит целое число n ≤ 500. Числа разделены пробелами.

Формат вывода

Точность — шесть знаков после запятой. Единственная строка с ответом.

Пример 1

Ввод

Вывод

4
100 100
200 100
200 200
100 200

0.000000

Пример 2

Ввод

Вывод

6
167 84
421 84
283 192
433 298
164 275
320 133

326.986753

Разбор

После решения этой проблемы поставленные условия задачи можно выполнить «в лоб» полным перебором всех вариантов соединений: ограничения времени выполнения и количества вершин — довольно мягкие. Основная сложность задачи сводится к тому, чтобы определить, лежит ли отрезок между двумя вершинами внутри многоугольника. Второстепенный момент: определение выпуклых и вогнутых вершин, а также направления обхода (заданы ли вершины по или против часовой стрелке) легко разрешается с помощью косого произведения векторов.

Необходимым условием является отсутствие пересечений между отрезком и любой другой стороной многоугольника (за исключением сторон, прилегающих к вершинам, являющимися концами отрезка). Вопрос, находится ли отрезок внутри многоугольника? Поэтому если выполнилось необходимое условие, нам нужно определить, находится ли любая точка этого отрезка (за исключением конечных точек) внутри многоугольника. Однако это условие не является достаточным: легко можно придумать фигуру, в которой отрезок, соединяющий две вершины, будет снаружи и при этом не пересекать ее стороны. Если количество пересечений нечетное — значит, точка (и весь отрезок) лежит внутри многоугольника, иначе — снаружи. Сделать это можно с помощью так называемого even-odd rule: пустить из этой точки невидимый луч и посчитать количество его пересечений со сторонами многоугольника.

Вот с какими сложностями можно столкнуться при реализации (список, разумеется, можно продолжать): У этой задачи, конечно, есть подводные камни — она не предлагалась бы в финальном туре, если бы решение было простым и очевидным.

  • Определение соседних вершин (при переходе через нулевой индекс);
  • Параллельные прямые: случай, когда какая-либо сторона частично или полностью совпадает с рассматриваемым отрезком;
  • Ошибки округления (в общем случае числа с плавающей точкой нужно сравнивать с точностью до некоторого значения, в нашем случае для прохождения тестов было достаточно значения 10е-5 или более точного);
  • При реализации even-odd rule — случай прохода луча через вершину;
  • В случае прохода луча через вершину есть еще один подводный камень: когда луч проходит через вершину с углом 180 градусов между сторонами и совпадает с этими сторонами.

Задача «DNA»

Ввод

Вывод

Ограничение времени

Ограничение памяти

стандартный ввод или input.txt

стандартный вывод или output.txt

8 секунд

128 мегабайт

Человек касается пальцем специального сенсора, а прибор берет определенный фрагмент его ДНК и ищет в этом фрагменте последовательности, которые хранятся в базе данных. Корпорация добра разработала устройство, мгновенно идентифицирующее людей по генотипу. Составьте перечень подстрок, которые найдет устройство. Дан пример фрагмента ДНК и n разных последовательностей. Искомые последовательности могут частично совпадать. В ДНК встречаются четыре буквы: A, T, G и C. Последовательность не может полностью совпадать с началом другой последовательности.

Формат ввода

Следующие n строк содержат по одной последовательности ДНК. Первая строка содержит целое число n. Общий объем входных данных не превышает 6⋅106 символов. Последняя строка содержит проверяемый фрагмент ДНК.

Формат вывода

Указывайте номер стартовой позиции и саму подстроку. В каждую строку вывода записывайте одно вхождение последовательности в проверяемый фрагмент. Нумерация букв во фрагменте ДНК начинается с единицы. Одно от другого отделяйте пробелом. Обязательно посмотрите примеры, прежде чем приступать к задаче. Вывод сортируйте по номеру стартовой позиции.

Пример

Ввод (скопируйте фрагмент в любой редактор, чтобы увидеть его целиком):

5
TTT
GAAGCT
CAAT
AGA
AGGCA
CTTTCAGAATCATGACCTGCACGGCAAAGAGACGCTTATTATGGAGCTCGACATGGCAATAACGCGACGAATCTACGTCACGACGAGAATAGTGTAAACGAAGCTGCTGACGGCGGAAGCGTCAAAGGGGTCTGTGAATTGTTATTCGCGAAAAACATCCGTCCCCGTGGGGGATAGTCACCGACGCCGTTTTATAGAAGCCTAGGGGAACAGGTTGGTTTAACTAGCTTAAGAAAGTAAATTCTGGGATTATACTGTAGTAATCACTAATTTACGGTGAGGGTTTTATGGCGGATCTTTACAAATTCAAGCCAGGTGATTTCAACAAATTTTGCTGACGATTTAGGCGCACTATCCCCTAAACTACAAATTAGAAAATAGCGTTCCTTGACGGCTAGAATTACCTACCGGCCTCCACCATACCTTCGATATTCGCGCCCACTCTCCCATTAATCCGCACAAGTGGATGTGATGCGATTGCCCGCTAAGATATTCTAACGTGTAACGCAGATGAGTATTCTACAGAGTTGCCGTACGCGTTGAACACTTCACGGATGATAGGAATTTGCGTATAGAGCGTGTCATTGAGGGGTTATACACCCGTAGACTACAACGGGCCCGGCTCAATCAGAACTCGAGTGCCTTGAATAACATACTCATCACTAAACATTCTCAACAGTCAATCGAGCAAGTCCATTATCAACGAGTGTGTTGCAGTTTTATTCTCTCGCCAGCATTGTAATAGGCACTAAAAGAGTGATGATAGTCATGAGTGCTGAGCTAAGACGGCGTCGGTGCATAGCGGACTTTCGGTCAGTCGCAATTCCTCACGAGACCCGTCCTGTTGAGCGTATCACTCTCAATGTACAAGCAACCCGAGAAGGCTGTGCCTGGACTCAACCGGATGCAGGATGGACTCCAGACACGGGGCCACCACTCTTCACACGTAAAGCAAGAACGTCGAGCAGTCATGAAAGTCTTAGTACCGCACGTGCCATCT

Вывод:

2 TTT
6 AGA
28 AGA
30 AGA
57 CAAT
86 AGA
100 GAAGCT
190 TTT
191 TTT
196 AGA
219 TTT
232 AGA
271 TTT
284 TTT
285 TTT
298 TTT
320 TTT
330 TTT
331 TTT
342 TTT
373 AGA
397 AGA
488 AGA
509 AGA
524 AGA
565 TTT
574 AGA
605 AGA
625 CAAT
630 AGA
681 CAAT
718 TTT
719 TTT
744 AGGCA
754 AGA
784 AGA
808 TTT
821 CAAT
833 AGA
861 CAAT
879 AGA
921 AGA
955 AGA

Разбор

Решение задачи сводилось к нахождению паттернов в строке наиболее оптимальным способом — например, по алгоритму Ахо-Корасика. Это последняя задача в финале, но не последняя по сложности. Автомат получает по очереди все символы строки и переходит по соответствующим ребрам. Алгоритм строит конечный автомат, которому затем передает строку поиска. Если автомат пришел в конечное положение, соответствующая строка словаря присутствует в строке поиска.

Вся сложность состояла в том, что требовалось найти такое решение за линию.

Задача «QR Quest»

Ввод

Вывод

Ограничение времени

Ограничение памяти

стандартный ввод или input.txt

стандартный вывод или output.txt

1 секунда

64 мегабайта

Формат ввода

Следующие t строк содержат по восемь целых чисел ni, разделенных пробелами. Первая строка содержит единственное целое число t, обозначающее количество тестовых кейсов.

Формат вывода

t строк, каждая из которых содержит одно целое число.

Пример 1

Ввод

Вывод

4
8 10 1 9 2 6 7 8
14 2 0 11 10 4 1 0
6 6 4 1 10 0 11 6
11 4 3 4 14 8 12 5

0
13
15
5

Пример 2

Ввод

Вывод

4
9 10 6 2 12 11 7 2
3 10 1 14 13 13 1 1
6 8 8 5 3 2 6 4
5 11 5 5 3 1 10 7

3
9
2
7

Разбор

QR-код позволял перейти по ссылке на документ, содержащий три таблицы значений. Мы оставили это бонусное задание для самых пытливых, потому что до методики решения еще надо было додуматься. С этими значениями требовалось провести кое-какие манипуляции.

Требовалось догадаться, какая операция была произведена с этими ячейками и из какой таблицы лишняя ячейка. Всего на вход подавалось восемь чисел — координаты ячеек в этих таблицах, то есть 4 пары с координатами столбца и строки.

Путем нехитрых манипуляций можно было удостовериться, что это xor-сумма для четырех ячеек таблиц A, B и C, адресуемых индексами a0...a7:
R = A[a0, a1] ^ B[a2, a3] ^ B[a4, a5] ^ C[a6, a7].

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»