Hornerovo schéma
V této úloze máme za úkol načíst ze vstupu mnohočlen jedné proměnné x, souřadnice bodů, v nichž se bude vyhodnocovat, a poté provést tři akce. První akcí je vypsání mnohočlenu ve standardní formě, druhou akcí je vypsání mnohočlenu ve formě Hornerova schématu a třetí akcí je vyhodnocení daného mnohočlenu v daných bodech. Všechny hodnoty v této úloze jsou celočíselné, koeficienty mnohočlenu jsou také celočíselné. Nejprve uvedeme jednoduchý orientační příklad.Příklad 1
Na vstupu je následující textový soubor s pěti řádky:p(x) = x^2 - 2*x^3 - 5*x + x^3 - 2*x^4 + x^3 + 1 2 1 -1 0První řádek představuje zadaný mnohočlen, na dalších řádcích jsou hodnoty proměnné x, na každém řádku jedna. Výstupní textový soubor má podobu:
p(x) = -2*x^4 + x^2 - 5*x + 1 p(x) = 1+(-5+(1+(0-2*x)*x)*x)*x p(2) = -37 p(1) = -5 p(-1) = 5 p(0) = 1První řádek obsahuje zápis daného mnohočlenu ve standardním tvaru, druhý řádek obsahuje zápis téhož mnohočlenu v podobě Hornerova schématu a za nimi následují jednotlivé řádky s vypočtenými hodnotami mnohočlenu v jednotlivých zadaných bodech.
Specifikace vstupu
První řádek řádek obsahuje zadání mnohočlenu. Mnohočlen je uveden povinnou posloupností znaků p(x)<mezera>=<mezera>, za kterou následuje samotný mnohočlen. Mnohočlen je vždy neprázdnou (alespoň jednoprvkovou) posloupností členů, mezi každými dvěma členy je právě jedno znaménko plus ('+') nebo mínus ('-'), první člen může být předcházen výhradně znaménkem mínus. Člen je neprázdná posloupnost znaků, která obsahuje následující složky v uvedeném pořadí:faktor, což je celé nezáporné číslo,
znak násobení '*',
znak proměnné 'x',
znak exponentu '^',
exponent, což je celé nezáporné číslo.
Pokud je hodnota faktoru rovna 0, celý člen může (ale nemusí) v zápisu mnohočlenu chybět. Pokud je hodnota faktoru rovna 1, faktor spolu s následujícím znaménkem násobení mohou (ale nemusí) v zápisu členu chybět. Pokud je hodnota exponentu rovna 0, člen může (ale nemusí) obsahovat pouze faktor. Pokud je hodnota exponentu rovna 1, mohou (ale nemusí) v členu chybět znaménko exponentu a za ním následující znak 1. V zápisu mnohočlenu se mohou vyskytovat mezery v libovolném počtu a na libovolných pozicích (tedy i před ním nebo za ním), pouze se nesmí žádná mezera vyskytovat v zápisu žádného celého čísla (mezery mu však mohou předcházet nebo za ním následovat). Zápis mnohočlenu obsahuje nejvýše 10 000 členů, každý člen má exponent nejvýše 100.
Druhý řádek výstupu obsahuje zápis zadaného mnohočlenu v podobě Hornerova schématu. Předpokládejme, že mnohočlen p je definován
Zápis p v podobě Hornerova schématu má tvar
p(x) = a0 + (a1 + ... + (an-2 + (an-1 OP bn *x)*x)*x ... * x)*x,
kde bn = |an| a OP = '-', pokud |an| < 0, jinak OP = '+'.
Pokud je p mnohočlen prvního nebo nultého stupně, zápis neobsahuje žádné závorky. Zápis v této podobě je uveden povinnou posloupností znaků p(x)<mezera>=<mezera> a žádné další mezery neobsahuje.
Další řádky za prvním řádkem představují neprázdný seznam hodnot proměnné x (bodů na ose x) , v nichž se bude mnohočlen vyhodnocovat. Poslední hodnota seznamu je povinně nula. Na každém řádku je jedna hodnota, řádek může obsahovat úvodní nebo koncové mezery. Vstup neobsahuje žádné prázdné řádky. Velikost seznamu nepřesahuje 1 000 000 položek.
Specifikace výstupu
První řádek výstupu obsahuje standardní zápis zadaného mnohočlenu. Zápis je uveden povinnou posloupností znakůp(x)<mezera>=<mezera>. Zápis polynomu je opět posloupností členů uspořádaných v sestupném pořadí hodnot exponentů, pro každou hodnotu exponentu je v posloupnosti nejvýše jeden člen. Pokud je faktor některého členu nulový, člen se v zápisu mnohočlenu neuvádí. Výjimku tvoří případ, kdy je celý mnohočlen konstantně nulový, pak se zápis mnohočlenu skládá z jediného znaku 0 (nula). Jednotkové faktory (s výjimkou členu nulového stupně) včetně symbolu násobení se ve standardním zápisu neuvádějí. V členu odpovídajícímu jednotkovému exponentu, pokud je tento člen přítomen, není uveden znak exponentu a exponent sám. V členu odpovídajícímu nulovému exponentu, pokud je tento člen přítomen, je uveden pouze faktor. Mezi sousedními členy je zapsán vždy jediný znak operace sčítání (plus) nebo odečítání (mínus), před a za znakem operace je uvedena jedna mezera, v zápisu členu se mezery nevyskytují. Před prvním členem (s nejvyšší hodnotou exponentu) je znaménko mínus nenásledované mezerou, pokud je hodnota faktoru tohoto členu záporná. Je-li kladná, znaménko plus se neuvádí.
Další řádky obsahují hodnoty mnohočlenu jednotlivých bodech ve stejném pořadí, v jakém byly načteny ze vstupu. Na každém řádku je jedna hodnota mnohočlenu. Je zaručeno, že všechny hodnoty, vstupní i výstupní, padnou do intervalu <-10^9, 10^9>.
Formát řádku je p(<číslo1>)<mezera>=<mezera><číslo2>, kde <číslo1> je vstupní hodnota, <číslo2> je hodnota mnohočlenu v bodě <číslo1>. Poslední řádek výstupu může i nemusí být ukončen znakem konce řádku.
Vstupní soubor se čte ze standardniho vstupu (konzole, stdin), výstupní soubor se zapisuje do standardního výstupu (na konzoli, stdout).
Příklad:
Vstup:p(x) = - 13*x^28-12*x^ 47+ 19* x^78-15 * x ^ 73 + 1 * x ^56 +7*x ^ 62+ 20 *x ^59- 9 *x^75 + 19 *x^64 + 12* x ^ 5 1 -1 0Výstup:
p(x) = 19*x^78 - 9*x^75 - 15*x^73 + 19*x^64 + 7*x^62 + 20*x^59 + x^56 - 12*x^47 - 13*x^28 + 12*x^5 p(x) = 0+(0+(0+(0+(0+(12+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0 +(0+(0+(0+(0+(-13+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(0+(-12+( 0+(0+(0+(0+(0+(0+(0+(0+(1+(0+(0+(20+(0+(0+(7+(0+(19+(0+(0+(0+(0+(0+(0+(0+(0+( -15+(0+(-9+(0+(0+19*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x) *x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x) *x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x)*x) *x)*x)*x)*x)*x)*x p(1) = 29 p(-1) = 37 p(0) = 0(Řádky s vstupujícími/vystupujícími mnohočleny jsou v tomto textu zalomeny.)
Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.