Rəqəmsal Məzmunun Qorunması
Dan rəqəmsal məzmunun qorunması üzrə bir şirkətdə çalışır və bu şirkət Anti Content Misuse (ACM) adlanan standart əsasında blu-ray disklərin məzmununun qorunmasına cavabdehdir.
ACM standartı belə işləyir: Tutaq ki, 2^n blu-ray sürücüsü/pleyer var. Bu 2^n sürücüləri n hündürlüyündə tam ikili ağacın yarpaqları kimi təsvir edilir, belə ki, hər bir kökdən yarpağa yol n kənardan ibarətdir. Bu ikili ağacda hər bir u düyünə bir identifikator nömrəsi təyin edilir və təsadüfi açar k_u saxlayır. İdentifikator nömrələri belə təyin edilir: Kök, r, 1 nömrəsi ilə təyin edilir. Bundan əlavə, nömrəsi i olan daxili düyünün sol və sağ övladları müvafiq olaraq 2i və 2i+1 nömrələri ilə təyin edilir. Bu sxem ağacdakı hər bir düyünə fərqli nömrə təyin edir. Düyünlərdə saxlanan açarlar blu-ray istifadəçilərinə məlum deyil, lakin blu-ray sürücü istehsalçılarına məlumdur. Hər bir blu-ray pleyer ağacdakı müvafiq yarpağının identifikator nömrəsi i (2^n ≤ i ≤ 2^{n+1}−1) ilə təyin edilir. Blu-ray sürücüsü istehsalçısı kökdən i nömrəli yarpağa qədər olan yoldakı düyünlərlə əlaqəli açarları i nömrəli pleyerə yerləşdirir.
Blu-ray diskinin məzmununu şifrələmək üçün məsul şirkət master açar adlanan təsadüfi açar k yaradır. Əvvəlcə, k açarını k_r açarı ilə şifrələyir (xatırlayın ki, r ikili ağacın kök düyünüdür) və onu diskə başlıq kimi yazır. Sonra, məzmunu k ilə şifrələyir və şifrələnmiş məlumatı blu-ray diskə yazır. Blu-ray sürücüsü əvvəlcə başlığı içində yerləşdirilmiş k_r açarı ilə deşifrə edir və master açar k bərpa edir, sonra isə məzmunu k açarı ilə deşifrə edir.
Təəssüf ki, bir sıra blu-ray sürücülərində yerləşdirilmiş açarlar, R, hakerlər tərəfindən ifşa edilir və internetdə yayımlanır. Nəticədə, master açar k bu ifşa edilmiş açarlardan heç biri ilə şifrələnə bilməz. Məsələn, bütün blu-ray sürücüləri k_r açarını ehtiva etdiyindən, yuxarıdakı şifrləmə sxemi artıq işləmir. ACM standartında bu vəziyyət üçün bir həll yolu nəzərdə tutulmuşdur. Daha böyük bir başlıq hesabına, sənaye yeni blu-ray diskinin məzmununu təhlükəsiz şəkildə şifrələyə bilər. Onlar diqqətlə ikili ağacda ifşa edilməmiş açarların K alt çoxluğunu seçirlər ki, R dəki sürücülər istisna olmaqla, bütün blu-ray sürücüləri K açarlarından ən azı birinə malik olsun. Onlar master açar k hər bir k' K açarı ilə şifrələyir və nəticəni başlığa yerləşdirirlər (yəni başlıqda |K| şifrlənmiş mətn var). İndi hər bir aktiv blu-ray sürücüsü başlıqdakı şifrlənmiş mətnlərdən ən azı birini deşifrə edə bilər və master açar k bərpa edə bilər. Dan sizdən verilmiş hack edilmiş sürücülərin identifikatorları ilə minimum kardinalitetli (ən kiçik başlıqla nəticələnən) K açarlarının alt çoxluğunu müəyyən etməyə kömək etməyinizi istəyir.
Giriş verilənləri
Giriş bir testdən ibarətdir. Test iki sətirdən ibarətdir. Birinci sətir iki tam ədəd n və |R| ehtiva edir, burada 1 ≤ n ≤ 62 və 1 ≤ |R| ≤ 1000. |R| ifşa edilmiş sürücülərin çoxluğunun, R, kardinalitetidir. İkinci sətir ifşa edilmiş blu-ray sürücülərinin identifikatorları olan |R| tam ədəd ehtiva edir. Ən azı bir hack edilməmiş blu-ray sürücüsünün olduğunu qəbul edə bilərsiniz.
Çıxış verilənləri
Yuxarıda göstərilən tələblərə cavab verən və minimum kardinalitetə malik olan K açarlarına uyğun düyünlərin identifikatorlarını artan sırada və tək boşluqlarla ayrılmış şəkildə göstərin.