Matematické Fórum

Ahoj, pomozte napsat program, prosim:


Jsou dány dva řídké polynomy jedné proměnné P a Q. Vašim úkolem je spočítat jejich podíl a zbytek po dělení. Při výpočtech smíte používat pouze celočíselnou aritmetiku.

Každý polynom je v souboru uložen jako několik po sobě jdoucích řádků. Na každém řádku se nachází dvojice čísel e a k, kde e představuje exponent a k příslušný koeficient. Polynom je zakončen řádkém, na kterém se nachází jediné číslo -1. Koeficienty jsou celočíselné, vejdou se do 32-bitového integeru a všechny jsou nenulové. Exponenty jsou rovněž celočíselné a jsou ≥ 0. Polynom je navíc setříděn sestupně podle exponentů.

Vstup je uložen v souboru polynomy.in. Polynomy P a Q jsou zde uloženy za sebou ve výše uvedeném formátu.

Výstup uložte do souboru polynomy.out a to opět ve výše uvedeném formátu. Nejprve uložte výsledek a následně zbytek po dělení. Při výpočtech se může stát, že koeficienty jednotlivých členů nevyjdou celočíselně, ale protože vstup celočíselný je, určitě si vystačíme s racionálními čísly. Takovýto koeficient uložte do výstupu ve tvaru zlomku v základním tvaru: např 2/5 (pozor - např. 3/6 je špatně, neboť zlomek lze zkrátit na 1/2). Pokud vyjde nějaký koeficient celočíselný, uložte jej jako celé číslo (ne jako zlomek).

Hint: Pro práci s řidkými polynomy použijte lineární spojové seznamy.
Příklad:
polynomy.in
  5 3
  2 2
  1 4
  0 1
  -1
  3 2
  2 1
  -1
polynomy.out
  2 3/2
  1 -3/4
  0 3/8
  -1
  2 13/8
  1 4
  0 1
  -1