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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.82
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
#1

Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% - C++

10.04.2013, 19:16. Просмотров 2754. Ответов 59
Метки нет (Все метки)

≡ вот эта закарюка меня пугает,подскажите, что это?
и решите пожалуйста задачку
Требуется для заданных K N M и X найти количество пар чисел A и B таких, что A≡0 (mod N), B≡0 (mod M), 0≤A,B<2 K , A⊕B=X.

Формат входных данных

Первая строка содержит целые числа K N M и X (1≤K≤30, 1≤N,M,X≤2×10(в девятой)9 ).

Формат результата

Выведите искомое количество пар чисел.

Примеры

Входные данные Результат работы
3 1 2 5
4
Примечания

Искомые пары (1;4), (3;6), (5;0) и (7;2).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.04.2013, 19:16     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000%
Посмотрите здесь:

C++ Дан текст из нескольки строк, определить самое длинное и самое короткое слово
Строки: найти самое короткое и самое длинное слово C++
Найти самое длинное и самое короткое слово в предложении C++
Напечатать самое длинное и самое короткое слово в строке C++
Вывести самое длинное и самое короткое слово из строки C++
C++ В заданной строке определить самое длинное и самое короткое слово
C++ В заданном предложении поменять местами самое длинное и самое короткое слова
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 20:50     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #21
nonedark2008, Вы совершенно правы! Я согласен с вашим решением)
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 20:53  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #22
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Будет вот так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main( void )
{
  UINT64 K = 3, N = 1, M = 2, X = 5;
  UINT64 A, B;
 
  for (A = 0; A < 1 << K; A += N)
  {
    B = A ^ X;
    if (B % M == 0)
      cout << '(' << A << ',' << B << ')' << endl;
  }
  system("pause");
  return 0;
}

а на каком это языке???,,,, просто Dev C++ не хочет компилить(
nonedark2008
854 / 593 / 116
Регистрация: 28.07.2012
Сообщений: 1,599
10.04.2013, 20:56     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #23
Цитата Сообщение от yutr777 Посмотреть сообщение
а на каком это языке???
Это C++ =) Попробуй заменить UINT64 на unsigned __int64, либо на unsigned long long, либо просто на unsigned если все остальное не фурычит
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 20:56     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #24
yutr777,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int main(){         
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    long long K = 3, N = 1, M = 2, X = 5;
    scanf("%I64d%I64d%I64d%I64d", &N, &M, &K, &X);
    long long ans = 0;
    for (long long A = 0; A < (1 << K); A += N){
      long long B = A ^ X;
      if (B % M == 0 && B < (1<<K)) //небольшой фикс
        ans++;
    }
    printf("%I64d", ans);
    system("pause");
    return 0;
}
Решение nonedark2008 верно. Но можно решить и комбинаторной формулой)
nonedark2008
854 / 593 / 116
Регистрация: 28.07.2012
Сообщений: 1,599
10.04.2013, 20:58     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #25
Просто UINT64 - это мой темплейт для unsigned __int64.
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 21:06  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #26
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Просто UINT64 - это мой темплейт для unsigned __int64.
парни, что-то не фурычит....компиляцию проваливает О_о на компе все окау а тут....

Добавлено через 3 минуты
Парни,облом((((
свалил время на 37 тесте...((( пэчаль беда(
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 21:08     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #27
yutr777, а сколько времени отводится ? Вы где решаете (любопытство)?
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 21:11  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #28
Цитата Сообщение от Ternsip Посмотреть сообщение
yutr777, а сколько времени отводится ? Вы где решаете (любопытство)?
чемпионат БГУИР по программированию)))


Добавлено через 15 секунд
только ТСССС!)))
молчим)
nonedark2008
854 / 593 / 116
Регистрация: 28.07.2012
Сообщений: 1,599
10.04.2013, 22:01     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #29
Хмм. А вообще какие ограничения?
Наверняка фейлится при больших N. Можно ли например вообще взять и цикл распаралелить?

Добавлено через 9 минут
Скорее всего тест фейлится когда N и M малы, а K - большое. Тогда происходит слишком много итераций.
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 22:10  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #30
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Хмм. А вообще какие ограничения?
Наверняка фейлится при больших N. Можно ли например вообще взять и цикл распаралелить?

Добавлено через 9 минут
Скорее всего тест фейлится когда N и M малы, а K - большое. Тогда происходит слишком много итераций.
да, скорее всего именно так и есть(
nonedark2008
854 / 593 / 116
Регистрация: 28.07.2012
Сообщений: 1,599
10.04.2013, 22:12     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #31
Еще ко-че можно выжать из условия A,B <2^k. Т.е. выбирать только подходящие промежутки.
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 22:19  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #32
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Еще ко-че можно выжать из условия A,B <2^k. Т.е. выбирать только подходящие промежутки.
всмысле?
но мы вроде же и так перебираем только эти промежутки?
nonedark2008
854 / 593 / 116
Регистрация: 28.07.2012
Сообщений: 1,599
10.04.2013, 22:21     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #33
Думаем дальше. Когда у нас B получается >= 2^K ? А тогда, когда X >= 2 ^ K. Т.е. если у нас X >= 2^K, то решений будет 0.
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 22:27  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #34
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Думаем дальше. Когда у нас B получается >= 2^K ? А тогда, когда X >= 2 ^ K. Т.е. если у нас X >= 2^K, то решений будет 0.
надо что-то с B придумать....
nonedark2008
854 / 593 / 116
Регистрация: 28.07.2012
Сообщений: 1,599
10.04.2013, 22:31     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #35
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
int main( void )
{
  UINT K = 30, N = 1, M = 2, X = 2 * pow(10, 3);
  UINT A, B;
  UINT num = 0;
  if (M > N)
  {
    swap(A, B);
    swap(M, N);
  }
 
  if (X > (1 << K))
  {
    cout << 0 << endl;
    return 0;
  }
 
  for (A = 0; A < (1 << K); A += N)
  {
    B = A ^ X;
    if (B % M == 0)
      ++num;
  }
  cout << num << endl;
  system("pause");
  return 0;
}
Вот немножко переделал, но наверняка все-равно не пройдет по времени.
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 22:37  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #36
Цитата Сообщение от nonedark2008 Посмотреть сообщение
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
int main( void )
{
  UINT K = 30, N = 1, M = 2, X = 2 * pow(10, 3);
  UINT A, B;
  UINT num = 0;
  if (M > N)
  {
    swap(A, B);
    swap(M, N);
  }
 
  if (X > (1 << K))
  {
    cout << 0 << endl;
    return 0;
  }
 
  for (A = 0; A < (1 << K); A += N)
  {
    B = A ^ X;
    if (B % M == 0)
      ++num;
  }
  cout << num << endl;
  system("pause");
  return 0;
}
Вот немножко переделал, но наверняка все-равно не пройдет по времени.
нее, тут вроде мне так кажется оно как было так и останется...(
nonedark2008
854 / 593 / 116
Регистрация: 28.07.2012
Сообщений: 1,599
10.04.2013, 22:41     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #37
Цитата Сообщение от yutr777 Посмотреть сообщение
нее, тут вроде мне так кажется оно как было так и останется...(
Остаться то останется, но немножко лучше станет.
lemegeton
2917 / 1346 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
10.04.2013, 22:42     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #38
Цитата Сообщение от yutr777 Посмотреть сообщение
нее, тут вроде мне так кажется оно как было так и останется...(
Покажите полностью код, который вы туда сдаете. Есть подозрение, что ваши модификации могут притормаживать.
yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 22:45  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #39
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Остаться то останется, но немножко лучше станет.
ну вот, как я говорил...тоже самое

Добавлено через 1 минуту
Цитата Сообщение от lemegeton Посмотреть сообщение
Покажите полностью код, который вы туда сдаете. Есть подозрение, что ваши модификации могут притормаживать.
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
#include <iostream>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int main()
{
  long long K = 30, N = 1, M = 2, X =0;
  cin >> K >> N >> M >> X;
  long long A, B;
  long long num = 0;
  if (M > N)
  {
    swap(A, B);
    swap(M, N);
  }
 
  if (X > (1 << K))
  {
    cout << 0 << endl;
    return 0;
  }
 
  for (A = 0; A < (1 << K); A += N)
  {
    B = A ^ X;
    if (B % M == 0)
      ++num;
  }
  cout << num << endl;
  return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.04.2013, 22:49     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000%
Еще ссылки по теме:

C++ Найти самое короткое и самое длинное слово в строке
Найдите самое длинное, и самое короткое слово в заданном предложении C++
C++ Напечатать самое длинное и самое короткое слово в строке
C++ Реализовать структуру данных, которая имеет все те же операции, что массив длины n. Сложность операций
C++ Ввести строку, содержащую несколько слов. Определить самое длинное и самое короткое слово

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

Или воспользуйтесь поиском по форуму:
lemegeton
2917 / 1346 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
10.04.2013, 22:49     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #40
Как он у вас вообще автотесты проходит? Там же надо что-то считывать со стандартного ввода, выводить на стандартный вывод... А у вас в коде этого нет.
Я что-то не знаю про эту олимпиаду и там дают заранее составленные и известные входные данные?
Тогда
C++
1
std::cout << 4 << std::endl;
ничем не отличается от фактического подсчета.
Yandex
Объявления
10.04.2013, 22:49     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000%
Ответ Создать тему
Опции темы

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