---> 39 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

Пастбища Берляндии в опасности. Волки напали на пастбище овец. Пастух решил застрелить всех волков, при этом не убив ни одной овцы. Ружье заряжено бронебойными патронами, поэтому пули пролетают насквозь. Овцы и волки представлены отрезками. Пастух находится в точке (0, 0). Траектория полета пули — луч, выходящий из точки (0, 0). Если траектория пули имеет общуюточку с отрезком, характеризующим животное, то животное умирает. Найдите наименьшее количество выстрелов, необходимое для убийства всех волков. Овцы при этом должны остаться живы.

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

В первой строке записаны два целых числа N и M (0 ≤ N ≤ 100000, 0 ≤ M ≤ 100000) — количество волков и овец соответственно. Далее следует N+M строк. В каждой строке записано четыре числа X1, Y1, X2, Y2 (−1000 ≤ X1, X2 ≤ 1000, 1 ≤ Y1, Y2 ≤ 1000), описывающие отрезки. Первые N отрезков описывают положение волков, следующие M строк положение овец.

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

Выведите наименьшее количество выстрелов, необходимое для убийства всех волков. Если невозможно убить всех волков, сохранив овец живыми, то выведите “No solution”.

Примеры
Входные данные
1 1
5 5 6 7
3 5 8 5
Выходные данные
No solution

Входные данные
2 1
1 1 2 3
-5 4 2 2
999 1000 1000 999
Выходные данные
1
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

Первая строка входного файла содержит два натуральных числа N и M (1 ≤ n ≤ 10000; NM ≤ 100000)

Следующие M строк содержат пары чисел xi и pi, xi – координата i-ой фабрики, а pi – идентификатор детали, которую производит данная фабрика (xi ≤ 100000; xixi +1; 1 ≤ piN).

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

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

Первая строка выходного файла должна содержать целое число K — количество точек, где может быть расположена Фабрика Гаджетов.

Следующие K строк должны содержать координаты этих точек в возрастающем порядке. Значения должны выводится с точность 10-6.

Примеры
Входные данные
3 5
-1 3
0 1
2 3
4 2
5 2
Выходные данные
1
2.0
Входные данные
2 5
1 1
2 2
3 1
4 2
5 1
Выходные данные
4
1.5
2.5
3.5
4.5

На прямой задано $N$ попарно различных отрезков $[a_i, b_i]$ ($i = 1, 2, \dots, N$, $a_i < b_i$). Будем говорить, что отрезок номер $i$ непосредственно содержится в отрезке номер $j$ ($i \ne j$), если:

  • он полностью принадлежит $j$-му (то есть $a_j \le a_i$ и $b_i \le b_j$),
  • среди заданных $N$ отрезков не найдётся такого отрезка (с номером $k$), что $i$-й отрезок принадлежит $k$-му и $k$-й принадлежит $j$-му (здесь $i$, $j$ и $k$ - различные числа).

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

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

Сначала вводится целое число $N$ ($1 \le N \le 100\,000$). Далее идут $N$ пар целых чисел $a_i$, $b_i$ ($-10^9 \le a_i < b_i \le 10^9$).

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

Выведите $N$ чисел. Число номер $i$ должно быть равно номеру отрезка, в котором непосредственно содержится отрезок номер $i$, либо 0 - если такого не существует.

Если существует несколько решений, выведите любое.

Примечания

Тесты состоят из четырёх групп.

  1. Тест 1, из условия, оценивается в 0 баллов.
  2. Тесты 2--11. В них $N \le 100$. Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 12--27. В них $N \le 10\,000$. Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Тесты 28--35. Off-line группа, полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.
Примеры
Входные данные
4
2 3
0 4
1 6
0 5
Выходные данные
3 4 0 0
ограничение по времени на тест
0.0 second;
ограничение по памяти на тест
0 megabytes

При написании программы, проверяющей ответ участника для задачи 3204 "Отрезки на прямой возвращаются" (прочитайте её условие!), жюри столкнулось с трудностями, превосходящими сложность самой задачи. С мыслью "почему бы и нет" написание такой программы было решено также включить в комплект задач.

Проверяющей программе доступно три блока информации:

  • входные данные в формате, описанном в условии предыдущей задачи,
  • ответ некоторого абстрактного участника в формате, также описанном в предыдущем условии,
  • ответ жюри.

Ваша задача - написать программу, которая по этим данным определит, правильно ли программа абстрактного участника посчитала ответ.

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

Вход состоит из трёх частей. Первая часть - число $N$ ($1 \le N \le 100\,000$) и следом $N$ пар $a_i$, $b_i$ ($-10^9 \le a_i < b_i \le 10^9$). Далее идут $N$ чисел, каждое из которых от 0 до $N$, $i$-е равно номеру отрезка, являющегося одним из непосредственно содержащих $i$-й, либо нулю - по мнению абстрактного участника. Далее идут ещё $N$ чисел в том же формате - ответ жюри на эту задачу.

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

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

Выведите $N$ строк. В $i$-й строке должен быть вердикт для $i$-го отрезка. Выведите OK, если ответ абстрактного участника правильный, и WA - иначе.

Примечания

Тесты состоят из четырёх групп.

  1. Тест 1, из условия, оценивается в 0 баллов.
  2. Тесты 2--11. В них $N \le 100$. Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  3. Тесты 12--27. В них $N \le 10\,000$. Группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
  4. Тесты 28--35. Off-line группа, полные ограничения. Каждый тест оценивается в 5 баллов (тесты оцениваются независимо друг от друга). При этом баллы за тесты этой группы ставятся только тогда, когда программа проходит все тесты групп 1 и 2. Если программа не проходит хотя бы один из тестов групп 1 и 2, то баллы за тесты группы 3 не ставятся.
Примеры
Входные данные
4
2 3
0 4
1 6
0 5
2 2 1 0
3 4 0 0
Выходные данные
OK
WA
WA
OK

На прямой задано некоторое множество отрезков с целочисленными координатами концов [$L_i$, $R_i$]. Выберите среди данного множества подмножество отрезков, целиком покрывающее отрезок [0, $M$], ($M$ — натуральное число), содержащее наименьшее число отрезков.

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

В первой строке указана константа $M$ ($1 \leq M \leq 5000$). В каждой последующей строке записана пара чисел $L_i$ и $R_i$ ($|L_i|, |R_i| \leq 50000$), задающая координаты левого и правого концов отрезков. Список завершается парой нулей. Общее число отрезков не превышает 100 000.

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

В первой строке выходного файла выведите минимальное число отрезков, необходимое для покрытия отрезка [0; $M$]. Далее выведите список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe. Завершающие два нуля выводить не нужно. Если покрытие отрезка [0, $M$] исходным множеством отрезков [$L_i$, $R_i$] невозможно, то следует вывести единственную фразу “No solution”.

Примеры
Входные данные
1
-1 0
-5 -3
2 5
0 0

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

Входные данные
1
-1 0
0 1
0 0
Выходные данные
1
0 1

Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест