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

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

Войти
Регистрация
Восстановить пароль
 
netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 63
Завершенные тесты: 2
#1

Найти пары элементов массива сумма которых является степенью двойки - C++

30.07.2016, 11:02. Просмотров 480. Ответов 14
Метки нет (Все метки)

Вам задано n чисел a1, a2, ..., an. Найдите количество пар индексов i, j (i < j) таких, что ai + aj является степенью двойки (то есть найдется такое целое число x, что ai + aj = 2x).
Входные данные
В первой строке следует целое положительное число n (1 ≤ n ≤ 105) — количество чисел.

Во второй строке следует n целых положительных чисел a1, a2, ..., an (1 ≤ ai ≤ 109).

Выходные данные
Выведите количество пар индексов i, j (i < j) таких, что ai + aj является степенью числа 2
0
Миниатюры
Найти пары элементов массива сумма  которых является степенью двойки   Найти пары элементов массива сумма  которых является степенью двойки  
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.07.2016, 11:02
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти пары элементов массива сумма которых является степенью двойки (C++):

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

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

Является ли число степенью двойки - C++
Условие: Входные данные Входной файл INPUT.TXT содержит единственное целое число N, не превосходящее 10000 по абсолютной величине. ...

Является ли число степенью двойки - C++
Дано натуральное число n. Определите, является ли оно степенью числа 2, и выведете слово YES если является,и выведите слово NO если не...

Является ли число степенью двойки? - C++
Вводится число. Напечатать YES, если оно является степенью двойки, NO - иначе.

Определить, является ли число степенью двойки - C++
По заданному положительному числу n &lt; 2^64 определить, является ли оно степенью двойки. Решение должно иметь сложность O(1). 1 ...

14
netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 63
Завершенные тесты: 2
30.07.2016, 11:04  [ТС] #2
Мой код оказался медленным:
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
27
28
29
30
31
#include"iostream"
using namespace std;
 
int main()
{
 
    int n, mas[100000];
    int pair = 0;
    cin >> n;
    for (int i = 0; i<n; i++)
    {
        cin >> mas[i];
    }
 
    for (int k = 0; k< n - 1; k++)
    {
        for (int j = k + 1; j<n; j++)
        {
            for (int v = 2; v<1000000000; v = v * 2)
            {
                if ((mas[k] + mas[j]) == v)
                {
                    ++pair;
                                         break;
                     
                }
            }
        }
    }
    cout << pair;
}
0
netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 63
Завершенные тесты: 2
30.07.2016, 11:11  [ТС] #3
В вопросе не приписал степени
0
Миниатюры
Найти пары элементов массива сумма  которых является степенью двойки  
Изображения
 
MansMI
1277 / 1055 / 291
Регистрация: 08.01.2012
Сообщений: 3,992
30.07.2016, 11:28 #4
mas[k] + mas[j] можно посчитать один раз,
и массив 20-230 можно подготоаить заранее, возможно поможет
0
zss
Модератор
Эксперт С++
6484 / 6047 / 1985
Регистрация: 18.12.2011
Сообщений: 15,680
Завершенные тесты: 1
30.07.2016, 13:29 #5
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
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
using namespace std;
 
bool is_power2(int k)
{
    int count1=0;
    while(k)
    {
        count1+=(k&1);
        k>>=1;
    }
    return !(count1-1); // должна быть всего одна единичка
}
int main()
{
 
    int n;
    cin >> n;
    int* mas=new int[n];
    for (int i = 0; i<n; i++)
    {
        cin >> mas[i];
    }
 
    int pair = 0;
    for (int k = 0; k< n - 1; k++)
    {
        for (int j = k + 1; j<n; j++)
        {
            if( is_power2(mas[k] + mas[j]) )
                ++pair;
        }
    }
    delete[] mas;
    cout << pair<<endl;
    system("pause");
    return 0;
}
1
mat_for_c
161 / 156 / 33
Регистрация: 26.04.2013
Сообщений: 704
Завершенные тесты: 2
31.07.2016, 16:39 #6
C++
1
x & (x-1) == 0
простая проверка на степень 2-ки
3
netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 63
Завершенные тесты: 2
31.07.2016, 20:17  [ТС] #7
mat_for_c, MansMI, Спасибо за помощь , конечно оба варианта рабочие, но на codeforces всё равно выдаёт, что превышено ограничение времени
0
Mr.X
Эксперт С++
3050 / 1695 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
31.07.2016, 21:24 #8
Цитата Сообщение от netrox Посмотреть сообщение
mat_for_c, MansMI, Спасибо за помощь , конечно оба варианта рабочие, но на codeforces всё равно выдаёт, что превышено ограничение времени
А кто тогда навесил "лучший ответ" на сообщение №5, оно же не проходит по времени?
0
MansMI
1277 / 1055 / 291
Регистрация: 08.01.2012
Сообщений: 3,992
31.07.2016, 21:36 #9
5Г вариантов, даже простой перебор индексов без вычислений не укладывается
0
netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 63
Завершенные тесты: 2
31.07.2016, 21:39  [ТС] #10
Mr.X, Ну ведь не я
0
Миниатюры
Найти пары элементов массива сумма  которых является степенью двойки  
netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 63
Завершенные тесты: 2
31.07.2016, 21:41  [ТС] #11
Mr.X,
0
Миниатюры
Найти пары элементов массива сумма  которых является степенью двойки  
netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 63
Завершенные тесты: 2
31.07.2016, 21:44  [ТС] #12
MansMI,
0
MansMI
1277 / 1055 / 291
Регистрация: 08.01.2012
Сообщений: 3,992
31.07.2016, 21:55 #13
чего?
0
netrox
0 / 0 / 0
Регистрация: 14.12.2015
Сообщений: 63
Завершенные тесты: 2
31.07.2016, 22:16  [ТС] #14
MansMI, прости , сайт заглючил
0
Новичок
Модератор
1250 / 798 / 178
Регистрация: 17.07.2012
Сообщений: 4,261
Записей в блоге: 1
Завершенные тесты: 2
31.07.2016, 23:19 #15
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
N <= 105
Очевидно же, что в лоб никак не зайдет. Нужно использовать map, насчитать количество каждого числа, а затем пройтись по нему и вычислить ответ используя комбинаторные формулы. Степени двойки предварительно насчитать. Идем по map и скажем видим число 1, тогда надо найти число 2 - 1 = 1, 4 - 1 = 3, 8 - 1 = 7... И дальше перемножить количества этих чисел и чтоб не было повторений поделить на 2. Если само число является степенью двойки то надо еще в ответ добавить количество комбинаций между равными числами. Ну например есть 3 двойки, 2 + 2 = 4 степень двойки, значит надо добавить в ответ 3 * (3 - 1) / 2. Вот такой код заходит.
Код
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
27
28
29
30
31
32
33
34
//GNU C++11
#include <bits/stdc++.h>
 
using namespace std;
using int64 = long long;
using uint64 = unsigned long long;
 
int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); // Эти 2 строки для ускорения ввода, порой в олимпиадных задачах без них решение может упасть по времени
    uint64 n;
    cin >> n;
    map <int64, uint64> cnt;
    for (uint64 i = 0; i < n; i++) {
        int64 t;
        cin >> t;
        cnt[t]++;
    }
    vector <int64> pow2;
    for (int64 p = 1, h = 1e18; p <= h; p *= 2) pow2.push_back(p); // Степени двойки
    uint64 ans = 0;
    for (auto& i: cnt) {
        for (auto& j: pow2) {
            if (j == 2 * i.first) {
                ans += i.second * (i.second - 1);
                continue;
            }
            auto it = cnt.find(j - i.first);
            if (it != cnt.end())
                ans += it -> second * i.second;
        }
    }
    cout << ans / 2;
}
3
31.07.2016, 23:19
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
31.07.2016, 23:19
Привет! Вот еще темы с ответами:

Определить, является ли число степенью двойки - C++
Такая проблема: в проге мне нужно задать количество чисел которые я введу (т.е создать массив под них), потом ввести числа и оно должно мне...

Проверить, является ли число степенью двойки - C++
Бьюсь с самого утра все никак. Условия Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или...

Определить, является ли число целой степенью двойки - C++
Задано целое положительное число.Определить, является ли оно целой степенью двойки. Вход 1 16 1028 1024 Выход Yes

Является ли заданное натуральное число степенью двойки - C++
Является ли заданное натуральное число степенью двойки? Добавлено через 3 часа 46 минут Помогите пожалуйста,очень нужно !!!


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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