По двум ислам найти такие два, для которых выполнятся следующие условия. - C++

@max_besheniy · Регистрация: 21.11.2013

Напишите программу, которая по двум целым неотрицательным числам A и B найдет такие неотрицательные целые числа X и Y, для которых выполняются условия:

A = X + Y
B = X xor Y, где xor – побитовое исключающее или.
X – наименьшее среди чисел, для которых выполняются условия 1 и 2.
Входные данные

Первые две строки содержат соответственно целые числа A и B (0 ≤ A, B ≤ 2^64 - 1).

Выходные данные

Вывести в одной строке два целых неотрицательных числа X и Y, либо одно число -1, если таких пар не существует.

Пример входных данных
142
76
Пример выходных данных
33 109

Решаю вот такую задачу. Придумал простенький алгоритм, который хоть не самый быстрый, но должен на коротких тестах выдавать правильный ответ

C++

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int main()
{
    long long a,b,x,y,k,f=0;
    cin>>a>>b;
    if (a%2==1) k=a/2;
    else
        k=a/2-1;
    for (int i=1;i<=k;i++)
    {
        int h=i^(a-i);
        if (h==b)
        {
            f=1;
            cout<<i<<" "<<a-i<<endl;
            exit(0);
        }
    }   
    cout<<-1<<endl;
}

Проходит 36%, и что странно, некоторые тесты с неправильными ответами(но больше половины-тайм лимит). Помогите решить

ValeryS · Регистрация: 14.02.2011

Сообщение от max_besheniy

if (a%2==1) k=a/2;
* * else
* * * * k=a/2-1;

C++

быстрее для нечетных
k=a/2;
if(a%2==0)
 k--;

Добавлено через 7 минут

Сообщение от max_besheniy

f=1;

что это за переменная за что отвечает?

я бы сделал так

C++

for( int i=0, k=a;i<=a/2;i++,k--)
 if((i^k)==b)
  {
     cout<<i<<" "<<k<<endl;
    return;
  }

@Eldies · Регистрация: 06.02.2014

C++

void find(unsigned long long A, unsigned long long B)
{
    unsigned long long Y = B;
 
    if (A < Y)
    {
        std::cout << "-1";
        return;
    }
 
    unsigned long long X = A - Y;
    if (X & 1)
    {
        std::cout << "-1";
        return;
    }
    X >>= 1;
    if (X & Y)
    {
        std::cout << "-1";
        return;
    }
    Y += X;
 
    std::cout << X << " " << Y;
}

Рассуждал так:
каждая 1 в В - место, где Х и У отличаются. Для определенности, поставим в этих местах 1 в У и 0 в Х.
теперь, во всех остальных битах Х и У одинаковы, значит
1) А - У должно быть четным
2) (А-У)/2 не должно иметь единичных битов там же, где У

Добавлено через 7 минут
не знаю, правильно ли в целом, но А = 142, В = 76 отрабатывает правильно, и никаких циклов

@max_besheniy · Регистрация: 21.11.2013

Eldies, объясните что значит оператор

C++

X >>= 1;

Раньше такого не видел

@Eldies · Регистрация: 06.02.2014

то же, что

C++

1	X = X >> 1;

ValeryS · Регистрация: 14.02.2011

и тоже что и

C++

1 2	X/=2; X=X/2;

C++

X >>= 1;

означает сдвинуть вправо на один разряд
а поскольку разряды двоичные то и делим на 2
были бы десятичные делили бы на 10

@max_besheniy · Регистрация: 21.11.2013

ValeryS, это типо побитовый сдвиг вправо?

@max_besheniy 25 / 25 / 1 Регистрация: 21.11.2013 Сообщений: 208
	14.02.2014, 17:25 [ТС] По двум ислам найти такие два, для которых выполнятся следующие условия.	#7
	ValeryS, это типо побитовый сдвиг вправо?

Yandex Объявления	14.02.2014, 17:25 По двум ислам найти такие два, для которых выполнятся следующие условия.

Опции темы

С++ для начинающих

По двум ислам найти такие два, для которых выполнятся следующие условия. - C++