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

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

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

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

13.02.2014, 19:50. Просмотров 328. Ответов 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%, и что странно, некоторые тесты с неправильными ответами(но больше половины-тайм лимит). Помогите решить
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.02.2014, 19:50
Здравствуйте! Я подобрал для вас темы с ответами на вопрос По двум ислам найти такие два, для которых выполнятся следующие условия. (C++):

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

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

Сколько существует натуральных чисел, для которых выполняются следующие условия - Информатика
кто решит задачу, тому я буду очень признателен и благодарен, я над ней ломаю голову уже не 2й день, вот текст задачи: Сколько...

В упорядоченном массиве, найти такие два элемента, произведение которых максимально - C#
Одномерный массив.В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально). Двумерный массив....

В упорядоченном массиве, найти такие два элемента, произведение которых максимально - C#
В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально).

В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально) - C#
В упорядоченном массиве, найти такие два элемента, произведение которых максимально (минимально). Составить обычную программу и через...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ValeryS
Модератор
6631 / 5039 / 466
Регистрация: 14.02.2011
Сообщений: 16,846
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;
  }
0
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 отрабатывает правильно, и никаких циклов
1
max_besheniy
25 / 25 / 1
Регистрация: 21.11.2013
Сообщений: 208
13.02.2014, 23:29  [ТС] #4
Eldies, объясните что значит оператор
C++
1
X >>= 1;
Раньше такого не видел
0
Eldies
90 / 81 / 28
Регистрация: 06.02.2014
Сообщений: 120
13.02.2014, 23:31 #5
то же, что
C++
1
X = X >> 1;
0
ValeryS
Модератор
6631 / 5039 / 466
Регистрация: 14.02.2011
Сообщений: 16,846
13.02.2014, 23:37 #6
и тоже что и
C++
1
2
X/=2;
X=X/2;

C++
1
X >>= 1;
означает сдвинуть вправо на один разряд
а поскольку разряды двоичные то и делим на 2
были бы десятичные делили бы на 10
0
max_besheniy
25 / 25 / 1
Регистрация: 21.11.2013
Сообщений: 208
14.02.2014, 17:25  [ТС] #7
ValeryS, это типо побитовый сдвиг вправо?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.02.2014, 17:25
Привет! Вот еще темы с ответами:

Для любого числа N найти все такие натуральные x,y, для которых выполняется заданное условие - Free Pascal
Для любого числа N найти все такие натуральные x,y, для которых выполняется N=(x)^2 + (y)^2. Ввод данных с клавиатуры. Иметь возможность...

Найти такие k, для которых k-ая строка массива совпадает с k-ым столбцом - C (СИ)
Задание-Для заданного двумерного массива из n строк и m столбцов: Найти такие k, для которых k-ая строка массива совпадает с k-ым...

Найти все такие тройки натуральных чисел х, у, z из интервала от 1 до 20, для которых выполняется равенство - Delphi
Найти все такие тройки натуральных чисел х,у,z из интервала от 1 до 20, для которых выполняется равенство: х2 + у2 =z2 var...

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


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
14.02.2014, 17:25
Ответ Создать тему
Опции темы

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