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

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


uu9njmq2vxp3qc6e1bu1t10wci4.jpeg

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


Ввод Вывод Ограничение времени Ограничение памяти
стандартный ввод или input.txt стандартный вывод или output.txt 15 секунд 15 мегабайт

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

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

Чтобы соединить месторождения с магистралью, нужно построить трубопроводы. В этом компании помогает подрядчик, который умеет прокладывать 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_{i}$ (удаленность), $Dv_{i}$ (объем добычи) и $Ds_{i}$ (стоимость лицензии). Индексировать объекты этого типа будем переменной i. Также имеется класс объектов Pipeliner с параметрами $PPl_{j}$ (длина трубы, которую подрядчик может построить) и $PPp_{j}$ (цена этой трубы), индексируем через j. У участников блица много раз возникал вопрос, можно ли один вид трубы использовать дважды. Предполагается, что нет, и приведенный пример это явно показывает. Так что по условию этой задачи, приняв $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 сверху вниз:



statement-image?imageId=616b6e564acd39e0

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


statement-image?imageId=eb8d83a0485129b9

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


statement-image?imageId=89e1ef3f85568a79

Разбор

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

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

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

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

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


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

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

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


Ввод Вывод Ограничение времени Ограничение памяти
стандартный ввод или input.txt стандартный вывод или output.txt 1 секунда 64 мегабайта

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


statement-image?imageId=9d1bf3ab6c6d4f11

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

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

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

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


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


Формат ввода

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


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

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


Пример


Ввод Вывод 
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

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


Пример 2


Ввод Вывод 
4 1 101363
1 0
2 0
0 1
1 2

-1

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


Пример 3


Ввод Вывод 
4 1 101363
0 0 
1 0
2 0
0 1

101363

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


Разбор

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

Первый шаг — для входного набора данных вершин определим, является ли многоугольник выпуклым, и если является, то сколько у него реальных вершин. Многоугольник является выпуклым, если все его вершины располагаются по одну сторону от линии, несущей любое ребро. Для каждой тройки смежных вершин $ (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, то вершины лежат на одной прямой и по условию задачи башня, стоящая в средней вершине, исчезает, уменьшая общее количество башен. Если для всех троек вершин знак произведения — 0 или всегда одинаков, то переходим ко второму шагу, если нет, считаем базу небезопасной и выводим ответ -1.

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

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

$ {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.</p> <p>Для случая <img src= 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! как 12… p(p+1)…2p(2p+1)…, при этом (p+1)…(2p-1) mod p = 12…(p-1)=(p-1)!… Итого, n mod p = ($(p-1)!^k$k (n mod p)!)mod p, где k = floor (n/p).

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


Ввод Вывод Ограничение времени Ограничение памяти
стандартный ввод или input.txt стандартный вывод или output.txt 10 секунд 224 мегабайта

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

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

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

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

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


Формат ввода

Первая строка содержит целое число 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 мегабайта

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

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

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

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


Формат ввода

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


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

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


Пример 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 мегабайта


statement-image?imageId=7befb946e4b49b65

Формат ввода

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


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

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].

© Habrahabr.ru