Страница: << 24 25 26 27 28 29 30 >> Отображать по:
#1384
Репортаж
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Для N дней заданы высоты. Требуется выделить максимальное подмножество дней нечетной длины (2K+1), так что бы впервые K дней высота увеличивалась,на K+1 день был достигнут максимум, а в оставшиеся дни высота уменьшалась.

Группа альпинистов покорила много вершин и возвратилась в родной город. Одна из местных газет решила написать статью об их походе. Как выяснилось, в процессе похода альпинисты N раз останавливались на ночлег на той или иной высоте hi. Поскольку главный редактор газеты настаивает, чтобы название статьи было «Восхождение и спуск», решено было не упоминать о некоторых днях похода, рассказав лишь о 2k+1 дне, причем если статья будет рассказывать о x1-ом, x2-ом, …, x2k+1-ом (x1 < x2 < … < x2k+1)) дне, то должно выполняться условие hx1 < hx2 < … < hxk < hxk+1 > hxk+2 > … > hx2k+1 . Найдите максимальное k, для которого можно соответствующим образом выбрать 2k+1 день.

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

Первая строка входного файла содержит число N – количество дней в походе (1 ≤ N ≤ 100). Следующая строка содержит N целых чисел – h1, h2, …, hN (0 ≤ hi ≤ 104).

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

В первой строке выходного файла выведите число k. Затем выведите 2k+1 число - номера дней, репортаж о которых следует включить в статью, в возрастающем порядке. Если возможных ответов несколько, выведите любой.

Примеры
Входные данные
7
0 3 1 10 7 2 1
Выходные данные
2
1 2 5 6 7
Входные данные
4
1 2 3 4
Выходные данные
0
1
#1390
Симпатичные прямоугольники
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

Картина представляет собой прямоугольник N на M сантиметров, разделенный на маленькие квадратики 1 на 1 сантиметр со сторонами, параллельными сторонам картины. Для достижения гармонии каждый из этих квадратиков Вася покрасил одним из 26 особых цветов, обозначаемых маленькими латинскими буквами.

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

abc
acb

симпатичными являются все части, состоящие из одного квадратика (их 6), а также части

bc и a

cb и a

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

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

В первой строке содержатся два числа N и M (1 ≤ N, M ≤ 100). В следующих N строках идут строки, состоящие из M маленьких латинских символов. Символ в i-й строке j-м столбце определяет цвет соответствующего квадратика картины.

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

Выведите стоимость шедевра — количество частей, симметричных относительно своего центра.

Комментарии к примерам тестов

Этот пример разобран в условии

Симпатичными являются шесть частей 1x1, одна часть 1x2 и сама картина.

Частичные ограничения

Первая группа состоит из тестов, в которых N, M ≤ 15. Данная группа оценивается в 30 баллов.

Вторая группа состоит из тестов, в которых N, M ≤ 50. Данная группа оценивается в 30 баллов.

Примеры
Входные данные
2 3
abc
acb
Выходные данные
8
Входные данные
3 2
ab
cc
ba
Выходные данные
8
#1615
Замена робота
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан новый промышленный робот, максимальный срок службы которого не ограничен. Однако, все механизмы со временем теряют свою ценность, производительность и требуют больше затрат на ремонт. Известно, что затраты на обслуживание робота в \(i\)-м году от начала эксплуатации составляют \(C_i\), прибыль, которую приносит робот за \(i\)-й год своей работы составляет \(P_i\). Также в конце любого года можно продать старого робота и купить нового. Цена нового робота не зависит от времени и равна \(S\). Цена подержанного робота, прослужившего \(i\) лет равна \(R_i\). Определите оптимальный график замены роботов в течение \(N\) лет (то есть чтобы суммарная прибыль от использования была максимальна).

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

в первой строке вводятся числа \(N\) – расчетный период времени (натуральное, не превышает 100) и \(S\) (натуральное, не превышает \(10^5\)) – цена нового робота. В следующей строке указано \(N\) чисел (натуральные, не превышают 500) – затраты на обслуживание робота в течение соответствующего года. В следующей строке следует еще \(N\) чисел (натуральные, не превышают 500) - прибыль, которую приносит робот в соответствующие годы, затем еще \(N\) чисел (натуральные, не превышают 500) – цена подержанного робота, в зависимости от возраста.

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

Выведите максимальную прибыль, которую можно получить к концу \(N\)-го года, при оптимальной смене роботов.

Обратите внимание: рассматривается только операция замены робота. То есть если в конце \(N\)-го года вы решите продать робота, то это означает автоматическую покупку нового. То есть робот, проданный после расчетного периода чистой прибыли не приносит.

Комментарий

если робот работает 2 года без замены, то он приносит прибыли на 100+95=195 и требует 2+3=5 на обслуживание; если мы решим в конце 1-го года заменить робота на нового, то мы получим: 100+100=200 (новый робот будет приносить прибыль 100, так как работает 1-й года) + 90 (выручка от продажи старого робота) мы потеряем: 2+2=4 (новый робот также будет требовать затрат за свой первый год) -100 – уплатим за нового робота итого +200+90-100-4=186. Следовательно, первый вариант предпочтительнее

Примеры
Входные данные
2 100
2 3 
100 95
90 80
Выходные данные
190
#1623
Пицца
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вы решили заказать пиццу с доставкой на дом. Известно, что для клиентов, сделавших заказ на сумму более \(C\) рублей, доставка является бесплатной, при заказе на \(C\) рублей и меньше доставка стоит B рублей.

Вы уже выбрали товар, стоимостью \(A\) рублей. В наличии имеются еще \(N\) товаров стоимостью \(d_1\), ..., \(d_N\) рублей, каждый в единственном экземпляре. Их также можно включить в заказ.

Как потратить меньше всего денег и получить на дом уже выбранный товар в \(A\) рублей?

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

Сначала вводятся числа \(A\), \(B\), \(C\), \(N\), а затем \(N\) чисел \(d_1\), ..., \(d_N\).

Все числа целые, 1 ≤ \(A\) ≤ 1000, 1 ≤ \(B\) ≤ 1000, 1 ≤ \(C\) ≤ 1000, 0 ≤ \(N\) ≤ 1000, 1 ≤ \(d_i\) ≤ 1 000 000.

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

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

Примеры
Входные данные
10 17 25
5
2 7 5 3 7
Выходные данные
26
3 1 2 5
#1633
Пицца
  
ограничение по времени на тест
3.0 second;
ограничение по памяти на тест
64 megabytes

Вы решили заказать пиццу с доставкой на дом. Известно, что для клиентов, сделавших заказ на сумму более \(C\) рублей, доставка является бесплатной, при заказе на \(C\) рублей и меньше доставка стоит \(B\) рублей. Вы уже выбрали товара стоимостью \(A\) рублей. В наличии имеются еще \(N\) товаров стоимостью \(d_1, ..., d_N\) рублей, каждый в единственном экземпляре. Их также можно включить в заказ. Как потратить меньше всего денег и получить на дом уже выбранный товар стоимостью \(A\) рублей?

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

Вводятся сначала числа \(A, B, C, N,\) а затем \(N\) чисел \(d_1, ..., d_N\). Все числа целые, \(1 \le A \le 1000, 1 \le B ≤ 1000, 1 \le C \le 1000, 0 \le N \le 1000, 1 \le di \le 1 000 000\).

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

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

Примечание
В первом примере экономнее всего докупить 1, 2 и 5 товары. Во втором ничего докупать не надо, ведь доставка уже стала бесплатной. В третьем дешевле всего заплатить за доставку самому.
Примеры
Входные данные
10 17 25
5
2 7 5 3 7
Выходные данные
26
Входные данные
100 1 50
5
5 2 4 3 1
Выходные данные
100
Входные данные
10 14 25
5
2 7 5 3 7
Выходные данные
24
Страница: << 24 25 26 27 28 29 30 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест