Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 6 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Региональный этап --> Кировская открытая областная олимпиада
    2003(6 задач)
    2004(7 задач)
    2005(8 задач)
Страница: << 1 2 Отображать по:
#1669
Отчет
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Заданы две последовательности чисел: объем продукции и процент брака. Требуется найти наибольшую подпоследовательность, в которой объем продукции растет, а процент брака падает.

Один из цехов завода производит продукцию в течение \(N\) месяцев. Начальнику цеха было поручено составить отчет о росте производительности данного цеха и об уменьшении доли некачественной продукции в процентном соотношении (точность доли процента до одного знака после запятой, например, 2/7=0.(285714) ≈ 28.6%). При этом в отчет должна войти информация как можно за большее число месяцев \(K\) (\(K\) ≤ \(N\)) работы цеха. Начальник цеха решил, что он включит в отчет данные только по тем месяцам (не обязательно взятым подряд, но обязательно в хронологическом порядке), по которым наблюдается строгий рост количества производимой продукции и строгий спад доли бракованных товаров по сравнению с данными предыдущего месяца, вошедшего в отчет. Определить, какое максимальное количество месяцев удовлетворяет этим условиям и сколько есть возможных вариантов составления отчета.

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

Первая строка файла содержит число \(N\) (1 ≤ \(N\) ≤ 40) - количество месяцев работы цеха. Далее следует N строк, содержащих целые числа \(v_i\) (1 ≤ \(v_i\) ≤ 10000) и \(b_i\) (1 ≤ \(b_i\) ≤ \(v_i\)); \(v_i\) - объем продукции, произведенной цехом за \(i\)-ый месяц; \(b_i\) - количество бракованной продукции в \(i\)-ом месяце.

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

Первая строка файла содержит число \(K\) - количество месяцев, по которым будет включена в отчет информация о работе цеха. Вторая строка содержит число \(P\) - количество возможных вариантов составления отчета с максимальным содержанием.

Примеры
Входные данные
10
313 100
313 106
442 106
442 104
475 104
475 102
539 102
539 109
682 109
682 111
Выходные данные
5
32
Страница: << 1 2 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест