Matematické Fórum

Ahoj můžete mi někdo prosím pomoct s následujícím příkladem ? Cokoli co vás napadne :)
Děkuji

Definujme funkci f, která přiřařuje sekvencím celých čísel sekvence celých čísel následujícím způsobem:
sekvenci ⟨x1, x2, . . . , xn⟩ délky n přiřadí sekvenci ⟨y1, y2, . . . , ym⟩ délky m = n · (n − 1)/2,
přičemž sekvenci ⟨y1, y2, . . . , ym⟩ dostaneme tak, že vezmeme všechny dvojice čísel (xi,xj),
kde 1 ≤ i < j ≤ n, každou takovou dvojici čísel sečteme a výsledné hodnoty těchto m součtů seřadíme od nejmenšího po největší. (Pozn.: Všimněme si, že z n čísel můžeme vytvořit právě n · (n − 1)/2 dvojic.)

Navrhněte a detailně popište algoritmus s polynomiální časovou složitostí řešící následující problém:
Vstup: Číslo n a posloupnost ⟨y1, y2, . . . , ym⟩ tvořená celými čísly, přičemž m = n·(n−1)/2.
Výstup: Nějaká posloupnost ⟨x1, x2, . . . , xn⟩ celých čísel taková, že f(⟨x1,x2,...,xn⟩) = ⟨y1,y2,...,ym⟩, nebo informace, že žádná taková posloupnost neexistuje.

Poznámka: Funkce f není ani injektivní ani surjektivní. Pro danou posloupnost ⟨y1, y2, . . . , ym⟩ může tedy existovat více různých posloupností ⟨x1, x2, . . . , xn⟩ takových, že f(⟨x1, x2, . . . , xn⟩) = ⟨y1, y2, . . . , ym⟩, nebo nemusí existovat žádná. Pokud jich existuje více, stačí, když algoritmus najde jednu z nich.