# coding=utf-8 # Často pracujeme s binárními operacemi, pojďme si v nich udělat pořádek: # >> je bitový posun doprava, které vezme číslo v binárním zápise a posune jej doprava # např. 54 >> 2 vezme 54 (110110) a posune o dva doprava, dostane 13 (1101) # << je bitový posun doleva, to samé jako doprava, zprava přidává nuly # např. 13 << 2 vezme 13 (1101) a zprava doplní dvě nuly, dostane 52 (110100) # & je bitový `and`, vezme bitový zápis dvou čísel a nechá jedničky tam kde obě čísla měla jedničky # např. 54 (110110) & 13 (001101) = 4 (000100), speciálně x & 1 se "divá" na poslední cifru čísla x # | je bitový `or` vezme dvě čísla v bitovém zápisu a napíše jedničku tam kde ji mělo alespoň jedno číslo # např. 12 (1100) | 6 (0110) = 14 (1110) # |= je jen zkratka: x = x | y je to samé jako x |= y # Program očekává na vstupu mezerou oddělená vstupní čísla cisla = [int(x) for x in input().split()] max_cifer = int.bit_length(max(cisla)) # ekvivalentně bychom mohli spočítat dvojikový logaritmus a zaokrouhlit dolů # Postavíme si strom -- každý vrchol bude reprezentován seznamem dvou vrcholů, na nulté pozici je syn vrcholu, kam se # dostaneme po hraně 0 a na pozici 1 je syn kam se dostaneme jedničkou, pokud syn neexistuje máme tam uložené None strom = [None, None] # začínáme pouze s kořenem for cislo in cisla: vrchol = strom # průchod začínáme od kořene for i in reversed(range(max_cifer)): cifra = (cislo >> i) & 1 # zkoumaná cifra -- 1 nebo 0 if vrchol[cifra] is None: # vrchol ještě neexistuje... vrchol[cifra] = [None, None] # ... vytvoříme ho vrchol = vrchol[cifra] # přesuneme se do příslušeného vrcholu nejlepsi_vysledek = 0 nejlepsi_dvojice = (None, None) for cislo in cisla: vrchol = strom # začínáme v kořeni vysledek = 0 # průběžně počítaný xor parovane = 0 # průbežně počítané nejlepší číslo na spárování for i in reversed(range(max_cifer)): cifra = (cislo >> i) & 1 # zkoumaná cifra -- 0 nebo 1 opak = int(not cifra) # její negace (také 0 nebo 1) if vrchol[opak] is not None: # Pokud můžeme jít do opaku, tak chceme vrchol = vrchol[opak] # přesuneme se do příslušného syna vysledek |= (1 << i) # ve XORu bude na příslušné pozici jednička parovane |= opak << i # párované číslo má na příslušné pozici "opak" (0 nebo 1) else: # musíme jít horší cestou vrchol = vrchol[cifra] # přesuneme se do příslušného syna parovane |= cifra << i # párované číslo má na příslušné pozici "cifra" # XOR má na příslušné pozici nulu, nemusíme jej nijak upravovat if vysledek > nejlepsi_vysledek: # Vylepšili jsme výsledek nejlepsi_vysledek = vysledek nejlepsi_dvojice = (cislo, parovane) # Jen troška magie abychom výsledek hezky vypsaly, hledaná čísla jsou v "nejlepsi_dvojice", xor v "nejlepsi_vysledek" predpis = "{{:0{}b}} ({{}})".format(max_cifer) print(u"Nejlepší výsledek je") print(predpis.format(nejlepsi_dvojice[0], nejlepsi_dvojice[0])) print(predpis.format(nejlepsi_dvojice[1], nejlepsi_dvojice[1])) print(max_cifer * '-') print(predpis.format(nejlepsi_vysledek, nejlepsi_vysledek))