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
странно что примере 2: 6 2/1 8/1 5/1 9/1 12/1 6/1 длина самой длинной строго возрастающей подпоследовательности равна 4. я вижу три: 5 9 12 https://rextester.com/IJT25817
Возможно в примере считают, как 2 5 9 12, но это только мое предположение
Айран
Просветленный
(26757)
Kuzhi Moshi, да, верно, это получается совсем другая задача. вот решение за n^2, хотя если применить динамическое программирование то можно и за n_logn
Дана последовательность обыкновенных дробей. Необходимо найти сумму её элементов и длину её самой длинной строго возрастающей подпоследовательности.
Обыкновенную дробь и операции над ней реализовать в виде класса.
Формат ввода
Первая строка 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