Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
max_besheniy
25 / 25 / 1
Регистрация: 21.11.2013
Сообщений: 208
13.02.2014, 19:50     По двум ислам найти такие два, для которых выполнятся следующие условия. #1
Напишите программу, которая по двум целым неотрицательным числам 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++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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%, и что странно, некоторые тесты с неправильными ответами(но больше половины-тайм лимит). Помогите решить
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.02.2014, 19:50     По двум ислам найти такие два, для которых выполнятся следующие условия.
Посмотрите здесь:

Построить такие два треугольника с вершинами в заданном множестве точек на плоскосли, из которых один лежал бы строго внутри другого C++
C++ Среди чисел 1, ..., n найти все такие, запись которых совпадает с последними цифрами записи их квадрата
C++ Найти такие элементы массива (а также их сумму), в которых чередуются четные и нечетные цифры
Найти такие пары натуральных чисел, сумма которых является квадратом некоторого натурального числа C++
C++ Найти такие тройки натуральных чисел x,y,z из интервала от 1 до 20,для которых выполняется равенство x^2-y=z^2
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,056
13.02.2014, 20:03     По двум ислам найти такие два, для которых выполнятся следующие условия. #2
Цитата Сообщение от max_besheniy Посмотреть сообщение
if (a%2==1) k=a/2;
* * else
* * * * k=a/2-1;
C++
1
2
3
4
быстрее для нечетных
k=a/2;
if(a%2==0)
 k--;
Добавлено через 7 минут
Цитата Сообщение от max_besheniy Посмотреть сообщение
f=1;
что это за переменная за что отвечает?

я бы сделал так
C++
1
2
3
4
5
6
for( int i=0, k=a;i<=a/2;i++,k--)
 if((i^k)==b)
  {
     cout<<i<<" "<<k<<endl;
    return;
  }
Eldies
89 / 80 / 28
Регистрация: 06.02.2014
Сообщений: 119
13.02.2014, 22:55     По двум ислам найти такие два, для которых выполнятся следующие условия. #3
Сообщение было отмечено автором темы, экспертом или модератором как ответ
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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
25 / 25 / 1
Регистрация: 21.11.2013
Сообщений: 208
13.02.2014, 23:29  [ТС]     По двум ислам найти такие два, для которых выполнятся следующие условия. #4
Eldies, объясните что значит оператор
C++
1
X >>= 1;
Раньше такого не видел
Eldies
89 / 80 / 28
Регистрация: 06.02.2014
Сообщений: 119
13.02.2014, 23:31     По двум ислам найти такие два, для которых выполнятся следующие условия. #5
то же, что
C++
1
X = X >> 1;
ValeryS
Модератор
6377 / 4843 / 442
Регистрация: 14.02.2011
Сообщений: 16,056
13.02.2014, 23:37     По двум ислам найти такие два, для которых выполнятся следующие условия. #6
и тоже что и
C++
1
2
X/=2;
X=X/2;

C++
1
X >>= 1;
означает сдвинуть вправо на один разряд
а поскольку разряды двоичные то и делим на 2
были бы десятичные делили бы на 10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.02.2014, 17:25     По двум ислам найти такие два, для которых выполнятся следующие условия.
Еще ссылки по теме:

C++ Как задать два условия для цикла
C++ Среди чисел от 1 до n найти такие, запись которых совпадает с последними цифрами записи их квадратов

Искать еще темы с ответами

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

Текущее время: 12:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru