Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Обход в глубину
    Компоненты сильной связности(3 задач)
    Мосты(2 задач)
    Применение обхода в глубину(3 задач)
    Топологическая сортировка(2 задач)
    Точки сочленения(1 задач)
---> 33 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
#112094
Пиксели торжествуют
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

08.03.2014, Париж, Франция. Дерзкое ограбление совершено в Парижском музее современного искусства. Похищено множество экспонатов, наиболее известный из которых — картина «Пиксели торжествуют» киберкубиста Этьена Бурсье-Мужено.

«Это большая потеря для нас, — заявил директор музея Фабрис Эрготт. — Полиция уже разыскивает преступников, но мы вынуждены признать, что, судя по тому, как легко злоумышленники справились с охранной системой, мы имеем дело с профессионалами экстра-класса и не питаем надежд на возвращение шедевра в нашу коллекцию. Кроме того, уничтожена вся база данных музея, поэтому реставраторы не обладают достаточным количеством информации для восстановления картины. Безусловно, каждый образованный француз знает, что она представляет собой прямоугольник из \(H\) x \(W\) черных и белых квадратных пикселей (\(H\) — высота, а \(W\) — ширина картины в пикселях). Но информацию о цвете самих пикселей придется добывать по крупицам».

В свою очередь, представитель Национального архива Франции Армель Ле Гофф поспешила успокоить культурную общественность: «К счастью, архив располагает снимками отдельных фрагментов картины. А именно, в нашем распоряжении имеется информация о \(N\) прямоугольных фрагментах (со сторонами, параллельными соответствующим сторонам картины), для каждого из которых известны его координаты \(r_1\), \(c_1\), \(r_2\), \(c_2\), а также цвета входящих в него пикселей. Строки картины пронумерованы от 1 до \(H\) сверху вниз, столбцы — от 1 до \(W\) слева направо, (\(r_1\); \(c_1\)) — номера строки и столбца левого верхнего пикселя фрагмента, (\(r_2\); \(c_2\)) — номера строки и столбца правого нижнего пикселя фрагмента, \(r_1\) ≤ \(r_2\), \(c_1\) ≤ \(c_2\). Однако, в силу ряда причин некоторые фрагменты могут храниться в инвертированном виде, то есть все белые пиксели в них заменены на черные, а все черные — на белые, при этом достоверно не известно, какие фрагменты инвертированы. Это серьезно усложняет задачу по восстановлению утерянного шедевра величайшего киберкубиста, поэтому мы обращаемся за помощью ко всему программистскому сообществу. Национальный архив, со своей стороны, готов предоставить все имеющиеся данные о фрагментах картины. Мы отдаем себе отчет в том, что, возможно, картину не удастся восстановить однозначно, поэтому просим найти максимально светлую из всех возможных подходящих картин, то есть содержащую как можно больше белых пикселей: широко известно, что „Пиксели“ являются одним из самых оптимистичных творений Этьена Бурсье-Мужено».

Формат входного файла

Первая строка входного файла содержит два целых числа \(H\) и \(W\) (1 ≤ \(H\) * \(W\) ≤ \(10^6\)) — высоту и ширину картины в пикселях. Вторая строка содержит единственное целое число \(N\) (1 ≤ \(N\) ≤ \(10^6\)) — количество фрагментов. Далее содержатся \(N\) описаний фрагментов. Первая строка описания — координаты \(r_1\), \(c_1\), \(r_2\), \(c_2\) (1 ≤ \(r_1\) ≤ \(r_2\) ≤ \(H\), 1 ≤ \(c_1\) ≤ \(c_2\) ≤ \(W\)). Следующие \(r_2\) - \(r_1\) + 1 строк описания содержат сам фрагмент (возможно, инвертированный): каждая из этих строк состоит из ровно \(c_2\) - \(c_1\) + 1 нулей и единиц, разделенных пробелами. Нули означают белые пиксели, единицы - черные.

Суммарная площадь всех фрагментов \(S\) ≤ \(10^6\).

Формат выходного файла

Если подходящей картины не существует, то~есть предоставленные Национальным архивом данные противоречивы, выведите единственное число \(-1\).

Иначе в первой строке выходного файла выведите максимальное число нулей, которое могла содержать утерянная картина, а в следующих \(H\) строках — искомую картину с максимально возможным количеством нулей в том же формате, что и фрагменты во входном файле: \(H\) строк, в каждой из которых \(W\) разделенных пробелами нулей и единиц. Если подходящих картин с максимальным числом белых пикселей несколько, выведите любую из них.

Комментарий

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

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

Тесты к этой задаче состоят из четырех групп.

0. Тесты 1–2. Тесты из условия, оцениваются в ноль баллов.

1. Тесты 3–27. В тестах этой группы \(N\) ≤ 10, \(S\) ≤ 1 000, \(H\) * \(W\) ≤ 1 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.

2. Тесты 28–36. В тестах этой группы \(N\) ≤ 500, \(S\) ≤ 20 000, \(H\) * \(W\) ≤ 500 000. Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.

3. Тесты 37–39. В тестах этой группы \(S\) ≤ 20 000, \(H\) * \(W\) ≤ 500 000. Эта группа оценивается в 4 балла, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой и второй групп.

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

Примеры
Входные данные
2 3
3
1 1 1 2
0 1
1 2 2 2
0
1
1 3 2 3
1
1
Выходные данные
5
0 1 0 
0 0 0
Входные данные
2 3
2
1 2 2 3
0 1
1 0
1 1 1 3
0 1 1
Выходные данные
-1
#112335
Автомат с игрушками
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes
В развлекательном центре \(Е\)-города был установлен игровой автомат нового поколения. В автомат можно бросить монету и следить за её продвижением сверху вниз по разветвляющемуся лабиринту из трубок. В лабиринте есть n узлов, которые пронумерованы числами от 1 до \(n\). При бросании монета попадает в первый узел. Каждый узел лабиринта, кроме первого, имеет одну входящую сверху трубку, по которой монета может в него попасть. Из каждого узла выходит не более двух трубок, идущих вниз, одна из которых ведет налево, а другая — направо. Каждая трубка имеет некоторую ширину. Монета проваливается в более широкую трубку, а в случае равенства ширины трубок — в левую.

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

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

Панкрату понравилась игрушка, которая находится в узле с номером \(v\).

Требуется написать программу, которая определяет, сколько монет должен бросить в автомат Панкрат, чтобы получить игрушку из узла \(v\).

Формат входного файла

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

Описание k-го узла состоит из четырех целых чисел: \(a_k\), \(u_k\), \(b_k\), \(w_k\). Если из \(k\)-го узла выходит левая трубка, то \(a_k\) — номер узла, в который она ведет (\(k\) < \(a_k\) <= \(n\)), а \(u_k\) — её ширина. Если левой трубки нет, то \(a_k\) = \(u_k\) = 0. Если из \(k\)-го узла выходит правая трубка, то \(b_k\) — номер узла, в который она ведет (\(k\) < \(b_k\) <= \(n\)), а \(w_k\) — её ширина. Если правой трубки нет, то \(b_k\) = \(w_k\) = 0.

В последней строке задано целое число \(v\) (1 <= \(v\) <= \(n\)) — номер узла, в котором находится игрушка, понравившаяся Панкрату.

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

Формат выходного файла

Выходной файл должен содержать одно число — количество монет, которое необходимо бросить в автомат Панкрату, чтобы получить игрушку, которая находится в узле \(v\). Если получить выбранную игрушку невозможно, выведите число −1.

Система оценки

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

Подзадача 1

1 <= \(n\) <= 100

1 <= \(u_k\); \(w_k\) <= 300

Подзадача оценивается в 50 баллов.

Подзадача 2

1 <= \(n\) <= \(10^5\)

1 <= \(u_k\); \(w_k\) <= \(10^9\)

Подзадача оценивается в 50 баллов.

Пояснения к примеру

В первом примере первая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 1, 3 и 4:

Вторая монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 2 и 6:

Третья монета пройдет лабиринт по следующему пути, и игрок получит игрушки из вершин 5 и 7:

Примеры
Входные данные
7
2 1 3 2
0 0 6 3
4 1 5 1
0 0 0 0
7 2 0 0
0 0 0 0
0 0 0 0
5
Выходные данные
3
Входные данные
4
0 0 2 1
4 1 3 1
0 0 0 0
0 0 0 0
3
Выходные данные
-1
#113441
Размещение данных
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Телекоммуникационная сеть крупной IT-компании содержит n серверов, пронумерованных от 1 до \(n\). Некоторые пары серверов соединены двусторонними каналами связи, всего в сети m каналов. Гарантируется, что сеть серверов устроена таким образом, что по каналам связи можно передавать данные с любого сервера на любой другой сервер, возможно с использованием одного или нескольких промежуточных серверов.

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

На рис. 1 показан пример сети и отказоустойчивого множества из серверов с номерами 1 и 4. Данные на сервер 2 можно передать следующим образом. При недоступности канала между серверами 1 и 2 — с сервера 4, при недоступности канала между серверами 2 и 3 — с сервера 1. На серверы 3 и 5 при недоступности любого канала связи можно по другим каналам передать данные с сервера 4.

В рамках проекта группе разработчиков компании необходимо разместить свои данные в сети. Для повышения доступности данных и устойчивости к авариям разработчики хотят продублировать свои данные, разместив их одновременно на нескольких серверах, образующих отказоустойчивое множество. Чтобы минимизировать издержки, необходимо выбрать минимальное по количеству серверов отказоустойчивое множество. Кроме того, чтобы узнать, насколько гибко устроена сеть, необходимо подсчитать количество способов выбора такого множества, и поскольку это количество способов может быть большим, необходимо найти остаток от деления этого количества способов на число \(10^9 + 7\).

Требуется написать программу, которая по заданному описанию сети определяет следующие числа: \(k\) — минимальное количество серверов в отказоустойчивом множестве серверов, \(c\) — остаток от деления количества способов выбора отказоустойчивого множества из \(k\) серверов на число \(10^9 + 7\)

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

Первая строка входного файла содержит целые числа \(n\) и \(m\) — количество серверов и количество каналов связи соответственно (\(2 \le n \le 200000\), \(1 \le m \le 200000\)). Следующие \(m\) строк содержат по два целых числа и описывают каналы связи между серверами. Каждый канал связи задается двумя целыми числами: номерами серверов, которые он соединяет.

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

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

Выведите два целых числа, разделенных пробелом: \(k\) — минимальное число серверов в отказоустойчивом множестве серверов, \(c\) — количество способов выбора отказоустойчивого множества из \(k\) серверов, взятое по модулю \(10^9 + 7\)

Пояснения к примеру

В приведенном примере отказоустойчивыми являются следующие множества из двух серверов: {1, 3}, {1, 4}, {1, 5}.

Описание подзадач и системы оценивания

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

Примеры
Входные данные
5 5
1 2
2 3
3 4
3 5
4 5
Выходные данные
2 3
#113538
Вечеринка Петара
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Вечеринка Петара ]
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
32 megabytes

Петар организует вечеринку по случаю своего дня рождения и планирует пригласить некоторых сотрудников из компании, где он работает генеральным директором. Каждый сотрудник, включая Петара, имеет уникальный номер от 1 до N и тип шуток, которые он рассказывает, V i . Также, каждый сотрудник в компании кроме Петара имеет ровно одного начальника. Так как Петар - генеральный директор компании, он имеет номер 1 и руководит всеми сотрудниками (не обязательно напрямую).

На вечеринке есть некоторые правила, которым должны отвечать все присутствующие: 1. На вечеринке не должно быть двух людей с одинаковым типом шуток. 2. Человек не может быть приглашен на вечеринку, если на нее не приглашен его прямой начальник. 3. Человек не может быть приглашен на вечеринку, если типы шуток, которые рассказывает он и его приглашенные подчиненные, не образуют последовательное множество.

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

Последовательное множество - такое множество, в котором, если отсортировать его по возрастанию, разность между соседними элементами будет равна 1. Например (3, 1, 2) и (5, 1, 2, 4, 3) - последовательные множества, а (2, 5, 3) - нет.

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

Первая строка содержит одно целое число N ( 1 ≤ N ≤ 10000 ). Вторая строка содержит N целых чисел V i - типы шуток, рассказываемые i -м человеком ( 1 ≤ V i ≤ 100 ). Каждая из следующих N - 1 строк содержит два целых числа A и B ( 1 ≤ A , B ≤ N ), обозначающих что сотрудник с номером A является прямым начальником сотрудника с номером B .

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

Выведите единственное число - количество возможных наборов типов шуток на вечеринке.

Примеры
Входные данные
4
2 1 3 4
1 2
1 3
3 4
Выходные данные
6
Входные данные
4
3 4 5 6
1 2
1 3
2 4
Выходные данные
3
Входные данные
6
5 3 6 4 2 1
1 2
1 3
1 4
2 5
5 6
Выходные данные
10
#113554
Король Артур
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 2, Король Артур ]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вы наверняка слышали легенду о Короле Артуре и Рыцарях Круглого Стола. Практически все версии этой истории указывают на то, что круглость Круглого Стола тесно связана с верой Артура в равенство среди рыцарей. Это ложь! На самом деле выбор Артура касательно формы стола вызван его детской травмой.

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

В этой задаче представим стол на координатной плоскости как квадрат с противоположными вершинами в точках (0, 0) и (10000, 10000), где палочкам соответствуют прямые отрезки, лежащие внутри квадрата. Предположим, что Артур сидит у края стола, прилежащего к оси X. Тогда уборка палочек со стола сводится к передвижению их к оси X, покуда они не упадут со стола. Ваша задача - определить порядок уборки палочек со стола, который соответствует условиям из предыдущего абзаца.

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

Первая строка содержит единственное целое число N ( 1 ≤ N ≤ 5000 ) - количество палочек на столе. Каждая из следующих N строк содержит 4 целых числа x 1 , y 1 , x 2 , y 2 ( 0 ≤ x 1 , y 1 , x 2 , y 2 ≤ 10000 ), обозначающих крайние точки палочек.

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

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

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