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

Как известно, при распространении радиоволн возникает интерференция, поэтому если рядом расположены две радиопередающие станции, вещающие на одной и той же частоте, то качество радиопередач резко снижается.

Радиостанция «Байтик» планирует транслировать свои программы в стране Флатландия. Министерство связи Флатландии выдало радиостанции лицензию на вещание на двух различных частотах.

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

Все передатчики, установленные на вышках, должны, согласно инструкции министерства, иметь одну и ту же мощность. Чтобы программы радиостанции могли приниматься на как можно большей территории, мощность передатчиков должна быть как можно большей. С другой стороны, необходимо, чтобы прием передач был качественным на всей территории Флатландии. Прием передач считается качественным, если не существует такого участка ненулевой площади, на который радиоволны радиостанции «Байтик» приходят на одной частоте одновременно с двух вышек.

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

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

Первая строка содержит число N — количество вышек (3 ≤ N ≤ 1200). Последующие N строк содержат по два целых числа — координаты вышек. Координаты заданы в километрах и не превышают 104 по модулю. Все точки, в которых расположены вышки, различны. Все числа в строках разделены пробелом.

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

В первой строке выводится вещественное число — искомая мощность передатчиков. Во второй строке выводятся N чисел, где i-е число должно быть равно 1, если соответствующий передатчик должен вещать на первой частоте, и 2, если на второй. Ответ должен быть выведен с точностью, не меньшей 10–8.

Примеры
Входные данные
4
0 0
0 1
1 0
1 1
Выходные данные
0.707106781186548
1 2 2 1

Команда Москвы на Всероссийской олимпиаде по информатике 2017 года оказалась настолько велика, что помещается только в 2 вагона. Некоторые школьники испытывают друг к другу такую личную неприязнь, что не могут есть, находясь в одном вагоне. Поскольку не есть в поезде нельзя (это противоречит СанПиНам), то участников олимпиады надо рассадить так, чтобы школьники, испытывающие взаимную неприязнь, ехали в разных вагонах. Если это невозможно, никто никуда не поедет.

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

Первая строка входного файла содержит количество школьников N (1 ≤ N ≤ 10000) и количество взаимных неприязней M (1 ≤ M ≤ 100000). Следующие M строк содержат пары чисел, задающих номера участников, испытывающих взаимную неприязнь. Участники нумеруются с единицы.

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

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

Примеры
Входные данные
4 3
1 2
2 3
2 4
Выходные данные
1 3 4 
2 

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

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

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

В первой строке находятся два числа $N$ и $M$ - количество студентов и количество пар студентов, обменивающихся записками ($1 \le N \le 100$, $0 \le M \le \frac{N \cdot (N-1)}{2}$). Далее в $M$ строках расположены описания пар студентов: два числа, соответствующие номерам студентов, обменивающихся записками (нумерация студентов идёт с 1). Каждая пара студентов перечислена не более одного раза.

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

Необходимо вывести ответ на задачу профессора Флойда. Если возможно разделить студентов на две группы - выведите YES; иначе выведите NO.

Примеры
Входные данные
3 2
1 2
2 3
Выходные данные
YES
Входные данные
3 3
1 2
2 3
1 3
Выходные данные
NO
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

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

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

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

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

1.Компьютеры размещаются на плоскости в точках с целочисленными координатами.

2.Координаты компьютеров x и y лежат в диапазоне 0  x, y  106.

3.Никакие два компьютера не располагаются в одной точке.

4.Кабели являются отрезками прямых.

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

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

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

В первой строке входного файла содержатся числа N и M  количество компьютеров и количество кабелей в схеме (1  N  100 000, 0  M  200 000). В последующих M строках содержатся пары чисел, разделенных пробелами. Каждая такая пара описывает один кабель, числа представляют собой номера соединенных компьютеров. Компьютеры пронумерованы от 1 до N. Никакая пара не встречается дважды, и никакой кабель не соединяет компьютер с самим собой.

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

Выходной файл должен содержать N строк. Строка с номером i должна содержать координаты i-го компьютера, разделенные пробелом. Сначала выводится координата x, затем y. Разрешается вывести любой вариант размещения компьютеров, при котором выполняются условия 1–5.

Примечания

Решения, корректно работающие при отсутствии циклов, будут оцениваться из 40 баллов.

Решения, корректно работающие при наличии только одного цикла, будут оцениваться из 60 баллов.

Пример входных и выходных данных

Ввод

Вывод

13 14

11 12

11 13

1 3

3 5

5 8

8 9

8 6

6 3

4 6

4 2

6 10

10 11

10 7

7 4

1 0

3 0

1 1

3 1

0 2

2 2

4 2

1 3

1 4

3 3

3 4

2 5

4 5


Петя с Васей решили поздравить всех своих одноклассниц с Международным Женским Днем. Важной частью любого праздника являются открытки. Купив их достаточно, друзья сели писать пожелания. Подписанные открытки они складывали на специальный стол, расчерченный в квадратную клетку параллельно краям стола так, что длина и ширина его составляли N и M клеток соответственно. По удивительному совпадению каждая открытка была размером точь-в-точь с две клетки стола. Петя настоял на том, чтобы класть подписанные поздравления строго по линиям сетки — горизонтально или вертикально, накрывая одной открыткой ровно две клетки.

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

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

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

В первой строке входного файла записаны два целых числа N и M (1 ≤ N, M ≤ 700) — длина и ширина стола. Гарантируется, что хотя бы одно из N, M четное. Будем считать, что все открытки занумерованы числами от 1 до NM. Следующие 2N строк содержат по M чисел: первые N строк описывают нижний слой, следующие N строк — верхний слой. Число k в i-й строке j-м столбце нижнего или верхнего слоя означает наличие на этой позиции одной из половинок открытки номер k.

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

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

В выходной файл запишите единственное слово NO, если не существует способа извлечь половину открыток нужным образом. В противном случае в первую строку выведите YES, во вторую — последовательность из NM/2 номеров открыток, которые надо достать, в правильном порядке. У каждой из них на момент извлечения хотя бы одна из половинок должна находиться сверху. Если искомых последовательностей несколько, выведите любую из них.

Частичные ограничения

Первая группа состоит из тестов, в которых произведение NM ≤ 24.

Вторая группа состоит из тестов, в которых N, M100.

Примеры
Входные данные
2 2
1 1
3 2
4 2
4 3
Выходные данные
YES
4
2
Входные данные
2 3
1 1 4
2 3 4
2 6 5
3 6 5
Выходные данные
YES
2
6
5

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