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

PTWPZ092 - PTwPZ Generator

Problem A: Generator

Treść

Franek jest hakerem jakich mało. Nie raz już pokazał co jest wart, wykrywając luki w zabezpieczeniach stron internetowych, baz danych, czy w protokołach przesyłania informacji, które do tej pory były uznawane za całkowicie bezpieczne. Jego ambicją jest utworzenie takiego sposobu szyfrowania danych, który z założenia będzie odporny na wszelkie próby złamania. Franek wie, że kluczową rolę pełni tu jakość generatora liczb losowych. W pierwszym odruchu chciał użyć szeroko stosowanego liniowego generatora kongruencyjnego, którego schemat działania można opisać wzorem:

xi + 1 = (a xi + c) mod m

dla którego przy zadanych całkowitych współczynnikach m, a, c, x0 można w łatwy sposób obliczyć kolejne wartości xi. Niestety taki generator ma pewną wadę. Otóż dla zadanej wartości xi wartość xi + 1 będzie zawsze taka sama. Oznacza to, że jeżeli potencjalny włamywacz dysponuje odpowiednio dużą bazą historycznych wyników generatora, w łatwy sposób może przewidzieć kolejną obliczoną przez generator liczbę. Dlatego też Franek postanowił wprowadzić małą modyfikację. Jego generator jest złożeniem kilku różnych generatorów liniowych, według następującego wzoru:

y1,i + 1 = (a1 y1,i + c1) mod m1
y2,i + 1 = (a2 y2,i + c2) mod m2


yg,i + 1 = (ag yg,i + cg) mod mg
xi + 1 = (y1,i + 1 + y2,i + 1 + … + yg,i + 1) mod M

Teraz Franek chciałby tak dobrać współczynniki swojego generatora, by otrzymywane wartości powtarzały się jak najrzadziej, inaczej mówiąc, by rozkład wyników był jak najbardziej zbliżony do rozkładu jednostajnego. Napisz program, który umożliwi przeprowadzenie niezbędnych testów i dla zadanych współczynników mj, aj, cj, yj,0, M oraz liczby wywołań generatora wyznaczy wartość, która jest generowana najczęściej, oraz liczbę jej powtórzeń.

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 liczbę całkowitą g (1<=g<=10) oznaczającą liczbę generatorów liniowych wchodzących w skład generatora Franka. W kolejnych g wierszach podane są liczby całkowite mj, aj, cj, yj,0 (2<=mj<=232, 0<aj<mj, 0<=cj<mj, 0<=yj,0<mj), oddzielone pojedynczymi spacjami, reprezentujące współczynniki j-tego generatora liniowego. Ostatnia linia zestawu danych składa się z dwóch liczb całkowitych M, n (2<=M<=232, 1<=n<=2 000 000), oddzielonych spacją, oznaczającymi odpowiednio współczynnik M generatora Franka oraz liczbę wywołań podczas testu.

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 są dwie liczby całkowicie oddzielone spacją, oznaczające kolejno najczęściej generowaną wartość oraz liczbę jej wystąpień. W przypadku gdy kilka wartości powtarza się jednakową (maksymalną) liczbę razy, należy podać najmniejszą z nich.

Przykład

dane wejściowe:
2
1
4 1 1 2
4 9
2
16 5 7 1
32 7 17 6
12 20

wynik:
3 3
1 5


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