#113462

Музей

Источники: [ Командные олимпиады, ВКОШП, 2016, Задача H ]

В Федеральном Университете Флатландии открылся музей спортивных достижений. Главная гордость этого музея — зал, в котором расположены сувениры со всевозможных соревнований по спортивному программированию.

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

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

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

Помогите директору оградить экспонаты.

Входные данные

Входные данные содержат один или несколько тестовых примеров.

В первой строке находится число \(t\) — количество тестовых примеров. Далее следуют \(t\) блоков, каждый из которых выглядит следующим образом.

В первой строке блока находится два целых положительных числа \(n\) и \(m\) — количество вершин в многоугольнике, форму которого имеет зал, и количество сувениров в зале (\(3 \le n \le 2000, 1 \le m \le 2000\)).

В следующих \(n\) строках находятся по два целых числа \(xh_i \ и \ yh_i\) — координаты вершин многоугольника в декартовой системе координат (\(−10^9 \le xh_i , yh_i \le 10^9\) ). Вершины даны в порядке обхода против часовой стрелки.

В следующих \(m\) строках находятся по два целых числа \(xs_i , ys_i\) — координаты сувениров (\(−10^9 \le xs_i , ys_i \le 10^9\) ) .

Гарантируется, что все сувениры находятся строго внутри зала, а также что никакие три из данных \(n + m\) точек не лежат на одной прямой. Сумма всех \(n\) и сумма всех \(m\) во всех тестовых примерах одних входных данных не превосходят 2000 каждая.

Выходные данные

Для каждого из \(t\) тестовых примеров выведите следующее.

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

Иначе выведите в первой строке целое число \(k \ (1 \le k \le 2)\) — количество выбранных треугольников, и в каждой из следующих \(k\) строк выведите по три целых числа — номера вершин зала, которые являются вершинами треугольника.

Если оптимальных ответов несколько, выведите любой из них.

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

Замечание

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

Примеры

Входные данные

Выходные данные

#113463

Обычный мальчик

Источники: [ Командные олимпиады, ВКОШП, 2016, Задача I ]

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

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

Дано целое положительное число \(x\). Требуется найти число \(y > x\), у которого не менее 100 делителей. Причем число \(y\) должно превышать число \(x\) не более чем на 1%, то есть должно выполняться неравенство \(x \le y \le 1.01x\).

Помогите Пете решить эту сложную задачу.

Входные данные

Первая строка ввода содержит число \(x \ (1 \le x \le 10^{16})\).

Выходные данные

Если подходящего числа не существует, то выведите −1, иначе выведите любое подходящие число.

Замечание

Число 510510 имеет ровно 128 делителей.

Примеры

Входные данные

Выходные данные

-1

Входные данные

Выходные данные

#113464

Полиглоты-интроверты

Источники: [ Командные олимпиады, ВКОШП, 2016, Задача J ]

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

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

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

Найдите для каждой пары людей \((A, B)\), какое минимальное людей можно отвлечь, чтобы передать информацию от \(A\) к \(B\).

Входные данные

В первой строке входных данных содержатся 2 числа \(n\) и \(k\) — число людей в комнате и число различных языков, на которых они разговаривают (\(2 \le n \le 300\), \(1 \le k \le 300\)).

Следующие \(n\) строк содержат описания людей, \(i\)-я из этих строк описывает языки, которые знает \(i\)-й человек, в следующем формате: \(k_i a_{i,1} a_{i,2} \dots a_{i,k_i}\) — количество языков и сами языки в порядке возрастания номеров (\(1 \le k_i \le k, 1 \le a_{i,j} \le k, a_{i,j} < a_{i,j+1}\)).

Выходные данные

Выведите \(n\) строк, в каждой по \(n\) чисел \(f_{i,j}\) , разделенных пробелами — минимальное количество людей, которые отвлекутся при оптимальном способе передаче информации от \(i\)-го человека к j\(-\)му. На главной диагонали должны стоять нули. Если передать информацию от \(i\)-го человека к \(j\)-му невозможно, выведите вместо соответствующего числа −1.

Примеры

Входные данные

Выходные данные

0 3 3 2 4 5 
3 0 3 4 2 3 
3 3 0 4 4 5 
2 4 4 0 5 6 
4 2 4 5 0 2 
5 3 5 6 2 0

Входные данные

Выходные данные

#113465

"Исключающее или" наносит ответный удар

Источники: [ Командные олимпиады, ВКОШП, 2016, Задача K ]

Даны два неотрицательных целых числа \(a\) и \(n\). Требуется найти такое минимальное неотрицательное число \(b\), что \(a \oplus b\) нацело делится на \(n\).

Здесь \(\oplus\) обозначает операцию побитового «исключающего или» и соответствует операции «xor» в Паскале или «^» в других языках. Для вычисления побитового «исключающего или» двух чисел \(x\) и \(y\) необходимо записать каждое из них в двоичной системе счисления, дополнив, при необходимости, ведущими нулями слева. Результат в каждой позиции равен 1 в том случае, если в точности в одном из чисел в соответствующей позиции находится 1. К примеру, для чисел \(x = 12\) и \(y = 26\) результат равен 22:

Входные данные

В первой строке входных данных содержится число \(t\) — количество тестовых примеров (\(1 \le t \le 10^4\) ). В следующих \(t\) строках содержатся описания тестовых примеров. Каждое описание состоит из двух чисел \(a\) и \(n\), разделенных пробелом (\(1 \le a, n \le 10^{18}\)).

Выходные данные

Для каждого из тестовых примеров требуется вывести единственное число — искомое \(b\).

Примеры

Входные данные

Выходные данные

0
1
6

#113503

Купоны и скидки

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2016, Лига А, Задача C ]

Уже начался сезон олимпиад по программированию, а значит пора писать командные тренировки. Серёжа ведёт тренировки у своих команд не первый год и знает, что к туру надо подготовить не только набор задач и разбор. Тренировка длится несколько часов, и команды, которые в ней участвуют, успевают за это время проголодаться. Поэтому на каждую тренировку Серёжа закупает некоторое количество пицц, чтобы после окончания тура команды подкрепились и обсудили свои успехи и неудачи.

Командам предстоит написать n тренировок в течение n последовательных дней. Во время каждой тренировки на каждую команду, пришедшую в этот день, Серёжа заказывает по пицце в своей любимой пиццерии. Серёжа уже знает, что на i -ю тренировку придёт ровно a _i команд.

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

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

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

Входные данные

В первой строке находится целое число n ( 1 ≤ n ≤ 200 000 ) — количество тренировок.

Во второй строке находится n целых чисел a ₁ , a ₂ , ..., a _n ( 0 ≤ a _i ≤ 10 000 ), разделённых пробелами, — количества команд, которые придут на каждую из тренировок.

Выходные данные

Если Серёжа может заказать все пиццы, используя только скидки и купоны и не покупая лишние пиццы ни в один из дней, выведите « YES » (без кавычек). Иначе выведите « NO » (без кавычек).

Примечание

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

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

Примеры

Входные данные

4
1 2 1 2

Выходные данные

YES

Входные данные

3
1 0 1

Выходные данные

NO