Страница: << 50 51 52 53 54 55 56 >> Отображать по:
#111134
Шахтеры
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
512 megabytes

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

  • если вся еда была одинаковой — будет произведена одна тонна угля
  • если еды была двух типов — будет произведено две тонны угля
  • если трех типов — три тонны угля

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

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

Первая строка содержит число N (1 ≤ N ≤ 100 000) — количество поставок еды. Вторая строка содержит N символов — типы поставок в том порядке, в котором они будут осуществляться. Каждый из символов будет большой латинской буквой M (мясо), F (фрукты) или B (бублики).

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

Выведите единственное число — количество тонн угля, которое можно добыть.

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

Входные данные
6
MBMFFB
Выходные данные
12
Входные данные
16
MMBMBBBBMMMMMBMB
Выходные данные
29

Подзадача 1.
\(1 \le N \le 27\). Решение оценивается в \(30\) баллов.
Подзадача 2.
Дополнительные ограничения отсутствуют. Решение оценивается в \(70\) баллов.

#111145
Две подпоследовательности
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
256 megabytes

На уроке информатики Валерий изучал сжатие данных. Учитель рассказал новый метод, который мы сейчас вам опишем.

Пусть {a1, a2, ..., an} — данная последовательность строк, которую необходимо сжать. Здесь и далее будем считать, что все строки имеют одинаковую длину и состоят только из символов 0 и 1. Определим функцию сжатия:

  • f(пустая последовательность) = пустая строка
  • f(s) = s.
  • f(s1, s2) = наименьшая по длине строка, у которой один из префиксов равен s1, а один из суффиксов равен s2. Например, f(001, 011) = 0011, f(111, 011) = 111011.
  • f(a1, a2, ..., an) = f(f(a1, a2, an - 1), an). Например, f(000, 000, 111) = f(f(000, 000), 111) = f(000, 111) = 000111.

Перед Валерой стоит серьезная задача — разделить данную последовательность {a1, a2, ..., an} на две подпоследовательности {b1, b2, ..., bk} и {c1, c2, ..., cm}, m + k = n, так, чтобы величина S = |f(b1, b2, ..., bk)| + |f(c1, c2, ..., cm)| приняла минимально возможное значение. Здесь |p| обозначает длину строки p.

Обратите внимание, что запрещается менять относительный порядок строк в подпоследовательностях. Разрешается делать одну из подпоследовательностей пустой. Каждый элемент исходной последовательности должен принадлежать ровно одной из получившихся подпоследовательностей. Элементы подпоследовательностей b и c не обязательно должны идти подряд в исходной последовательности a, то есть они могут чередоваться (смотрите примеры 2 и 3).

Помогите Валере найти минимальное возможное значение S.

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

В первой строке входных данных содержится целое число n — количество строк (1 ≤ n ≤ 2·105). Далее в n строках даны элементы последовательности — строки длиной от 1 до 20 символов, состоящие только из символов 0 и 1. На i + 1 строке входных данных находится i-ый член последовательности. Элементы последовательности разделены исключительно символом перевода строки. Гарантируется, что все строки имеют одинаковую длину.

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

Выведите единственное число — минимально возможное значение S.

Примеры тестов
Входные данные
3
01
10
01
Выходные данные
4
Входные данные
4
000
111
110
001
Выходные данные
8
Входные данные
5
10101
01010
11111
01000
10010
Выходные данные
17
Примечание

Подробные ответы к тестам:

  • Оптимальный вариант: сделать одну из подпоследовательностей пустой, а вторую — равной всей данной последовательности. S = |f(01, 10, 01)| = |f(f(01, 10), 01)| = |f(010, 01)| = |0101| = 4.
  • Оптимальный вариант: b = {000, 001}, c = {111, 110}. S = |f(000, 001)| + |f(111, 110)| = |0001| + |1110| = 8.
  • Оптимальный вариант: b = {10101, 01010, 01000}, c = {11111, 10010}. S = |10101000| + |111110010| = 17.

Подзадача 1. N ≤ 10. Решение оценивается в 30 баллов.

Подзадача 2. N ≤ 1 000. Решение оценивается в 30 баллов.

Подзадача 3. Дополнительные ограничения отсутствуют. Решение оценивается в 40 баллов.

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

#111227
Ордынское войско
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Готовясь к бою, хан Гирей пронумеровал всех воинов своего войска натуральными числами от 1 до N. Поскольку воины умеют сражаться, но не умеют считать, при любом построении в шеренгу они выстраиваются в произвольном порядке. Одного или несколько воинов, стоящих в шеренге, будем называть отрядом. Отряд назовем правильным, если номера этих воинов в том порядке, в котором они стоят в шеренге, образуют упорядоченную по возрастанию последовательность чисел. Среди всех правильных отрядов хан Гирей выбирает ударный отряд – самый большой по количеству воинов. Так, в шеренге 1 3 2 4 из четырех воинов ударными являются отряды 1 3 4 и 1 2 4, а отряд 1 4 – один из правильных, но не ударный. Некоторые воины являются личными телохранителями хана Гирея. Требуется составить программу, определяющую количество таких шеренг, в которых телохранители хана образуют ударный отряд.

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

В первой строке входного файла задано натуральное число N – общее количество воинов (1 ≤ N ≤ 15). Во второй строке задано натуральное число K – количество телохранителей хана (1 ≤ K ≤ N). В третьей строке через пробел указаны K различных натуральных чисел, не превосходящих N, – номера телохранителей хана в порядке возрастания.

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

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

Примечание

В первом примере войско состоит из пяти воинов. Ударный отряд должен состоять из трех воинов с номерами 1, 3 и 4. Этому условию удовлетворяют следующие 11 шеренг: (1, 3, 2, 5, 4), (1, 3, 5, 2, 4), (1, 3, 5, 4, 2), (1, 5, 3, 2, 4), (1, 5, 3, 4, 2), (2, 1, 3, 5, 4), (2, 1, 5, 3, 4), (2, 5, 1, 3, 4), (5, 1, 3, 2, 4), (5, 1, 3, 4, 2), (5, 2, 1, 3, 4).

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

  1. (оценивается в 40 баллов) 1 ≤ N ≤ 8.

  2. (оценивается в 10 баллов) 9 ≤ N ≤ 10.

  3. (оценивается в 10 баллов) N = 11.

  4. (оценивается в 10 баллов) N = 12.

  5. (оценивается в 10 баллов) N = 13.

  6. (оценивается в 10 баллов) N = 14.

  7. (оценивается в 10 баллов) N = 15.

Примеры
Входные данные
5
3
1 3 4
Выходные данные
11
Входные данные
3
3
1 2 3
Выходные данные
1
Входные данные
1
1
1
Выходные данные
1
#111256
Простая арифметика
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Задана последовательность цифр. Определите, можно ли расставить между некоторыми из них знаки "+" и "-", так чтобы получилось заданное число \(M\), но никакие промежуточные вычисления не превосходили по модулю \(10000\).

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

Входные данные содержат две строки: в первой строке - натуральное число \(M\)≤\(20000\), во второй строке - последовательность цифр. Длина входной последовательности не превышает \(200\) символов.

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

Выведите одно слово YES или NO в зависимости от того, есть решение у задачи или нет.

Примеры
Входные данные
2009
20009
Выходные данные
YES
Входные данные
10
000000050049000
Выходные данные
YES
#111270
Поливальная машина
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
6 megabytes

Город N, в отличие от города M, расположен на склоне одного холма. Чистоту улиц этого города обеспечивает единственная поливальная машина. Бензин нынче дорог, поэтому движение муниципального транспорта «в гору» признано слишком расточительным.

Карта города представляет собой прямоугольник, разбитый на H × W клеток, где H и W — высота и ширина карты в клетках соответственно. Часть клеток заняты зданиями, остальные соответствуют улицам и площадям, которые и требуется помыть.

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

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

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

В первой строке входного файла находятся натуральные числа H и W — высота и ширина карты города (1 ≤ W ≤ 1 000, 1 ≤ H ≤ 1 000). В следующей строке расположено единственное натуральное число K — номер столбца клетки первой строки, в которой поливальная машина начинает движение (1 ≤ K ≤ W). Гарантируется, что эта клетка свободна от зданий.

Каждая из следующих H строк содержит W символов ‘|#|’ и ‘.’, означающих, соответственно, клетки со зданиями и без.

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

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

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

Входные данные
8 8
7
..#....#
##..#...
...#..#.
.##..#..
..#.#...
#.#.#...
#.#...##
##..####
Выходные данные
21 23

Страница: << 50 51 52 53 54 55 56 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест