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

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

Войти
Регистрация
Восстановить пароль
 
max_besheniy
25 / 25 / 1
Регистрация: 21.11.2013
Сообщений: 208
#1

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

13.02.2014, 19:50. Просмотров 323. Ответов 6
Метки нет (Все метки)

Напишите программу, которая по двум целым неотрицательным числам 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     По двум ислам найти такие два, для которых выполнятся следующие условия.
Посмотрите здесь:

Найти такие тройки натуральных чисел x,y,z из интервала от 1 до 20,для которых выполняется равенство x^2-y=z^2 - C++
найти все такие тройки натуральных чисел x,y,z из интервала от 1 до 20,для которых выполняется равенство x^2-y=z^2

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

Найти такие числа, десятичное представление которых содержит убывающую последовательность - C++
Среди простых чисел, не превосходящих заданного числа N, найти такие, десятичное представление которых содержит убывающую...

Как задать два условия для цикла - C++
т.е. мне нужно чтобы программа отобрала слова которые имеют 3 буквы и 2 гласных к примеру

Найти такие числа запись которых совпадает с последними цифрами записи их квадрата - C++
Натолкните на мысль, пожалуйста!!! Программу пока не пишите, а дайте подсказки, или покажите код похожих программ. Очень прошу помочь ...

Найти такие элементы массива (а также их сумму), в которых чередуются четные и нечетные цифры - C++
Дан массив из N целых чисел, где N&lt;=16, каждое число в диапазоне от –32000 до 32000. Массив для каждой задачи должен задаваться в секции...

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,733
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
90 / 81 / 28
Регистрация: 06.02.2014
Сообщений: 120
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
90 / 81 / 28
Регистрация: 06.02.2014
Сообщений: 120
13.02.2014, 23:31     По двум ислам найти такие два, для которых выполнятся следующие условия. #5
то же, что
C++
1
X = X >> 1;
ValeryS
Модератор
6551 / 5017 / 463
Регистрация: 14.02.2011
Сообщений: 16,733
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++
Задание: Среди заданных натуральных чисел найти такие, десятичная запись кото- рых не содержит одинаковых цифр. я понимаю, что и...

Среди чисел 1, ..., n найти все такие, запись которых совпадает с последними цифрами записи их квадрата - C++
Среди чисел 1, ..., n найти все такие, запись которых совпадает с последними цифрами записи их квадрата. Составил алгоритм, а дальше тю-тю....

Найти такие пары натуральных чисел, сумма которых является квадратом некоторого натурального числа - C++
На интервале найти такие пары натуральных чисел, сумма которых является квадратом некоторого натурального числа. Пожалуйста, экзамен.

Среди заданных натуральных чисел найти такие, десятичная запись которых не содержит одинаковых цифр - C++
Среди заданных натуральных чисел найти такие, десятичная запись которых не содержит одинаковых цифр. По идее есть работающий код, но...

Найти такие элементы, у которых оба соседних элемента, как и сам он, делятся нацело на одно и то же число - C++
Найти и вывести на экран такие элементы, у которых оба соседних элемента как и сам он делятся нацело на одно и то же число. Помогите...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru