Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTWPZ082 - PTwPZ Giełda

Giełda

Treść

Giełda papierów wartościowych to źródło zysków i strat finansowych niejednego obywatela czy instytucji. Zmienność i nieprzewidywalność kursów akcji niejednego gracza przyprawiły już o siwe włosy. Nie mniej jednak większość zainteresowanych twierdzi, że gra jest warta świeczki i potencjalne zyski rekompensują utracone zdrowie. Aby zmniejszyć ryzyko złego ulokowania środków, inwestorzy podpierają się analizą techniczną notowań oraz licznymi algorytmami przewidywania zmian kursów. Jednym z nich jest porównywanie historii najnowszych wyników notowań z danymi historycznymi. W metodzie tej należy odnaleźć najdłuższy ciąg notowań najnowszych (kończący się ostatnim notowaniem) pasujący do fragmentu notowań historycznych. Fragment notowań historycznych może zachodzić na ciąg notowań najnowszych. Przewidywanym kolejnym notowaniem będzie, według algorytmu, kolejna wartość z dopasowanego fragmentu notowań historycznych. W przypadku, gdy istnieje kilka fragmentów o takiej samej, maksymalnej długości, należy wziąć pod uwagę najnowszy z nich.

Spróbuj zaimplementować podany algorytm. Napisz program, który dla podanego ciągu notowań wyznaczy przewidywaną wartość kolejnego notowania. Kto wie, może kiedyś Ci się przyda.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Pierwszy wiersz zestawu danych zawiera całkowitą liczbę n (1<=n<=100 000) oznaczającą długość ciągu notowań. W drugim wierszu podane są wartości kolejnych notowań, od najstarszego do najnowszego. Wartości te reprezentowane są przez liczby całkowite, nie mniejsze niż 1 i nie większe niż 106, oddzielone pojedynczymi spacjami.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest przewidywana wartość kolejnego notowania lub liczba −1, gdy wartości tej nie da się wyznaczyć.

Przykład

dane wejściowe:
4
4
1 2 2 4
6
1 1 1 2 1 1
6
1 3 2 3 2 3
4
1 2 1 2

wynik:
-1
2
2
1


Dodane przez:Michael Suchacz
Data dodania:2009-07-24
Limit czasu wykonania programu:0.460s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ERL GOSU JS-RHINO NODEJS PERL6 VB.NET
Pochodzenie:Podlaski Turniej w Programowaniu Zespołowym
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.