Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 1657 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 200 201 202 203 204 205 206 >> Отображать по:
#2906
Форматирование текста
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Компания MacroHard разработала новый язык программирования PASCAL++. В этом языке имеется оператор вывода PrintLn, с помощью которого можно выводить строки любой длины. По стандарту языка, разработанному специалистами компании, некоторые комбинации символов в строке должны при выводе играть особую роль:

Комбинация Значение
\n Переход на новую строку
\t Вывод K пробелов (1 ≤ K ≤ 7), после чего курсор оказывается на позиции, имеющей номер вида 7N+1 (первая позиция каждой строки имеет номер 1).
\\ Вывод символа "\".
\XY, где X и Y – шестнадцатеричные цифры (0..9, A..F или a..f), причем \(XY \geq 20\) Вывод символа, имеющего ASCII код XY

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

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

Входной файл содержит одну или несколько строк, каждая из которых является результатом работы неправильного оператора PrintLn. Размер файла не превышает 100000 байт.

(Все символы "\", встречающиеся во входном файле участвуют в создании какой-либо ключевой комбинации, т.е. сразу после любой последовательности, состоящей из нечетного количества подряд идущих символов "\", следует символ из набора {"n", "t", "\", "0".."9", "A".."F", "a".."f" }, причем в случае символа из множества {"0".."9", A".."F", "a".."f"}, затем следует еще один символ из этого множества.)

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

Выведите в выходной файл, как выглядел бы данный текст, если бы он был преобразован по соответствующим правилам языка PASCAL++.

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

#2908
Гаджеты
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

Первая строка выходного файла должна содержать целое число 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
#2909
Функция Гранди
  
Функция Гранди на специфическом графе с одним циклом с подвешенными к нему поддеревьями. Если в цикле все вершины имеют одинаковое значение Гранди относительно поддеревьев для цикла нечетной длины ответ NO, а для четной - a, a+1, a, a+1... В противном случае ищем минимальное значение сосед которого, входящий в него, не минимален. Расставляем значения начиная с этого минимума.

Пусть G=(V, E) – произвольный ориентированный граф. Для каждой вершины x этого графа введем множество Next(x) как множество всех вершин, в которые ведут дуги, выходящие из вершины x.

Пусть F – функция, принимающая целые неотрицательные значения, определенная на вершинах графа G. Функция F называется функцией Гранди, если для каждой вершины x графа G выполняется условие F(x)=min{n≥0|n≠F(y) ни для какой вершины y из Next(x)}.

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

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

Входной файл содержит описание ориентированного графа. В первой строке файла находится целое число N (2 ≤ N ≤ 100000), равное количеству вершин графа. В i-й из следующих N строк находится одно целое число Pi (1 ≤ Pi ≤ N; Pi ≠ i), равное номеру вершины, из которой выходит та дуга, которая ведет в вершину с номером i.

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

Eсли для графа, описанного во входном файле, не существует функции Гранди, то выходной файл должен содержать одну строку со словом "NO". В противном случае, файл должен состоять из N строк, в i-й из которых должно быть записано одно целое число Fi – значение найденной функции Гранди для вершины с номером i. Если существует несколько функций Гранди для графа, описанного во входном файле, то выведите любую из них.

Примеры
Входные данные
4
2
4
4
1
Выходные данные
YES
Входные данные
3
3
1
2
Выходные данные
NO
Входные данные
4
4
3
2
1
Выходные данные
YES
#2910
Го
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Халява

Совсем недавно Али-Баба узнал от своего брата Касима об удивительной игре Го. В Го играют на прямоугольной доске – гобане, расчерченном вертикальными и горизонтальными линиями. Все линии пронумерованы. В игре участвуют два игрока, которые по очереди выставляют на гобан камни – специальные круглые фишки. Каждый камень ставится на незанятую точку пересечения линий доски (пересечения называют пунктами). У одного игрока – черные камни, у другого – белые. Камни одного цвета, смежные по вертикали, либо по горизонтали (но не диагонали), объединяются в группу. Одиночный камень также считается группой.

Один из способов набрать очки в Го – захватить камни противника. Каждый камень может иметь от двух до четырех смежных с ним пунктов (по вертикали и горизонтали, но не по диагонали). Если такой пункт не занят камнем, то он называется «дамэ». Дамэ группы – это все дамэ камней, составляющих группу. Как только оппонент своими камнями закрывает все дамэ чужой группы, то эта группа считается захваченной и снимается с доски. Если у группы осталось лишь одно дамэ, то говорят, что эта группа находится в «атари» т.е. на один шаг от захвата соперником.

Дамэ черных камней на рисунке отмечены крестиком. Группа черных из камней (1, 3) и (1, 4) имеет 4 дамэ. Группа (6, 1), (6, 2) и (6, 3) имеет одно дамэ и находится в атари. Черный камень (4, 5) также находится в атари. Помогите Али-Бабе, который всегда играет черными, определить, какие его группы находятся в атари.

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

Описание каждого теста начинается со строки, содержащей число N – размерность игровой доски (6 ≤ N ≤ 19). Далее следует N строк по N символов каждая. Каждый символ описывает один пункт доски. «B» означает черный камень, «W» – белый, «.» означает пустой пункт. Все группы на доске имеют хотя бы одно дамэ.

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

Выводите одно число – количество групп черных камней, находящихся в атари.

Примеры
Входные данные
9
.........
.........
.........
...WW....
...BW.B..
B..W.W...
B...WBW..
....WBW..
W....BW..
Выходные данные
2
Входные данные
6
WB.WBB
.B.W.B
..WW.W
WWW..W
..W...
BBW...
Выходные данные
1
#2911
Ковбои
  

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

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

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

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

В первой строке каждого теста находятся два целых неотрицательных числа N (0 < N < 1000) – количество поселений и M (0 ≤ M ≤ 100 000) – количество дорог, их соединяющих. Далее следует M строк, содержащих описание дорог. В i-й строке находятся два натуральных числа V и U (1 ≤ V, U ≤ N) – номера поселений, которые соединяет i-я дорога. Между двумя различными поселениями существует не более одной дороги, но может существовать несколько маршрутов. Нет дорог, которые образуют петлю, исходящую из поселения и ведущую в него же, не заходя в другие поселения. Не гарантируется, что существует маршрут между любой парой поселений. Маршрутом называется такая последовательность поселений s1-s2- … -sn, что любые два последовательных поселения si и si+1 соединены дорогой..

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

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

Примеры
Входные данные
6 6
1 2
2 3
1 3
4 5
5 6
4 6
Выходные данные
2
Страница: << 200 201 202 203 204 205 206 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест