Psevdorandom ədəd generatoru#9709

Psevdorandom ədəd generatoru

1 saniyə

128 meqabayt

Asan

Donald təbiəti sevir. O, proqramçı olaraq, ağacların böyüməsini simulyasiya etmək və realistik üçölçülü landşaftlar yaratmaq üçün proqramlar hazırlayır. Bu məqsədlər üçün Donalda etibarlı psevdorandom ədəd generatoru lazımdır. O, sonsuz bir ardıcıllıqda işarəsiz $40$ bitlik tam ədədləri yaratmaq üçün aşağıdakı metodu təklif edir.

m := 1 << 40 // = 2^40 = 1 099 511 627 776
S(0) := 0x600DCAFE // = 1 611 516 670
S(n + 1) := (S(n) + (S(n) >> 20) + 12345) % m

Sonuncu sətirdə $x >> 20$ x >> 20 əməliyyatı $x$ ədədinin $2^{20}$ 2^{20}-yə bölünməsindən yaranan tam hissəni göstərir, $x % m$ əməliyyatı isə $x$ ədədinin m-ə bölünməsindən alınan qalığı göstərir.

Psevdorandom ədəd generatorunun keyfiyyətini qiymətləndirmək üçün Donaldı ilk test olaraq bu ardıcıllıqla yaradılan ədədlərin cüt olma sayını hesablayıb, bu nisbətin $50%$ -ə nə qədər yaxın olduğunu yoxlamaq istəyir. Sizin köməyiniz bu məsələdə çox yerinə düşəcək.

Giriş

Bir tam ədəd $n (0 \leq n < 2^{63})$ n~(0 \le n < 2^{63}).

Çıxış

Bir tam ədəd çıxarılmalıdır — ardıcıllığın $S (0), S (1), ..., S (n - 1)$ S(0), S(1), ..., S(n - 1) elementləri arasında cüt olanların sayı.

Nümunələr

Nümunə 1

Nümunə 2