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

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

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

Требуется написать программу, которая назначит каждой станции тарифный номер.

1

4 станции, 3 перегона: 1-4, 2-4, 3-4

Маршруты: 1-4-2, 2-4-3, 3-4-1.


Ответ: решения нет

2

5 станций, 4 перегона: 1-5, 2-5, 3-5, 4-5

Маршруты: 1-5-2, 2-5-3, 3-5-4, 4-5-1.


Ответ: решение есть; например, следующее: номер станции: 1 2 3 4 5

тарифный номер: 1 4 1 5 3


Замечание: тарифные номера разных станций могут совпадать.

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

В первой строке входных данных содержатся два целых числа: N — количество станций (2 N ≤ 100 000), и M — количество перегонов между ними (1 M N – 1). В последующих M строках записаны пары целых чисел a, b (a ≠ b, 1 ≤ aN, 1 ≤ bN), означающие наличие перегона между станциями a и b. За ними в отдельной строке записано единственное целое положительное число K — количество маршрутов электричек. В последующих K строках идут описания маршрутов электричек, по одному на строке. Каждое описание представляет собой последовательность целых чисел — номеров всех станций маршрута в порядке одного из двух возможных направлений следования электрички. Описание маршрута заканчивается числом 0.

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

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

В первую строку  выведите «NO», если искомого назначения тарифных номеров не существует. В противном случае в первую строку выведите «YES», а в следующей строке — N целых положительных чисел, где i-е число — тарифный номер i-й станции. Тарифный номер каждой станции должен находиться в диапазоне от 1 до N.

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

Система оценивания

Тесты к этой задаче состоят из четырёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.

  • Группа 1 (20 баллов): N, K <= 20
  • Группа 2 (30 баллов): N, K <= 2000
  • Группа 3 (50 баллов): без дополнительных ограничений
Примеры
Входные данные
6 5
1 2
5 2 
5 6
4 5
3 2
6
1 2 0
5 6 0
3 2 1 0
5 2 3 0
4 5 2 0
6 5 4 0
Выходные данные
YES
2 3 4 1 2 3 
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задано N точек. Из каждой точки исходят красные или синие ребра во все точки с большим номером. Требуется определить, существует ли пара точек такая, что из первой можно добраться до второй как по красным ребрам так и по синим.

Даны N точек, занумерованных числами 1, 2, ..., N. От каждой точки с меньшим номером к каждой точке с большим номером ведет стрелка красного или синего цвета. Раскраска стрелок называется однотонной, если нет двух таких точек A и B, что от A до B можно добраться как только по красным стрелкам, так и только по синим.

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

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

В первой строке входных данных содержится единственное число N (3 ≤ N ≤ 5000).

В следующих N–1 строках идет описание раскраски. В (i+1)-й строке  записано (N–i) символов R (красный) или B (синий), соответствующих цвету стрелок, выходящих из точки i и входящих в точки (i+1), (i+2), ..., N соответственно.

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

Выведите YES, если приведенная раскраска является однотонной, и NO в противном случае.

Оценка задачи

1 балл будут набирать решения, верно работающие для N ≤ 50.

Примеры
Входные данные
3
RB
R
Выходные данные
NO
Входные данные
3
RR
R
Выходные данные
YES
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан ориентированный граф. Требуется определить, есть ли в нем цикл.

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

В первой строке вводится число вершин N≤ 50. Далее в N строках следуют по N чисел, каждое из которых – 0 или 1. j-ое число в i-ой строке равно 1 тогда и только тогда, когда существует ребро, идущее из i-ой вершины в j-ую. Гарантируется, что на диагонали матрицы будут стоять нули.

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

Выведите 0, если в заданном графе цикла нет, и 1, если он есть.

Примеры
Входные данные
3
0 1 0
0 0 1
0 0 0
Выходные данные
0
Входные данные
3
0 1 0
0 0 1
1 0 0
Выходные данные
1
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке входных данных содержатся два числа: N и S (1 ≤ N ≤ 100; 1 ≤ SN), где N – количество вершин графа, а S – заданная вершина. В следующих N строках записано по N чисел – матрица смежности графа, в которой 0 означает отсутствие ребра между вершинами, а 1 – его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

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

Выведите одно целое число – искомое количество вершин.

Примеры
Входные данные
3 1
0 1 1
1 0 0
1 0 0
Выходные данные
3
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

На банкет были приглашены N Очень Важных Персон (ОВП). Были поставлены 2 стола. Столы достаточно большие, чтобы все посетители банкета могли сесть за любой из них. Проблема заключается в том, что некоторые ОВП не ладят друг с другом и не могут сидеть за одним столом. Вас попросили определить, возможно ли всех ОВП рассадить за двумя столами.

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

В первой строке входных данных содержатся два числа: N и M (1 <= N,M <= 100), где N – количество ОВП, а M – количество пар ОВП, которые не могут сидеть за одним столом. В следующих M строках записано по 2 числа – пары ОВП, которые не могут сидеть за одним столом.

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

Если способ рассадить ОВП существует, то  выведите YES в первой строке и номера ОВП, которых необходимо посадить за первый стол, во второй строке. В противном случае в первой и единственной строке выведите NO.

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

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