Напишите программу сложения, умножения и деления с остатком от разреженных многочленов, т.е. многочленов, для которых мы храним только ненулевые члены.
Разреженный многочлен определяется как последовательность пар (e,x)(e,x), где ee — показатель степени, а xx — соответствующий коэффициент. Пары перечислены в порядке убывания показателей, каждая на отдельной строке. Весь полином заканчивается линией -1 -1. Мы никогда не перечисляем пары с нулевыми коэффициентами, особенно нулевой полином представлен самой линией -1 -1.
Например полином 3x^5 - x^2 + 7 запишем так:
5 3
2 -1
0 7
-1 -1
Первая строка ввода говорит нам, какую операцию выполнять: add для сложения, mul для умножения или div для деления с остатком. В следующих строках вводятся два разреженных полинома.
Снова запишите результат операции в виде разреженного многочлена. Результатом операции div являются два многочлена: частное и остаток от деления. Обратите внимание, что при делении могут получиться нечетные числа; запишите их в виде дробей (мы рекомендуем использовать тип Fraction).
Например сложение Input:
add
6 1
4 3
3 -3
0 5
-1 -1
3 3
0 -3
-1 -1
Правильный Output:
6 1
4 3
0 2
-1 -1
Если бы операция была mul Output:
9 3
7 9
6 -12
4 -9
3 24
0 -15
-1 -1
И про деление div Output:
3 1/3
1 1
0 -2/3
-1 -1
1 3
0 3
-1 -1
Примечание: функции NumPy для работы с полиномами не подходят для этой задачи, так как не используют разреженное представление полиномов. Поэтому они слишком медленны для полиномов высокой степени с большим количеством нулевых членов.
