Герой известного мультсериала Колыван решил построить себе бассейн. Поскольку он очень скуп, он пытается использовать уже имеющееся строение.
Строение представляет собой абсолютно ровный коридор единичной ширины, в котором имеется N перегородок. Если расположить ось Х вдоль коридора, все перегородки будут находиться точно в ее целочисленных координатах с шагом 1, причем по ширине перегородки занимают весь коридор, а высоты могут отличаться. Создаваемый бассейн должен иметь максимально большой возможный объем при условии, что из всех имеющихся перегородок нужно оставить только две и увеличивать их высоту запрещено.
Формат ввода/вывода.
Программа flooding считывает с клавиатуры (стандартного устройства ввода) целое число N (2<=N<=105) – количество перегородок. Затем считывается N целых чисел аi (1<=аi<=109) – высоты перегородок.
Программа flooding выводит на экран (стандартное устройство вывода) единственное число – максимальный объем создаваемого бассейна при описанных ограничениях.
Пример входных и выходных данных.
|
Ввод |
Вывод |
|
4 1 2 1 3 |
4 |
Задача Фазенда (hacienda).
Для своей приятельницы бабы Яги Колыван решил построить фазенду в лесу. Баба Яга очень любит треугольники и поэтому Колыван хочет, чтобы участок для фазенды был треугольной формы с деревьями в вершинах. Поскольку баба Яга не хочет наносить вред природе и рубить лес, Колывану необходимо найти такие три дерева, чтобы внутри ограды не было других деревьев.
Чтобы иметь возможность выбора, Колывану нужно знать, сколько всего в лесу имеется таких участков.
Формат ввода/вывода.
Программа hacienda считывает с клавиатуры (стандартного устройства ввода) целое число N (3<=N<=200) – количество деревьев в лесу. Затем считывается N пар целых чисел xi,yi (|xi|,|yi|<=105) – координаты деревьев в лесу, причем никакие три дерева не находятся на одной прямой.
Программа hacienda выводит на экран (стандартное устройство вывода) единственное число – количество треугольных участков, не содержащих ни единого дерева.
Пример входных и выходных данных.
|
Ввод |
Вывод |
|
5 -9 -10 0 4 8 8 -1 10 1 -7 |
8 |
Задача Хитрый палиндром (pal333).
После выбора участка и разработки проектов строительства бассейна и фазенды Колыван получил смету на выполнение строительных работ. С учетом изменения курса доллара сумма получилась очень внушительной и Колыван, чтобы успокоиться, решил определить, является ли эта сумма палиндромом, т.е. таким числом, которое читается в обоих направлениях одинаково. Затем Колыван задался вопросом, а сколько существует способов получить палиндром из заданной последовательности цифр, удаляя из нее некоторое, возможно пустое, множество цифр. Наконец, он решил еще больше усложнить себе задачу и найти среди них все числовые палиндромы, которые делятся на число 333. Помогите ему решить эту задачу.
Формат ввода/вывода.
Программа pal333 считывает с клавиатуры (стандартного устройства ввода) целое число N (1<=N<=100) – количество цифр числа. Затем считывается N цифр.
Программа pal333 выводит на экран (стандартное устройство вывода) единственное число – количество способов получения чисел-палиндромов, делящихся на число 333, из заданной последовательности цифр. Ответ должен быть выведен по модулю 10007. Палиндром может начинаться с ведущих нулей.
Пример входных и выходных данных.
|
Ввод |
Вывод |
|
6 303330 |
8 |
Пояснение к примеру: из заданной последовательности цифр можно получить такие палиндромы, кратные 333: 0 (1-й ноль), 0 (2-й ноль), 00, 333 (1-я, 2-я и 3-я тройки), 333 (1-я, 2-я и 4-я тройки), 333 (1-я, 3-я и 4-я тройки), 333 (2-я, 3-я и 4-я тройки), 03330.