Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.74/27: Рейтинг темы: голосов - 27, средняя оценка - 4.74
 Аватар для yutr777
8 / 8 / 3
Регистрация: 07.04.2013
Сообщений: 85

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

10.04.2013, 19:16. Показов 7165. Ответов 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).
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
10.04.2013, 19:16
Ответы с готовыми решениями:

Что самое сложное в программировании на С++ для Вас?
Добрый вечер! В перерывах между общением с марсианами и постройкой петамобиля задаю здесь сущие вопросы. Расскажите, пожалуйста, какие...

Что самое сложное вы делали в паскале? Скиньте свои роботы пожалуйста
Что самое сложное вы делали в паскале? Скиньте свои роботы пожалуйста. Самые сложные

Булева алгебра
Помогите пожалуйста решить задания. Просто завтра контрольная, а в ДМ не очень шарю Правила, 5.16, 5.18. Задания набирать ручками....

59
 Аватар для yutr777
8 / 8 / 3
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 22:51  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от lemegeton Посмотреть сообщение
Как он у вас вообще автотесты проходит? Там же надо что-то считывать со стандартного ввода, выводить на стандартный вывод... А у вас в коде этого нет.
Я что-то не знаю про эту олимпиаду и там дают заранее составленные и известные входные данные?
Тогда
C++
1
std::cout << 4 << std::endl;
нееет,вы что это просто sample'вские данные в переменные можно обнулить что угондо написать....они все равно потом считываются
0
 Аватар для lemegeton
4904 / 2697 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
10.04.2013, 22:53
Цитата Сообщение от yutr777 Посмотреть сообщение
нееет,вы что это просто sample'вские данные в переменные можно обнулить что угондо написать....они все равно потом считываются
Тогда еще раз. Покажите, пожалуйста, весь код. Тот самый, который "потом считывает". Есть подозрение, что там тормоза.
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
10.04.2013, 22:55
Цитата Сообщение от lemegeton Посмотреть сообщение
Тогда еще раз. Покажите, пожалуйста, весь код.
Чувствуется, что на олимпиадах вы не были. Программа тестер сама подает на ввод нужные данные, для этого там и стоит cin.

Добавлено через 46 секунд
Цитата Сообщение от lemegeton Посмотреть сообщение
Есть подозрение, что там тормоза.
Тормоза в том, что при маленьких N совершается огромное число итераций.
0
 Аватар для lemegeton
4904 / 2697 / 921
Регистрация: 29.11.2010
Сообщений: 5,783
10.04.2013, 22:59
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Чувствуется, что на олимпиадах вы не были. Программа тестер сама подает на ввод нужные данные, для этого там и стоит cin.
То ли лыжи не едут, то ли... я не вижу в этом посте ни одного cin'а.

Добавлено через 45 секунд
Все. Нашел.

Добавлено через 2 минуты
Попробуйте в следующий проход еще убрать лишние библиотеки
C++
1
2
#include <cmath>
#include <algorithm>
Они, конечно, должны аффектить только на этапе компиляции, но кто его знает, что там за система.
0
 Аватар для yutr777
8 / 8 / 3
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 23:00  [ТС]
Цитата Сообщение от lemegeton Посмотреть сообщение
То ли лыжи не едут, то ли... я не вижу в этом посте ни одного cin'а.

Добавлено через 45 секунд
Все. Нашел.

Добавлено через 2 минуты
Попробуйте в следующий проход еще убрать лишние библиотеки
C++
1
2
#include <cmath>
#include <algorithm>
Они, конечно, должны аффектить только на этапе компиляции, но кто его знает, что там за система.
нет, тут решение оптимальнее найти надо(
0
 Аватар для Ternsip
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 23:01
не используйте cin и cout используйте printf и scanf (cout будет выводить минут 5 на большом тесте когда вводится 1e6 элементов printf сделает за 200 ms)
Это просто к сведению. 6иблиотеки никогда не сожрут столько времени ил памяти, это надо знать, действительно, нужно придумать комбинаторную формулу.
0
 Аватар для yutr777
8 / 8 / 3
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 23:08  [ТС]
Цитата Сообщение от Ternsip Посмотреть сообщение
не используйте cin и cout используйте printf и scanf (cout будет выводить минут 5 на большом тесте когда вводится 1e6 элементов printf сделает за 200 ms)
Это просто к сведению. 6иблиотеки никогда не сожрут столько времени ил памяти, это надо знать, действительно, нужно придумать комбинаторную формулу.
а вот у меня сейчас вопрос идиота
а какие библиотеки для printf и scanf нужно включать?
просто у меня оно на компе все ок компилится с принт и скан, а в системе не компилится даже!
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
10.04.2013, 23:09
Цитата Сообщение от yutr777 Посмотреть сообщение
а какие библиотеки для printf и scanf нужно включать?
stdio.h

Добавлено через 44 секунды
Так еще раз. Можно ли использовать распаралеливание?
0
 Аватар для Ternsip
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 23:11
nonedark2008, на кодефорсесе нельзя
0
 Аватар для yutr777
8 / 8 / 3
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 23:18  [ТС]
Цитата Сообщение от Ternsip Посмотреть сообщение
nonedark2008, на кодефорсесе нельзя
Задача H-Tower Defence

Ограничение времени: 2 с
Ограничение памяти: 64 M

Андрей очень любить играть в различные Flash-игры, но особенно ему нравятся игры жанра Tower Defence. И вот недавно ему в руки как раз попалась такая игра.

Основная цель этой игры — уничтожить как можно больше монстров, которые хаотично перемещаются по арене. Арена представляет собой прямоугольник шириной W и высотой H. Андрей может строить башни, которые атакуют монстров. Каждая башня имеет определенную область видимости в форме квадрата и может атаковать тех монстров, которые находятся в области ее видимости. Сама башня является материальной точкой, с которой совпадает центр области ее видимости.

Абсолютно случайно Андрей узнал о пасхальном яйце в этой игре: с помощью волшебного сочетания клавиш 'Ctrl+A+C+M+I+C+P+C' он может задать целое положительное число A, после чего размер стороны области видимости любой башни, которую построит Андрей будет равна A.

На каждом уровне Андрей должен построить ровно N башен. При этом области видимости башен не должны перекрываться или выходить за пределы арены, однако они могут касаться друг друга и границ арены. И, конечно, чтобы уничтожить максимальное число монстров, Андрею необходимо покрыть большую площадь арены.

Помогите Андрею для каждого уровня, который он проходит определить такое число A i , чтобы выполнить все его условия. Андрей пользуется пасхальным яйцом перед началом каждого уровня.

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

В первой строке задано количество уровней K (1≤K≤10 5 ).

В следующих K строках заданы описания уровней — три целых числа, разделенных пробелами: ширина арены W i , высота арены H i и число башен N i (1≤W i ,H i ,N i ≤2 63 -2), которое должен построить игрок. Гарантируется, что для любого i выполняется условие: N≤W i ·H i , то есть решение всегда существует.

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

Необходимо вывести K целых чисел A i по одному в строке — размеры области видимости башен для каждого уровня.

Примеры

Входные данные Результат работы
1
4 8 5
2
2
6 9 2
9 6 13
4
1

нашел формулу неравенства вроде как верную,вот:
(w/a)*(h/a)>=n
но перебор не катит здесь(
ещё вот такая формула но тоже не катит...
x=w*h;
y=x/2;
y=y+1;
y=y/n;

гляньте уже хоть это....а то совсем труба дело...(

Добавлено через 14 секунд
знаю,задолбал я вас, ну простите уж меня)
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
10.04.2013, 23:32
Т.е. задача сводится к тому, что нужно найти максимальную сторону квадрата, такую что N квадратов можно впихнуть в прямоугольник W*H?
0
 Аватар для yutr777
8 / 8 / 3
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 23:36  [ТС]
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Т.е. задача сводится к тому, что нужно найти максимальную сторону квадрата, такую что N квадратов можно впихнуть в прямоугольник W*H?
совершенно верно!
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
10.04.2013, 23:43
Первые мысли, которые приходят.
У нас есть поле W*H. В него влезет W*H квадратов со стороной 1. Далее в него влезет W/2 * H/2 квадратов со стороной 2. 3 - W/3*H/3 и т.д. Т.е. нужно найти такое m, чтобы W/m * H/m >= N и W/(m+1) * H(m+1) < N

Добавлено через 2 минуты
А точнее первое m, что W/m*H/m < N
W/m - целочисленное деление.
0
 Аватар для yutr777
8 / 8 / 3
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 23:44  [ТС]
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Первые мысли, которые приходят.
У нас есть поле W*H. В него влезет W*H квадратов со стороной 1. Далее в него влезет W/2 * H/2 квадратов со стороной 2. 3 - W/3*H/3 и т.д. Т.е. нужно найти такое m, чтобы W/m * H/m >= N и W/(m+1) * H(m+1) < N

Добавлено через 2 минуты
А точнее первое m, что W/m*H/m < N
W/m - целочисленное деление.
именно так, я так написал, но увы это перебор(
TLE 3 тест...жесткие задачи
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
11.04.2013, 00:28
Нууу, с этим все оказалось намного проще. Первым делом нужно поискать, а не сделал ли кто раньше за нас эту работу...
Короче, тута есть решение задачи.
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
39
40
41
42
43
44
45
int GetTileSize(int width, int height, int tileCount)
{
    // quick bailout for invalid input
    if (width*height < tileCount) { return 0; }
 
    // come up with an initial guess
    double aspect = (double)height/width;
    double xf = sqrtf(tileCount/aspect);
    double yf = xf*aspect;
    int x = max(1.0, floor(xf));
    int y = max(1.0, floor(yf));
    int x_size = floor((double)width/x);
    int y_size = floor((double)height/y);
    int tileSize = min(x_size, y_size);
 
    // test our guess:
    x = floor((double)width/tileSize);
    y = floor((double)height/tileSize);
    if (x*y < tileCount) // we guessed too high
    {
        if (((x+1)*y < tileCount) && (x*(y+1) < tileCount))
        {
            // case 2: the upper bound is correct
            //         compute the tileSize that will
            //         result in (x+1)*(y+1) tiles
            x_size = floor((double)width/(x+1));
            y_size = floor((double)height/(y+1));
            tileSize = min(x_size, y_size);
        }
        else
        {
            // case 3: solve an equation to determine
            //         the final x and y dimensions
            //         and then compute the tileSize
            //         that results in those dimensions
            int test_x = ceil((double)tileCount/y);
            int test_y = ceil((double)tileCount/x);
            x_size = min(floor((double)width/test_x), floor((double)height/y));
            y_size = min(floor((double)width/x), floor((double)height/test_y));
            tileSize = max(x_size, y_size);
        }
    }
 
    return tileSize;
}
Указываешь ширину, высоту и кол-во квадратов и на выходе получаешь ответ.
Только тебе нужно точно проверить для всех ли твоих исзодных данных оно подойдет.

Добавлено через 24 минуты
Алгоритм достаточно прост для понимания, так что кто знаком с английским - быстро разберется.
1
 Аватар для yutr777
8 / 8 / 3
Регистрация: 07.04.2013
Сообщений: 85
11.04.2013, 09:18  [ТС]
Цитата Сообщение от 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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int GetTileSize(int width, int height, int tileCount)
{
    // quick bailout for invalid input
    if (width*height < tileCount) { return 0; }
 
    // come up with an initial guess
    double aspect = (double)height/width;
    double xf = sqrtf(tileCount/aspect);
    double yf = xf*aspect;
    int x = max(1.0, floor(xf));
    int y = max(1.0, floor(yf));
    int x_size = floor((double)width/x);
    int y_size = floor((double)height/y);
    int tileSize = min(x_size, y_size);
 
    // test our guess:
    x = floor((double)width/tileSize);
    y = floor((double)height/tileSize);
    if (x*y < tileCount) // we guessed too high
    {
        if (((x+1)*y < tileCount) && (x*(y+1) < tileCount))
        {
            // case 2: the upper bound is correct
            //         compute the tileSize that will
            //         result in (x+1)*(y+1) tiles
            x_size = floor((double)width/(x+1));
            y_size = floor((double)height/(y+1));
            tileSize = min(x_size, y_size);
        }
        else
        {
            // case 3: solve an equation to determine
            //         the final x and y dimensions
            //         and then compute the tileSize
            //         that results in those dimensions
            int test_x = ceil((double)tileCount/y);
            int test_y = ceil((double)tileCount/x);
            x_size = min(floor((double)width/test_x), floor((double)height/y));
            y_size = min(floor((double)width/x), floor((double)height/test_y));
            tileSize = max(x_size, y_size);
        }
    }
 
    return tileSize;
}
Указываешь ширину, высоту и кол-во квадратов и на выходе получаешь ответ.
Только тебе нужно точно проверить для всех ли твоих исзодных данных оно подойдет.

Добавлено через 24 минуты
Алгоритм достаточно прост для понимания, так что кто знаком с английским - быстро разберется.
я разобрался,но он работает как моя формула и получает неправильный ответ на третьем тесте.
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
11.04.2013, 11:36
Цитата Сообщение от yutr777 Посмотреть сообщение
≤2 63 -2
Эт вообще че?

Добавлено через 37 секунд
И выложи код того, что отправляешь вместе с парсером ввода.
0
 Аватар для yutr777
8 / 8 / 3
Регистрация: 07.04.2013
Сообщений: 85
11.04.2013, 11:43  [ТС]
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Эт вообще че?

Добавлено через 37 секунд
И выложи код того, что отправляешь вместе с парсером ввода.
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int GetTileSize(int width, int height, int tileCount)
{
 
    if (width*height < tileCount) { return 0; }
 
 
    double aspect = (double)height/width;
    double xf = sqrtf(tileCount/aspect);
    double yf = xf*aspect;
    double x = max(1.0, floor(xf));
    double y = max(1.0, floor(yf));
    double x_size = floor((double)width/x);
    double y_size = floor((double)height/y);
    double tileSize = min(x_size, y_size);
 
 
    x = floor((double)width/tileSize);
    y = floor((double)height/tileSize);
    if (x*y < tileCount)
    {
        if (((x+1)*y < tileCount) && (x*(y+1) < tileCount))
        {
      
            x_size = floor((double)width/(x+1));
            y_size = floor((double)height/(y+1));
            tileSize = min(x_size, y_size);
        }
        else
        {
   
            double test_x = ceil((double)tileCount/y);
            double test_y = ceil((double)tileCount/x);
            x_size = min(floor((double)width/test_x), floor((double)height/y));
            y_size = min(floor((double)width/x), floor((double)height/test_y));
            tileSize = max(x_size, y_size);
        }
    }
 
    return tileSize;
}
int main()
{
long long k;
cin  >> k;
long long w,h,n;
for (int i=1;i<=k;i++)
{
    cin >> w >> h >> n;
    long long mo=GetTileSize(w,h,n);
    cout << mo << endl;
}
return 0;
}
Это 2^63
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
11.04.2013, 11:58
Я ж писал, что тебе нужно еще подстроить код под данную задачу. 2^63 - это точно не int. И даже больше скажу, это точно не unsigned int. T=Единственное что подойдет - это unsigned __int64 (unsigned long long).
Я бы еще переехал с double на long double. Но возможно и его будет нехватать.
Т.е. тебе нужно все это проверить, заметить функции на те, которые работают с long double.
Но если и в этом случае нехватит точности long double, то нужно от него отказаться и реализовывать через целочисленну арифметику.
Цитата Сообщение от yutr777 Посмотреть сообщение
floor((double)height/y)
Вот, например, эту фигню можно заменить просто на height/y - тогда мы не уйдем из целых чисел.
Короче, нужно тебе побумать как это переделать шоб работало.
0
 Аватар для yutr777
8 / 8 / 3
Регистрация: 07.04.2013
Сообщений: 85
11.04.2013, 12:18  [ТС]
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Я ж писал, что тебе нужно еще подстроить код под данную задачу. 2^63 - это точно не int. И даже больше скажу, это точно не unsigned int. T=Единственное что подойдет - это unsigned __int64 (unsigned long long).
Я бы еще переехал с double на long double. Но возможно и его будет нехватать.
Т.е. тебе нужно все это проверить, заметить функции на те, которые работают с long double.
Но если и в этом случае нехватит точности long double, то нужно от него отказаться и реализовывать через целочисленну арифметику.

Вот, например, эту фигню можно заменить просто на height/y - тогда мы не уйдем из целых чисел.
Короче, нужно тебе побумать как это переделать шоб работало.
я трудно понимаю все эту штуку....
решил написать дихотомию....Не поверите, WA 3 тест....это то-то страшное
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
11.04.2013, 12:18

Булева алгебра
Найти значение логического выражения: (x &lt; y) AND (x = z) при a) x = 0, y = 0, z = 0; б) x = 0, y = -8, z =...

Булева Алгебра
Ребят, помогите пожалуйста с работой, 1,2,7 сделал, с остальными не могу переварить.

Булева Алгебра
Проверти пожалуйста правильно ли выполнил минимизацию ? Меня сильно смущает (Х1Х2Х3) что не сокращается.

Булева Алгебра)
Помогите пожалуйста)Ни как не могу понять,как минимизировать то,что стоит в скобках Пускай НЕ-это ! х4*х5*(!х1*х2*х3+х1*!х2*!х3) или...

Булева алгебра
при умножении x на y по and(&amp;), получаем некое с, как потом зная с и x найти y ?


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

Или воспользуйтесь поиском по форуму:
60
Ответ Создать тему
Новые блоги и статьи
Книги по геймдизайну, игровым механикам и проектированию игрового опыта
8Observer8 08.11.2026
Содержание блога | English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle | Объем: 768 стр. Ссылки: Amazon . . .
Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят
zorxor 08.11.2026
Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .
Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ.
zorxor 08.11.2026
Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .
Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL
8Observer8 07.11.2026
Содержание блога | English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике
Maks 07.11.2026
Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .
Про "Windows must die!"
kumehtar 04.11.2026
Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .
Красочные поля с номером страницы svg+background-image
russiannick 04.11.2026
Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .
Вступаем в новую фазу генерации favicons, векторную.
russiannick 02.11.2026
Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru