Kody Qrey
Qrey Kodu adını Bell Telephone Laboratories-də çalışan fizik Frank Gray-dən almışdır. O, 1930-cu illərdə mövcud olan ağ-qara siqnalın ötürülməsi və alınması metodları ilə birlikdə rəngli televiziya siqnalının ötürülməsi üçün hazırda istifadə olunan bir metodu icad etmişdir; yəni, rəngli siqnal ağ-qara qəbuledici tərəfindən alındıqda, görüntü boz rəng çalarlarında göstərilir.
Qrey kodlarının bir çox fərqli variantları olsa da, yalnız birini nəzərdən keçirək: "ikili əks olunan (refleksiv) Qrey kodu". Adətən qeyri-müəyyən "Qrey kodu" deyildikdə bu kod nəzərdə tutulur.
Əks olunan ikili Qrey kodu aşağıdakı şəkildə qurulur. 0 və 1 rəqəmlərindən başlayırıq, bunlar müvafiq olaraq tam ədədləri 0 və 1 təqdim edir.
Bu rəqəmlərin siyahıdan sonra üfüqi ox ətrafında əksini götürək və siyahının yeni qeydlərinin sol tərəfinə 1, mövcud qeydlərin sol tərəfinə isə 0 yerləşdirək.
Beləliklə, n = 2 üçün əks olunan Qrey kodu əldə edilir. n = 3 üçün kodu əldə etmək üçün təsvir olunan proseduru təkrarlayırıq və əldə edirik:
Bu quruluş üsulu ilə induksiya ilə n-ə görə asanlıqla görmək olar ki, birincisi, hər bir 2n bit kombinasiyası siyahıda yalnız bir dəfə görünür; ikincisi, siyahıdakı bir elementdən yanındakı elementə keçərkən yalnız bir bit dəyişir; üçüncüsü, siyahının son elementindən birinciyə keçərkən yalnız bir bit dəyişir. Sonuncu xüsusiyyətə malik olan Qrey kodları dövri adlanır və əks olunan Qrey kodu mütləq belədir.
Hər bir verilmiş k ədədi üçün k-cı Qrey kodunun onluq dəyərini çıxarın.
Giriş məlumatları
Giriş faylında bəzi test məlumatları dəsti var, hər bir k ədədi (0 ≤ k ≤ 10^18) dəstdə ayrı bir sətirdə verilir. Bir testdəki məlumat dəstlərinin sayı 10^5-i keçmir.
Çıxış məlumatları
Hər bir verilmiş k ədədi üçün k-cı Qrey kodunun onluq dəyərini ayrı bir sətirdə çıxarın.