Страница: << 1 2 3 4 Отображать по:
#3583
Башня
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятия башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен.

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

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

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

В первой строке входного файла содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1 ≤ K ≤ N ≤ 100 000). Далее на следующей строке содержатся N целых чисел, обозначающих Ai (1 ≤ Ai ≤ 106).

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

На первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни.

Примеры
Входные данные
1 1
1
Выходные данные
1
1
Входные данные
2 1
1 1000000
Выходные данные
2
1 2
Входные данные
8 3
1 2 3 4 1 6 7 8
Выходные данные
2
2 6
#3588
Башня
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Вскоре ему стало интересно, насколько его крепость защищена от жуликов и воров. Для этого он ввел понятия башни. Башней называется любая последовательность из K столбиков подряд (где K — любимое число Пети). Защищенность башни определяется как суммарная высота всех столбиков этой башни (чем она больше, тем громаднее и ужаснее она кажется), умноженная на минимум высоты столбиков башни (т.к. враги, очевидно, будут пытаться проникнуть через самое слабое место башни). Неприступность крепости определяется как сумма защищенностей каждой из башен.

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

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

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

В первой строке входного файла содержатся число N — количество столбиков в крепости и число K — любимое число Пети (1 ≤ K ≤ N ≤ 1000). Далее на следующей строке содержатся N целых чисел, обозначающих Ai (1 ≤ Ai ≤ 103).

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

На первой строке выведите число Q — количество башен в оптимальном разбиении. Далее выведите Q чисел — номера первых столбиков каждой башни.

Гарантируется, что в оптимальном разбиении неприступность крепости не превосходит 2 × 109.

Примеры
Входные данные
1 1
1
Выходные данные
1
1
Входные данные
2 1
1 1000
Выходные данные
2
1 2
Входные данные
8 3
1 2 3 4 1 6 7 8
Выходные данные
2
2 6
#3590
Палиндромика
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

Выведите номер игрока, который победит в игре (число 1 или 2) при оптимальной игре каждого из игроков.

Примеры
Входные данные
3
uho
Выходные данные
1
Входные данные
6
ababab
Выходные данные
2
#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

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