Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Программа Последовательность дробей на С++

Kuzhi Moshi Ученик (92), на голосовании 1 год назад
Обыкновенная (или простая) дробь — запись рационального числа в виде +-m/n, или +-m/n, где n не равно 0.
Дана последовательность обыкновенных дробей. Необходимо найти сумму её элементов и длину её самой длинной строго возрастающей подпоследовательности.
Обыкновенную дробь и операции над ней реализовать в виде класса.
Формат ввода
Первая строка N - количество дробей в последовательности. N<10^5
Вторая строка - последовательность из N обыкновенных дробей в виде +-m/n, записанных через пробел.
Формат вывода
Первая строка - сумма элементов последовательности.
Вторая строка - длина самой длинной строго возрастающей подпоследовательности.
Пример 1
Ввод
3
1/2 -1/2 2/3
Вывод
2/3
2
Пример 2
Ввод
6
2/1 8/1 5/1 9/1 12/1 6/1
Вывод
42/1
4
Голосование за лучший ответ
Айран Просветленный (26757) 1 год назад
странно что примере 2:
6
2/1 8/1 5/1 9/1 12/1 6/1
длина самой длинной строго возрастающей подпоследовательности равна 4.
я вижу три: 5 9 12
https://rextester.com/IJT25817
Kuzhi MoshiУченик (92) 1 год назад
Возможно в примере считают, как 2 5 9 12, но это только мое предположение
Айран Просветленный (26757) Kuzhi Moshi, да, верно, это получается совсем другая задача. вот решение за n^2, хотя если применить динамическое программирование то можно и за n_logn
Kuzhi MoshiУченик (92) 1 год назад
А без буста получается нельзя решить или можно?
Айран Просветленный (26757) Kuzhi Moshi, реализовать самому данный класс.
Алексей Платонов Мастер (1031) 1 год назад
хренасе ты генератор идей 4 вопроса подряд
Похожие вопросы