Страница: 1 Отображать по:
#1229
Кафе
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Необходимо каждый день обедать в кафе. Для каждого дня задана цена обеда. Обедать можно за деньги или за купон. Купон можно получить, пообедав более чем на 100 рублей. Требуется определить способ оплаты, чтобы суммарная цена обедов была минимальна.

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

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

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

В первой строке входного файла записано целое число N (0≤N≤100). В каждой из последующих N строк записано одно целое число, обозначающее стоимость обеда в рублях на соответствующий день. Стоимость — неотрицательное целое число, не превосходящее 300.

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

В первой строке выдайте минимальную возможную суммарную стоимость обедов. Во второй строке выдайте два числа K1 и K2 — количество купонов, которые останутся неиспользованными у Пети после этих N дней и количество использованных им купонов соответственно.

В последующих K2 строках выдайте в возрастающем порядке номера дней, когда Пете следует воспользоваться купонами. Если существует несколько решений с минимальной суммарной стоимостью, то выдайте то из них, в котором значение K1 максимально (на случай, если Петя когда-нибудь ещё решит заглянуть в это кафе). Если таких решений несколько, выведите любое из них.

Примеры
Входные данные
5
35
40
101
59
63
Выходные данные
235
0 1
5
#1232
Скобки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Дана скобочная последовательность. Требуется определить минимальное количество скобок, которое необходимо добавить, чтобы она стала правильной скобочной последовательностью.

Назовем строку S правильной скобочной последовательностью, если она состоит только из символов '{', '}', '[', ']', '(', ')' и выполнено хотя бы одно из следующих трех условий:

1) S — пустая строка;

2) S можно представить в виде S=S1+S2+S3+...+SN (N>1), где Si — непустые правильные скобочные последовательности, а знак "+" обозначает конкатенацию (приписывание) строк;

3) S можно представить в виде S='{'+C+'}' или S='['+C+']' или S='('+C+')', где C является правильной скобочной последовательностью.

Дана строка, состоящая только из символов '{', '}', '[', ']', '(', ')'. Требуется определить, какое минимальное количество символов надо вставить в эту строку для того, чтобы она стала правильной скобочной последовательностью.

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

В первой строке входного файла записана строка, состоящая только из символов '{','}', '[',']', '(',')'. Длина строки не превосходит 100 символов.

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

Вывести в первую строку выходного файла единственное неотрицательное целое число — ответ на поставленную задачу.

Примеры
Входные данные
{(})
Выходные данные
2
Входные данные
([{}])
Выходные данные
0
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест