Pomaly sa blíži začiatok semestra, a s ním aj najťažšie rozhodnutia každého študenta - ktoré predmety si zapísať? Presne takúto dilemu má aj Stanko, študent informatiky na matfyze1. Stanko si najprv teda zapísal všetky povinné predmety - napríklad programovanie, algebru, angličtinu, či telesnú, a má ešte veľa zaujímavých nepovinných predmetov, ktoré by si chcel zapísať - napríklad Neštruktúrované rozpravy o štruktúrach: kapitoly z matematiky pre informatikov, Hyperprogramovanie, či Determinanty pohybovej aktivity2. Bohužial, už teraz má plný rozvrh, a v škole bude tak 12 hodín denne, takže si nemôže zapísať všetky predmety, ale len 2. Zároveň, aby to nemal až príliš tažké3 chcel by, aby boli tieto dva predmety viac rovnaké, ako rozdielne.
Úloha
Pre každý predmet existuje jedno číslo, ktoré daný predmet dokonale popisuje. Dva predmety sú tak rovnaké, aká je hodnota bitového ANDu ich čísel, a tak rozdielne ako je hodnota ich bitového XORu. Vašou úlohou je zistiť, koľko dvojíc predmetov spĺňa Stankove kritérium - dvojica je viac rovnaká ako rozdielna.
Bitové operácie
Bitové operácie majú ako “vstup” dve čísla, a vracajú jedno. Pozerajú sa na zápis vstupných čísiel v 2-kovej sústave – ich bitový zápis. Potom sa pozrú na každú bit (pozíciu) zvlášť, a vo výsledku bude bit podľa tých na vstupe. V prípade XORu (buď alebo) bude výsledok ‘1’ ak boli vstupné bity rôzne a inak ‘0’. V prípade ANDu (a) to bude ‘1’ len v prípade, že boli oba vstupné bity ‘1’, v opačnom ‘0’. Napríklad bitový AND čísel \(6\) a \(12\), teda \(6 \& 12 = 4\), a ich bitový XOR \(6 \oplus 12 = 10\). Bitová reprezentácia \(6\) je ‘0110’ a \(12\) je ‘1100’. Teda ich AND má bitovú reprezentáciu ‘0100’ a XOR ‘1010’.
Formát vstupu
V prvom riadku vstupu je číslo \(n\) - počet predmetov, nad ktorými Stanko uvažuje. V druhom riadku je medzerou oddelených \(n\) čísel \(p_1, \dots p_n\), \(p_i\) popisuje \(i\)-ty predmet. Platia nasledujúce obmedzenia: \(1 \leq p_i \leq 10^{9}\)
Sada | 1 | 2 | 3 | 4 |
---|---|---|---|---|
\(1 \leq n \leq\) | \(6\) | \(30\) | \(1\,000\) | \(2\cdot10^5\) |
Formát výstupu
Vypíš jeden riadok a v ňom jedno celé číslo - počet dvojíc predmetov, ktoré sú viac podobné ako rozdielne.
Príklad
Input:
5
1 4 3 7 10
Output:
1
Vyhovuje iba dvojica \(4\) a \(7\).
Input:
3
3 3 3
Output:
3
Input:
2
2 4
Output:
0
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.