Страница: << 109 110 111 112 113 114 115 >> Отображать по:
#111485
Дубы
  

На аллее перед зданием Министерства Обороны в ряд высажены \(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
Выходные данные
0
Входные данные
6
1 1 3 3 2 2
Выходные данные
-1
Входные данные
6
400 300 310 300 310 500
Выходные данные
-1
#111486
Палиндромность
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Напомним, что палиндромом называется строка, которая читается одинаково как слева направо, так и справа налево. Например, палиндромами являются строки “abba” и “madam”.

Для произвольной строки \(s\) введем операцию деления пополам, обозначаемую \(half(s)\). Значение \(half(s)\) определяется следующими правилами:

Если \(s\) не является палиндромом, то значение \(half(s)\) не определено;

Если \(s\) имеет длину 1, то значение \(half(s)\) также не определено;

Если \(s\) является палиндромом четной длины \(2m\), то \(half(s)\) — это строка, состоящая из первых \(m\) символов строки \(s\);

Если \(s\) является палиндромом нечетной длины \(2m+1\), большей \(1\), то \(half(s)\) — это строка, состоящая из первых \(m + 1\) символов строки \(s\).

Например, значения \(half(\mbox{inforamatics})\) и \(half(\mbox{i})\) не определены, \(half(\mbox{abba}) = \mbox{ab}\), \(half(\mbox{madam}) = \mbox{mad}\).

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

Например, палиндромность строк “informatics” и “i” равна 0, так как к ним нельзя применить операцию деления пополам даже один раз. Палиндромность строк “abba” и “madam” равна 1, а палиндромность строки “totottotot” равна 3, поскольку операция деления пополам применима к ней три раза: “totottotot” → “totot” → “tot” → “to”.

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

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

В первой строке входного файла содержатся три целых числа \(n\), \(p\) и \(k\) — длина и палиндромность строк рассматриваемого множества и номер искомой строки в этом множестве (\(1 \le n \le 200\); \(0 \le p \le 8\); \(1 \le k \le 10^9\)).

Гарантируется, что в множестве строк длины \(n\) с палиндромностью \(p\) содержится не менее \(k\) элементов, то есть искомая строка существует.

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

В выходной файл выведите \(k\)-ю в алфавитном порядке строку из множества строк длины \(n\) с палиндромностью \(p\).

Примеры
Входные данные
4 1 1
Выходные данные
abba
Входные данные
10 3 490
Выходные данные
totottotot
Входные данные
5 0 6597777
Выходные данные
olymp
#111488
Кастинг
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В театре работает \(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
Выходные данные
3
Входные данные
1
5 3 4 5
Выходные данные
2
#111489
Города
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Юный программист решил придумать собственную игру. Игра происходит на поле размером \(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
Выходные данные
11111
11111
12222
22222
22222
#111490
A + B = C
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Часто для пробного тура на различных олимпиадах по информатике предлагается задача «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.

Примеры
Входные данные
22
Выходные данные
2
Входные данные
200
Выходные данные
0
Входные данные
1000
Выходные данные
0
Входные данные
239
Выходные данные
16
Страница: << 109 110 111 112 113 114 115 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест