#3898

Два капитана

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

Источники: [ Личные олимпиады, Нижегородская олимпиада школьников, 2012, Задача F ]

Капитаны Флинт и Джек Воробей нашли клад и хотят поделить его. Клад находится в шкатулке и состоит из чётного числа драгоценных камней. Капитан Флинт оценил \(i\)-ый камень в \(a_i\) пиастров, а Джек Воробей — в \(b_i\) долларов. Теперь они действуют следующим образом. Джек Воробей достаёт из шкатулки два камня, после чего Флинт забирает себе один из них (естественно, тот, у которого больше \(a_i\)). Оставшийся камень достаётся Воробью. После этого Джек Воробей достаёт ещё пару камней, и так далее: каждым ходом Воробей достает из шкатулки два камня, Флинт забирает себе камень с большим \(a_i\), оставшийся камень достается Воробью.

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

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

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

Первая строка входного файла содержит одно целое число \(N\) — количество камней в кладе. Гарантируется, что \(N\) чётное и что \(2\leq N\leq 5000\). Далее следуют две строки по \(N\) целых чисел в каждой: сначала заданы все \(a_i\), потом — все \(b_i\). Гарантируется, что все \(a_i\) различны (т.е. что действия Флинта всегда однозначно определены). Гарантируется, что все \(a_i\) и все \(b_i\) положительны и не превосходят \(400\,000\).

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

В выходной файл выведите \(N/2\) строк по два числа в каждой — пары камней, в том порядке, как их должен доставать из шкатулки Джек Воробей. Камни нумеруются начиная с 1.

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

Примечание

Среди тестов будут такие, в которых каждый камень оба капитана оценивают одинаково: \(a_i=b_i\) для каждого \(i\) (как во втором тесте из примера); суммарная стоимость таких тестов будет 40 баллов.

Примеры

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

6
6 10 11 18 5 14
1 7 6 12 15 16

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

5 1
2 3
6 4

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

6
6 44 2 43 7 48
6 44 2 43 7 48

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

3 1
5 4
2 6

#111134

Шахтеры

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

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

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

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

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

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

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

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

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

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

6
MBMFFB

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

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

16
MMBMBBBBMMMMMBMB

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

Подзадача 1.

\(1 \le N \le 27\). Решение оценивается в \(30\) баллов.

Подзадача 2.

Дополнительные ограничения отсутствуют. Решение оценивается в \(70\) баллов.

#111227

Ордынское войско

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

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2012, Задача H ]

Готовясь к бою, хан Гирей пронумеровал всех воинов своего войска натуральными числами от 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).

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

(оценивается в 40 баллов) 1 ≤ N ≤ 8.
(оценивается в 10 баллов) 9 ≤ N ≤ 10.
(оценивается в 10 баллов) N = 11.
(оценивается в 10 баллов) N = 12.
(оценивается в 10 баллов) N = 13.
(оценивается в 10 баллов) N = 14.
(оценивается в 10 баллов) N = 15.

Примеры

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

5
3
1 3 4

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

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

3
3
1 2 3

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

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

1
1
1

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

#111256

Простая арифметика

Темы: [Задача о рюкзаке]

Источники: [ Командные олимпиады, Барнаульские командные турниры, 2009, Задача I ]

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

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

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

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

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

Примеры

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

2009
20009

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

YES

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

10
000000050049000

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

YES

#111270

Поливальная машина

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

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2012, Лига А, Задача E ]

Город 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