Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 4 задач <---
Источники --> Личные олимпиады --> Нижегородская олимпиада школьников
Страница: 1 Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

Игра будет состоять в том, что игрок будет управлять автобусом, перемещающимся по городу. В первой версии игры город будет представлять собой прямоугольное поле размера $N\times M$ клеток, каждая из которых либо занята зданием, либо свободна (т.е. по ней проходит дорога). Автобус игрока может перемещаться лишь по дорогам, но не по зданиям.

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

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

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

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

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

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

На первой строке входного файла находятся два числа $N$ и $M$ — количество строк и столбцов игрового поля соответственно ($1\leq N, M\leq 500$). Далее следуют $N$ строк, описывающих поле. В каждой строке находятся ровно $M$ символов, каждый из которых может быть или “#” (решётка, ASCII-код 35), или “.” (точка). Решётка обозначает клетку со зданием, точка — свободную клетку.

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

В выходной файл выведите $N$ строк по $M$ символов в каждой: для клеток, в которых находятся здания, выводите “#”, для клеток, где игрок может побывать не более одного раза — “X” (латинская заглавная буква X), для остальных клеток — “.”.

Примечание

Если ваша программа будет работать при $N,M\leq 100$, то вы получите как минимум 50 баллов.

Если ваша программа будет работать при $N,M\leq 250$, то вы получите как минимум 60 баллов.

Примеры
Входные данные
4 12
.#....#.##..
.##.#.#.##..
......####..
.##.#.#.####
Выходные данные
X#X...#X##..
X##.#.#X##..
XXX...####..
X##X#X#X####
Входные данные
3 2
##
##
##
Выходные данные
##
##
##
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

В секретном 240 отделе ИПФ РАН $N$ сотрудников и $N$ компьютеров. В отделе вводятся новые требования к секретности. В соответствии с этими требованиями, для каждого сотрудника будут определены ровно $K$ компьютеров, к которым этот сотрудник будет иметь допуск (т.е. за которыми этот сотрудник будет иметь право работать), причём так, что к каждому компьютеру будут иметь допуск ровно $K$ сотрудников.

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

Обратите внимание, что значение $K$ тоже будет известно лишь в последний момент. Из общих соображений секретности известно лишь, что $K$ будет равняться или 1, или 2, или 4; поэтому ваша программа должна уметь работать для любого из этих трех значений $K$.

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

В первой строке входного файла записаны натуральные числа $N$ и $K$ ($1\leq N \leq 500$). Далее следуют $KN$ строк, в каждой из которых записаны два натуральных числа — номер сотрудника и номер компьютера, к которому этот сотрудник имеет допуск.

Гарантируется, что каждый сотрудник имеет допуск ровно к $K$ компьютерам, что к каждому компьютеру ровно $K$ сотрудников имеют допуск, и что $K$ равно либо 1, либо 2, либо 4.

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

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

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

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

Выходные данные
3 1
1 2
2 3

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

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

ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

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

Система дорог в области устроена следующим простым образом. Есть $N$ населённых пунктов, некоторые из которых соединены дорогами. Между каждой парой пунктов существует не более одной дороги, и более того, для каждой пары населённых пунктов есть ровно один способ добраться из одного в другой (возможно, через промежуточные посёлки).

В каждом населённом пункте можно разместить ремонтную подстанцию. В принципе, фирма может размещать как крупные подстанции, которые даже в одиночку смогут обслуживать всю область, но при этом будут требовать больших расходов на содержание, так и небольшие станции, которые будут обслуживать лишь прилегающие населённые пункты, но при этом будут обходиться намного дешевле. Фирма уже определила, что каждую подстанцию можно характеризовать параметром “мощность”, которая может принимать значения, являющиеся целыми положительными числами (равна нулю мощность быть не может). Подстанция с мощностью $k$ будет обслуживать населённый пункт u, в котором она расположена, и все другие населённые пункты, до которых можно добраться из u, использовав не более k дорог (т.е. при $k$=1, например, подстанция обслуживает свой населённый пункт и все, которые напрямую соединены с ним дорогой). Стоимость содержания такой подстанции пропорциональна её мощности.

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

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

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

В первой строке входного файла находится одно число $N$ — количество населённых пунктов в области (1<=$N$<=300). Далее следуют $N$−1 строка, описывающая дороги. Каждая строка содержит два числа — номера населённых пунктов, которые соединяет эта дорога. Населённые пункты нумеруются от 1 до $N$.

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

В первую строку выходного файла выведите одно число — оптимальную суммарную мощность подстанций. Далее выведите $N$ чисел, описывающих какое-нибудь оптимальное решение. $i$-ое из этих чисел должно быть равно мощности подстанции, которую в вашем решении надо расположить в пункте $i$, или 0, если в населённом пункте $i$ не должна находиться подстанция.

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

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

ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Сеть компьютерных салонов «ХТТП» представлена в городе Н. двумя магазинами. Руководство Н-ского отделения сети решило реорганизовать витрины, на которых представлены ноутбуки. В каждом из двух магазинов на витрине должны быть представлены $N$ моделей ноутбуков, выставленные в ряд от касс вглубь помещения магазина. Маркетологи каждого из магазинов уже определили порядок, в котором на витрине должны быть расположены эти модели (эти порядки в двух магазинах, конечно же, могут быть разными).

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

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

Но при этом возникла проблема. По требованиям Федеральной антимонопольной службы, компьютерные салоны не должны предоставлять преимущества ни одной из операционных систем. Начальство сети «ХТТП» знает, как проходит проверка на соответствие этой норме законодательства. Инспектор антимонопольной службы идет по магазину начиная от касс вдоль витрины с ноутбуками, считает отдельно количество встреченных ноутбуков с Windows и Linux, а также модуль разности этих чисел (т.е. на сколько ноутбуков с одной системой он встретил больше, чем ноутбуков с другой системой). В некоторый момент он останавливается и говорит: «Ага!». Это значит: слишком у вас большой дисбаланс между операционными системами, поэтому платите штраф. Размер штрафа пропорционален разнице (взятой по модулю) количества ноутбуков с разными системами, которые увидел инспектор.

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

Например, пусть $N=5$: в магазинах должны быть выставлены пять моделей ноутбуков. Будем нумеровать модели ноутбуков от 1 до 5. Пусть в первом магазине маркетологи определили, что оптимальный порядок ноутбуков следующий (от касс вглубь зала):

2 4 1 3 5,

а во втором магазине —

3 1 2 5 4.

Тогда, если закупить ноутбуки моделей 1, 3 и 4 с операционной системой Windows, а 2 и 5 — с Linux, то порядок операционных систем в магазинах будет следующий (от касс вглубь зала):

L W W W L,

W W L L W.

Тогда, если, например, инспектор придет в первый магазин и просмотрит первые четыре ноутбука, то он скажет: «Ага!», и выпишет штраф за то, что он увидел Windows-ноутбуков на два больше, чем Linux. Аналогичный результат будет, если он придет во второй магазин и просмотрит только первые два ноутбука.

А если закупить ноутбуки 2 и 3 с системой Linux, а 1, 4, 5 — с Windows, то порядок операционных систем будет следующий:

L W W L W,

L W L W W,

и в какой бы магазин не пришел инспектор, и сколько бы ноутбуков он не посмотрел, разница Windows- и Linux-ноутбуков не будет превосходить по модулю 1, и это и будет оптимальным вариантом для руководства сети. (Напомним, что инспектор всегда начинает осмотр магазина от касс и идет вглубь магазина вдоль ряда с ноутбуками).

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

В первой строке входного файла записано одно число $N$ ($1\leq N\leq 10^5$) — количество моделей ноутбуков, которые должны быть представлены на витрине. Модели ноутбуков нумеруются от 1 до $N$.

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

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

В выходной файл выведите строку из $N$ символов, описывающих необходимую конфигурацию ноутбуков. А именно, $i$-ый символ должен быть “W” (без кавычек), если $i$-ую модель ноутбуков надо закупать с предустановленной системой Windows, и “L” для Linux.

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

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

Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест