Daimi bitlər
WhatNext şirkəti, 0-dan 65535-ə qədər olan aralıqda təsadüfi ardıcıllıqlar yaratmağı hədəfləyən ardıcıllıq generatorları hazırlayır. Bu ardıcıllıq dörd tam ədəd ilə təyin olunur: A, B, C və S, burada 1 ≤ A < 32768, 0 ≤ B < 65536, 2 ≤ C < 65536 və 0 ≤ S < C. S ardıcıllığın ilk elementi olaraq başlayır və hər bir növbəti element əvvəlkindən əldə edilir. Əgər X ardıcıllığın hər hansı bir elementidirsə, növbəti element belə hesablanır:
(A*X + B) % C
burada '%' qalıq alma əməliyyatını göstərir. Hər bir ardıcıllıq elementi 65536-dan kiçik olan 16-bitlik işarəsiz tam ədəddir. Lakin A*X + B aralıq nəticəsi daha böyük ola bilər, buna görə də hesablamalar 32-bitlik tam ədədlərlə aparılmalıdır.
Bəzi parametr dəyərləri daha yaxşı ardıcıllıqlar yaradır. WhatNext şirkətində ən pis ardıcıllıqlar, bir və ya bir neçə biti heç vaxt dəyişməyənlərdir. Ardıcıllıq boyunca heç vaxt dəyişməyən bit sabit bit adlanır. İdeal olaraq, ardıcıllıq sabit bitə malik olmamalıdır. Siz ardıcıllığı test etməli və hansı bitlərin sabit olduğunu müəyyən etməlisiniz.
Məsələn, A = 2, B = 5, C = 18 və S = 3 seçimi çox pis olacaq. Bu, 3, (2*3+5)%18 = 11, (2*11+5)%18 = 9, (2*9+5)%18 = 5, (2*5+5)%18 = 15, (2*15+5)%18 = 17, sonra isə (2*17+5)%18 = 3 ardıcıllığını yaradır və belə davam edir. Ardıcıllıq hər altı elementdən bir təkrarlanır:
Sonuncu sətir, bitlərin həmişə 0, həmişə 1 qaldığı və ya hər iki dəyəri qəbul etdiyi mövqeləri göstərir. Qeyd edək ki, 16 bitdən 12-si sabitdir. Yaxşı təsadüfi ardıcıllıqlar sabit bitlərə malik deyil, lakin əksinə doğru deyil. Məsələn, A = 1, B = 1, C = 64000 və S = 0 dəyərləri ilə əldə edilən ardıcıllıq sabit bitlərə malik deyil, lakin təsadüfi deyil: sadəcə 0-dan 63999-a qədər sayır və təkrarlanır. Ardıcıllıq mütləq ilk elementdən təkrarlanmalı deyil: A = 2, B = 0, C = 16 və S = 2 dəyərləri 2, 4, 8, 0, 0, 0, ... ardıcıllığını yaradır.
Giriş verilənləri
Giriş məlumatları birdən on altıya qədər testdən ibarətdir və bir 0 olan bir sətirlə bitir. Hər bir test, ondalık yazıda boşluqla ayrılmış tam ədədlər A, B, C və S olan tək bir sətirdən ibarətdir.
Çıxış verilənləri
Hər bir test üçün, hər biri ən əhəmiyyətli bitdən başlayaraq 16 bit üçün '1', '0' və ya '?' simvollarını ehtiva edən bir sətir çıxarın. '1' müvafiq bitin həmişə 1 olduğunu, '0' müvafiq bitin həmişə 0 olduğunu və '?' bitin ardıcıllıqda həm 0, həm də 1 dəyərlərini qəbul edə biləcəyini göstərir.