#111475

Обмен королей (O)

Темы: [Обход в ширину]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Муниципальный этап, Московская область, Очный этап, 2012, Задача D ]

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

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

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

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

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

В первой строке входных данных даны целые числа N и M (1 ≤ N, M ≤ 8) — размеры доски по вертикали и по горизонтали, соответственно. В следующих N строках даны M символов — состояние доски в начале игры. Символ «.» обозначает пустую клетку, символ «*» — недостижимую клетку, символ «W» — белого короля, «B» — черного короля. Гарантируется, что символы «W» и «B» встречаются на поле ровно по одному разу, и короли не находятся в соседних клетках изначально.

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

В выходной файл необходимо вывести минимальное количество ходов, которое потребуется для того, чтобы белый король поменялся местами с чёрным. В случае, если поменять королей местами невозможно, требуется вывести «Impossible» без кавычек.

Примеры тестов

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

4 3
*.*
W.B
...
*.*

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

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

2 3
W..
..B

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

Impossible

Примечание

Последовательность ходов, необходимая для обмена королей в первом тесте, приведена на рисунке:

$\text{[math]}$

#111485

Дубы

Темы: [Динамическое программирование по подстрокам]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Санкт-Петербург, 2008, Задача B ]

На аллее перед зданием Министерства Обороны в ряд высажены $n$ дубов. В связи с грядущим приездом главнокомандующего, было принято решение срубить несколько деревьев для придания аллее более милитаристического вида.

Внутренние распорядки министерства позволяют срубать дуб только в двух случаях:

* Если и ближайший дуб слева, и ближайший дуб справа строго ниже, чем данный дуб.

* Если и ближайший дуб слева, и ближайший дуб справа строго выше, чем данный дуб.

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

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

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

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

Первая строка входного файла содержит целое число $n$ — количество дубов, растущих на аллее ($2\le n \le 200$). Вторая строка содержит $n$ чисел — высоты дубов, приведенные слева направо. Высоты дубов — положительные целые числа, не превышающие 1000.

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

Если оставить последовательность дубов с неубывающими высотами невозможно, выходной файл должен содержать только одно число $-1$.

В случае, если искомый план существует, в первую строку выходного файла выведите целое число $m$ — минимальное количество дубов, которые необходимо срубить. В следующие $m$ строк выведите оптимальный план вырубки деревьев — номера дубов в том порядке, в котором их следует срубать, по одному номеру на строке.

Дубы нумеруются слева направо натуральными числами от $1$ до $n$.

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

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

В 50 баллов оценивается решение для случая, когда все высоты дубов попарно различны.

Примеры

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

5
3 2 4 8 5

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

2
2
4

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

5
4 5 5 5 6

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

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

6
1 1 3 3 2 2

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

-1

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

6
400 300 310 300 310 500

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

-1

#111488

Кастинг

Темы: [Пересечение множеств]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2013, 1 день, Задача A ]

В театре работает $n$ актеров. Известно, что среди них $a$ – высоких, $b$ – голубоглазых и $с$ – блондинов. Для главной роли в новом спектакле режиссеру требуется только один высокий голубоглазый блондин. Чтобы спланировать свое время для беседы с каждым таким артистом из труппы театра, режиссеру необходимо узнать, какое максимальное или какое минимальное количество артистов из работающих в театре подходит для этой роли.

Требуется написать программу, которая по заданным числам $n$, $a$, $b$ и $с$ определяет минимальное или максимальное количество актеров, с которыми режиссер должен переговорить.

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

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

1, если в данном теcте требуется определить минимальное количество актеров;
2, если в данном тесте требуется определить максимальное количество актеров.

Вторая строка входного файла содержит разделенные пробелами четыре целых числа: $n$, $a$, $b$, $с$ ($1 \leq n \leq 10 000$, $0 \leq a \leq n$, $0 \leq b \leq n$, $0 \leq c \leq n$).

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

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

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

Правильные решения для тестов, в которых требуется найти минимальное количество актеров, будут оцениваться из 50 баллов.

Правильные решения для тестов, в которых требуется найти максимальное количество актеров, будут оцениваться из 50 баллов.

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

Примеры

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

2
5 3 4 5

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

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

1
5 3 4 5

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

#111489

Города

Темы: [Двумерные массивы] [Жадный алгоритм]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2013, 1 день, Задача B ]

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

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

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

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

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

Первая строка входного файла содержит одно целое положительное число N, задающее размер игрового поля ($1 \leq N \leq 50$).

Последующие N строк содержат по $N$ заглавных латинских букв (без пробелов), кодирующих соответствующие клетки игрового поля: ‘C’ обозначает клетку, занятую городом, ‘D’ – пустую клетку. Гарантируется, что на поле есть хотя бы два города и всего их четное число.

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

Выходной файл должен содержать $N$ строк по $N$ цифр (без пробелов) в каждой, кодирующих соответствующие клетки. Цифра 1 обозначает, что данная клетка принадлежит первому государству, цифра 2 – данная клетка принадлежит второму государству. Если решений несколько, необходимо вывести любое из них.

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

Правильные решения для тестов, в которых всего два города, будут оцениваться из 40 баллов.

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

Примеры

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

3
DDD
DDC
DDC

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

111
111
112

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

5
DDDDD
CDCDC
DCCDC
DDDDD
DDDDD

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

#111490

A + B = C

Темы: [Динамическое программирование: последовательности]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2013, 1 день, Задача C ]

Часто для пробного тура на различных олимпиадах по информатике предлагается задача «A + B», в которой по заданным целым числам $A$ и $B$ требуется найти их сумму.

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

Пусть председатель жюри выбрал число $C$, запись которого состоит из $n$ десятичных цифр и не начинается с нуля. Теперь он хочет подобрать такие целые положительные числа $A$ и $B$, чтобы их сумма была равна $C$, и запись каждого из них также состояла из $n$ десятичных цифр и не начиналась с нуля. В дополнение к этому председатель жюри старается подобрать такие числа $A$ и $B$, чтобы каждое из них было красивым. Красивым в его понимании является число, запись которого не содержит двух одинаковых подряд идущих цифр. Например, число 1272 считается красивым, а число 1227 — нет.

Требуется написать программу, которая для заданного натурального числа $C$ вычисляет количество пар красивых положительных чисел $A$ и $B$, сумма которых равна $C$. Поскольку количество пар красивых чисел может быть большим, необходимо вывести остаток от деления этого количества на число $10^9+7$.

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

Входной файл содержит одно целое положительное число $C$. Число $C$ не начинается с нуля. Количество цифр в записи числа $С$ не превышает $10000$.

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

Выходной файл должен содержать одно целое число — остаток от деления количества искомых пар красивых чисел $A$ и $B$ на число $10^9+7$.

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

Правильные решения для тестов, в которых 1 ≤ C ≤ 999 (1 ≤ n ≤ 3), будут оцениваться из 25 баллов.

Правильные решения для тестов, в которых 1 ≤ C ≤ 999 999 (1 ≤ n ≤ 6), будут оцениваться из 50 баллов.

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

Пояснения к тестам

Число 22 можно представить в виде суммы двузначных чисел тремя способами: 10 + 12, 11 + 11, 12 + 10. Способ 11 + 11 не подходит, поскольку число 11 не является красивым. Следовательно, ответ для числа 22 равен 2.

Число 200 можно представить в виде суммы трехзначных чисел единственным способом: 100 + 100. Этот способ не подходит, поэтому ответ для числа 200 равен 0.

Число 1000 нельзя представить в виде суммы четырехзначных чисел, поэтому ответ для числа 1000 аналогично равен 0.

Примеры

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

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

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

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

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

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

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

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

Страница: << 259 260 261 262 263 264 265 >> Отображать по:

Выбрано

:

Отменить

|

Добавить в контест