// Задача AT6 — ПЪТУВАНЕ ВЪВ ВРЕМЕТО
// Наивно решение (максимално h = 20, частичен резултат ~27%).
//
// Ползваме обикновения двоичен запис на числата (N <= 920 < 2^10, т.е. 10 бита).
// За двойка (x, y) търсим позиция, на която двата записа се различават:
//   * ако някой бит е 1 в x и 0 в y, Сашка подвиква тази позиция (1..10), а Звезденчо
//     отговаря „да“, когато съответният бит на въпроса е единица;
//   * иначе някой бит е 0 в x и 1 в y; Сашка подвиква позицията плюс 10 (11..20), а
//     Звезденчо отговаря „да“, когато съответният бит на въпроса е нула.
// Понеже позицията може да стигне 20, резултатът е само частичен.

#include <string>

int encode(int N, int x, int y) {
    int oneInXzeroInY = x & ~y;
    int zeroInXoneInY = ~x & y;
    if (oneInXzeroInY != 0) {
        return __builtin_ctz(oneInXzeroInY) + 1;          // позиция 1..10
    }
    return __builtin_ctz(zeroInXoneInY) + 11;             // позиция 11..20
}

bool answer(int N, int q, int h) {
    if (h <= 10) {
        return (q >> (h - 1)) & 1;                        // „да“, ако битът е единица
    }
    return !((q >> (h - 11)) & 1);                        // „да“, ако битът е нула
}
