Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

Выгодная покупка (30 баллов)

Автор задачи: Рогачева Е.В.

Задачу добавил: alef

Успешно сдано решений: 54

У NN выдался свободный день, который он решил посвятить путешествию по K лучшим книжным магазинам города MM (K >= 3). Ему хотелось приобрести книгу, которая была издана недавно и еще не "добралась" до его родного города. Принцип путешествия таков: переходя из магазина в магазин NN помнит только последние две цены (обозначим их С1 и С2). В очередном магазине он видит "текущую" цену (обозначим ее C3). Если текущая цена оказалась выше предыдущей, он расстраивается, а если C1 < C2 < C3, он расстраивается настолько, что прекращает свое путешествие. Если это не так, он надеется найти в дальнейшем лучшую цену и продолжает путешествие. Книгу он купит в последнем магазине, если доберется до него, и указанное выше условие не будет выполнено.
Надо выяснить, сколько существует маршрутов, заканчивающихся успехом (приобретением книги).

Формат входного файла input.txt
Первая строка - целое число K (3<=K<=20) - количество магазинов.
Вторая строка содержит K вещественных чисел с точностью 2 знака после запятой - цены на искомую книгу в магазинах.

Формат выходного файла output.txt
Целое число - число успешных маршрутов

Пример входного файла


Пример выходного файла

 

Сдать задачу

Задать вопрос жюри по этой задаче