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.|

AL_14_08 - Generator liczb prawie pseudolosowych

Jasio zainteresował się niedawno problemem generowania przez komputer liczb losowych. Dowiedział się, że tak naprawdę, programy zwane PRNG, generują tylko liczby, które wydają się losowe, gdyż są one wyliczane przy użyciu pewnych funkcji matematycznych. Jasiek spróbował więc samodzielnie stworzyć taki generator i wymyślił następującą funkcję:

ai = |[(sin((i+ai-1)·b/c))2·d/e]+f·ai-1| mod |g|

gdzie:
sin(x) - sinus kąta x podanego w radianach;
[x] - największa liczba całkowita nie większa niż x;
|x| - wartość bezwzględna liczby x;
x mod y - reszta z dzielenia x przez y 

Następnie Jasio rozpoczął testy swojego generatora. Ustalał najpierw wartości parametrów b, c, d, e, f i g oraz liczby a(będącej tzw. "ziarnem"), a następnie generował ciąg k liczb od a1 do ak. Chłopiec zauważył, że bardzo dużo zależy od przyjętych wartości parametrów. Czasami uzyskiwał ciąg liczb, które wydawały się losowe, a czasami pewne liczby pojawiały się o wiele częściej niż inne.

Ponieważ to dopiero pierwsze próby z generatorem liczb pseudolosowych, Jasiek nie ma wielkich wymagań. Uznaje, że generator działający według przyjętego zestawu parametrów jest dobry, jeśli w wygerowanym ciągu, żadna z liczb nie pojawia się częściej niż wszystkie pozostałe razem wzięte (czyli nie występuje na ponad połowie pozycji w ciągu). Chłopiec chce teraz intensywniej przebadać swoją funkcję. Potrzebny jest mu więc program, który automatycznie sprawdzi, czy przy danych parametrach generator jest wystarczająco dobry.

Wejście

W pierwszej linii liczba przypadków testowych t (≤ ≤ 10).
W każdej z kolejnych t linii najpierw liczba k (0 < k2000000) oznaczająca ile liczb należy wygenerować, a następnie siedem liczb całkowitych: a0, b, c, d, e, f, g (-109a0, b, c, d, e, f, g109; c0; e0; g ≠ 0) - ziarno i parametry generatora.

Wyjście

Dla każdego przypadku testowego, w osobnej linii, napis "TAK", jeśli Jasio uzna generator za wystarczająco dobry. W przeciwnym wypadku napis "NIE", a po nim liczba, która wskazuje na to, że generator jest zły (czyli taka, która pojawiła się w wygenerowanym ciągu więcej niż k/2 razy).

Przykład

Wejście:
2
10 7 2 12 9 1 1 -4
10 0 1 2 5 3 -2 3
Wyjście:
NIE 3
TAK

Pomoc do przykładu: 
W pierwszym teście wygenerowane zostaną liczby: 3 3 1 1 3 3 3 3 2 1. Liczba 3 pojawia się 6 razy wśród 10 liczb.
W drugim teście wygenerowane zostaną liczby: 0 1 1 2 1 2 0 0 1 2. Tu żadna liczba nie występuje więcej niż 5 razy.


Dodane przez:Witold Długosz
Data dodania:2014-02-10
Limit czasu wykonania programu:1s-3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

ukryj komentarze
2014-02-15 21:38:47 ArGroc
Mógłbym prosić o out dla testu:
1
10 193643241 817077231 331722709 194874807 234270413 248782552 655779168
?

Ostatnio edytowany: 2014-02-15 21:38:57
2014-02-15 21:05:03 Ostry
sin powinien wystarczyć
2014-02-15 20:55:58 Thun
sin z math.h wystarcza czy trzeba szybszego?
2014-02-15 15:20:21 Witold D³ugosz
(sin(x))^2. Dodałem nawias we wzorze.

Ostatnio edytowany: 2014-02-15 15:27:42
2014-02-15 14:56:48 Jakub Staroñ
czy kwadrat we wzorze dotyczy wartosci sinusa czy argumentu?
tzn. czy jest to (sin(x))^2 czy sin(x^2)?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.