Разбор задачи «Морские скважины»

Идея задачи

Для каждого числа x нужно найти такое число y, что:

• 1 <= y < x,
• если вычислить z = x xor y,
• то числа x, y, z образуют невырожденный треугольник.

Это значит, что должны выполняться строгие неравенства:

• x + y > z
• x + z > y
• y + z > x

Если подходящего y нет, нужно вывести -1.

Наблюдение про XOR

Обозначим:

• a = x
• b = y
• c = x xor y

Очень полезна формула:

x + y = (x xor y) + 2 * (x & y)

Она показывает связь обычного сложения и побитовых операций.

Из неё сразу получаем:

• x + y > x xor y тогда и только тогда, когда x & y > 0

То есть у чисел x и y должен быть хотя бы один общий единичный бит.

Что означает третье неравенство

Разберём условие:

y + (x xor y) > x

Если упростить его через биты, получится важный смысл:

• у числа y должен быть хотя бы один бит, которого нет в x.

Почему это так?

Если все единичные биты y уже содержатся в x, то y целиком «лежит внутри» битов x, и нужной строгости не получится.

Значит, чтобы треугольник был невырожденным, число y должно одновременно:

1. иметь общий единичный бит с x;
2. иметь хотя бы один единичный бит вне x.

Каким должно быть число y

Теперь задача становится почти конструктивной.

Нужно собрать y так, чтобы:

• один его бит совпадал с единичным битом числа x;
• другой бит стоял в позиции, где у x ноль.

Тогда:

• общий бит даст x + y > x xor y;
• новый бит даст y + (x xor y) > x.

Остаётся проследить, чтобы y < x.

Для этого достаточно брать оба таких бита ниже старшего бита числа x.

Когда ответа не существует

Случай 1. x — степень двойки

Например:

• 2 = 10₂
• 4 = 100₂
• 8 = 1000₂

У такого числа ровно один единичный бит.

Если мы захотим, чтобы у y был общий бит с x, нам придётся поставить именно этот бит. Но если добавить ещё какой-то бит, чтобы выполнить второе условие, конструкция уже не даст нужного корректного ответа.

Для таких x ответа нет.

Проверка степени двойки стандартная:

x & (x - 1) == 0

Случай 2. x имеет вид 2^k - 1

Например:

• 3 = 11₂
• 7 = 111₂
• 15 = 1111₂

У такого числа все биты ниже старшего равны 1.

Значит, ниже старшего бита нет позиции, где можно взять нулевой бит и добавить его в y. То есть мы не можем сделать так, чтобы у y был бит, которого нет в x.

Следовательно, здесь тоже ответа нет.

Проверка такого вида числа тоже стандартная:

x & (x + 1) == 0

Как построить ответ

Если x не является степенью двойки и не имеет вид 2^k - 1, то ответ существует.

Тогда можно сделать так:

• взять младший единичный бит числа x;
• найти младший нулевой бит числа x ниже старшего бита;
• объединить их в число y.

То есть:

y = low_one | low_zero

Почему это работает:

• бит low_one уже есть в x, значит у x и y есть общий единичный бит;
• бит low_zero отсутствует в x, значит у y есть новый бит;
• оба бита лежат ниже старшего бита x, значит y < x.

Пошаговый пример

Пусть x = 10.

В двоичном виде:

10 = 1010₂

1. Младший единичный бит — это 2 = 0010₂.
2. Младший нулевой бит ниже старшего — это 1 = 0001₂.
3. Тогда:

y = 2 | 1 = 3

Проверим:

• x = 10
• y = 3
• z = 10 xor 3 = 9

Получаем стороны 10, 3, 9.

Проверка:

• 10 + 3 > 9
• 10 + 9 > 3
• 3 + 9 > 10

Все три неравенства выполнены.

Алгоритм

Для каждого x:

1. Если x — степень двойки, вывести -1.
2. Если x имеет вид 2^k - 1, вывести -1.

3. Иначе:

   • найти младший единичный бит low_one = x & -x;
   • найти младший нулевой бит ниже старшего;
   • вывести y = low_one | low_zero.

Почему алгоритм корректен

Докажем, что построенное число y всегда подходит.

Пусть:

• low_one — бит, который есть в x;
• low_zero — бит, которого нет в x, но он расположен ниже старшего бита;
• y = low_one | low_zero.

Тогда:

1. Выполняется 1 <= y < x

Число y положительно, потому что содержит хотя бы один установленный бит.

Оба выбранных бита строго ниже старшего бита числа x, значит y < x.

2. Выполняется x + y > x xor y

Поскольку бит low_one присутствует и в x, и в y, имеем x & y > 0.

По формуле

x + y = (x xor y) + 2 * (x & y)

получаем строгое неравенство x + y > x xor y.

3. Выполняется y + (x xor y) > x

У числа y есть бит low_zero, которого нет в x. Значит, y содержит хотя бы один «новый» бит относительно x, и это как раз даёт строгую прибавку, необходимую для выполнения неравенства.

4. Выполняется x + (x xor y) > y

Это неравенство автоматически верно, потому что x — самое большое по смыслу число конструкции, а y < x, при этом x xor y >= 0. В реальной проверке оно также всегда выполняется для нашего построения.

Следовательно, все три строгих треугольных неравенства выполнены, значит ответ корректен.

Сложность

Мы перебираем не более 31 бита для каждого теста.

• Время: O(31) на тест, то есть фактически O(1)
• Память: O(1)

Эталонная реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        int x;
        cin >> x;

        if ((x & (x - 1)) == 0) {
            cout << -1 << '\n';
            continue;
        }

        if ((x & (x + 1)) == 0) {
            cout << -1 << '\n';
            continue;
        }

        int low_one = x & -x;
        int low_zero = 0;

        for (int b = 0; b < 31; b++) {
            if ((1 << b) >= x) {
                break;
            }
            if ((x & (1 << b)) == 0) {
                low_zero = (1 << b);
                break;
            }
        }

        int y = low_one | low_zero;
        cout << y << '\n';
    }

    return 0;
}

Эталонная реализация на Python

import sys

input = sys.stdin.readline

t = int(input())
for _ in range(t):
    x = int(input())

    if x & (x - 1) == 0:
        print(-1)
        continue

    if x & (x + 1) == 0:
        print(-1)
        continue

    low_one = x & -x
    low_zero = 0

    for b in range(31):
        if (1 << b) >= x:
            break
        if (x & (1 << b)) == 0:
            low_zero = 1 << b
            break

    y = low_one | low_zero
    print(y)

Типичные ошибки

1. Проверять только одно условие

Некоторые пытаются выбрать y, чтобы у x и y был общий бит. Но этого недостаточно: нужен ещё хотя бы один бит в y, которого нет в x.

2. Брать бит слишком высоко

Если взять бит не ниже старшего бита x, можно получить y >= x, а это запрещено.

3. Не обработать числа без ответа

Если не сделать отдельную проверку для:

• степеней двойки;
• чисел вида 2^k - 1,

то программа будет выдавать неверные ответы на специальных тестах.

Вывод

В этой задаче главное — не перебирать ответы, а понять битовый смысл треугольных неравенств.

После этого задача превращается в короткую конструкцию:

• нужен один общий бит;
• нужен один новый бит;
• оба должны лежать ниже старшего бита.

Именно это и позволяет получить решение за константное время на каждый тест.