По двум ислам найти такие два, для которых выполнятся следующие условия. - 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 · 13.02.2014, 20:03

Сообщение от 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 · 13.02.2014, 22:55

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 · 13.02.2014, 23:29 **[ТС]**

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

C++

X >>= 1;

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

@Eldies · 13.02.2014, 23:31

то же, что

C++

1	X = X >> 1;

ValeryS · 13.02.2014, 23:37

и тоже что и

C++

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

C++

X >>= 1;

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

@max_besheniy · 14.02.2014, 17:25 **[ТС]**

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

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

Опции темы

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

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