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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.82
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 19:16     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #1
≡ вот эта закарюка меня пугает,подскажите, что это?
и решите пожалуйста задачку
Требуется для заданных 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++
матрица 8X8 (найти самое большое и самое маленькое число) C++
C++ В заданной строке определить самое длинное и самое короткое слово
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 22:51  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #41
Цитата Сообщение от lemegeton Посмотреть сообщение
Как он у вас вообще автотесты проходит? Там же надо что-то считывать со стандартного ввода, выводить на стандартный вывод... А у вас в коде этого нет.
Я что-то не знаю про эту олимпиаду и там дают заранее составленные и известные входные данные?
Тогда
C++
1
std::cout << 4 << std::endl;
нееет,вы что это просто sample'вские данные в переменные можно обнулить что угондо написать....они все равно потом считываются
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2908 / 1337 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
10.04.2013, 22:53     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #42
Цитата Сообщение от yutr777 Посмотреть сообщение
нееет,вы что это просто sample'вские данные в переменные можно обнулить что угондо написать....они все равно потом считываются
Тогда еще раз. Покажите, пожалуйста, весь код. Тот самый, который "потом считывает". Есть подозрение, что там тормоза.
nonedark2008
623 / 501 / 92
Регистрация: 28.07.2012
Сообщений: 1,338
10.04.2013, 22:55     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #43
Цитата Сообщение от lemegeton Посмотреть сообщение
Тогда еще раз. Покажите, пожалуйста, весь код.
Чувствуется, что на олимпиадах вы не были. Программа тестер сама подает на ввод нужные данные, для этого там и стоит cin.

Добавлено через 46 секунд
Цитата Сообщение от lemegeton Посмотреть сообщение
Есть подозрение, что там тормоза.
Тормоза в том, что при маленьких N совершается огромное число итераций.
lemegeton
 Аватар для lemegeton
2908 / 1337 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
10.04.2013, 22:59     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #44
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Чувствуется, что на олимпиадах вы не были. Программа тестер сама подает на ввод нужные данные, для этого там и стоит cin.
То ли лыжи не едут, то ли... я не вижу в этом посте ни одного cin'а.

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

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

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

Добавлено через 2 минуты
Попробуйте в следующий проход еще убрать лишние библиотеки
C++
1
2
#include <cmath>
#include <algorithm>
Они, конечно, должны аффектить только на этапе компиляции, но кто его знает, что там за система.
нет, тут решение оптимальнее найти надо(
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 23:01     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #46
не используйте cin и cout используйте printf и scanf (cout будет выводить минут 5 на большом тесте когда вводится 1e6 элементов printf сделает за 200 ms)
Это просто к сведению. 6иблиотеки никогда не сожрут столько времени ил памяти, это надо знать, действительно, нужно придумать комбинаторную формулу.
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 23:08  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #47
Цитата Сообщение от Ternsip Посмотреть сообщение
не используйте cin и cout используйте printf и scanf (cout будет выводить минут 5 на большом тесте когда вводится 1e6 элементов printf сделает за 200 ms)
Это просто к сведению. 6иблиотеки никогда не сожрут столько времени ил памяти, это надо знать, действительно, нужно придумать комбинаторную формулу.
а вот у меня сейчас вопрос идиота
а какие библиотеки для printf и scanf нужно включать?
просто у меня оно на компе все ок компилится с принт и скан, а в системе не компилится даже!
nonedark2008
623 / 501 / 92
Регистрация: 28.07.2012
Сообщений: 1,338
10.04.2013, 23:09     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #48
Цитата Сообщение от yutr777 Посмотреть сообщение
а какие библиотеки для printf и scanf нужно включать?
stdio.h

Добавлено через 44 секунды
Так еще раз. Можно ли использовать распаралеливание?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
10.04.2013, 23:11     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #49
nonedark2008, на кодефорсесе нельзя
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 23:18  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #50
Цитата Сообщение от 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 секунд
знаю,задолбал я вас, ну простите уж меня)
nonedark2008
623 / 501 / 92
Регистрация: 28.07.2012
Сообщений: 1,338
10.04.2013, 23:32     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #51
Т.е. задача сводится к тому, что нужно найти максимальную сторону квадрата, такую что N квадратов можно впихнуть в прямоугольник W*H?
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 23:36  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #52
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Т.е. задача сводится к тому, что нужно найти максимальную сторону квадрата, такую что N квадратов можно впихнуть в прямоугольник W*H?
совершенно верно!
nonedark2008
623 / 501 / 92
Регистрация: 28.07.2012
Сообщений: 1,338
10.04.2013, 23:43     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #53
Первые мысли, которые приходят.
У нас есть поле 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 - целочисленное деление.
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
10.04.2013, 23:44  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #54
Цитата Сообщение от 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 тест...жесткие задачи
nonedark2008
623 / 501 / 92
Регистрация: 28.07.2012
Сообщений: 1,338
11.04.2013, 00:28     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #55
Нууу, с этим все оказалось намного проще. Первым делом нужно поискать, а не сделал ли кто раньше за нас эту работу...
Короче, тута есть решение задачи.
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 минуты
Алгоритм достаточно прост для понимания, так что кто знаком с английским - быстро разберется.
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
11.04.2013, 09:18  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #56
Цитата Сообщение от 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 минуты
Алгоритм достаточно прост для понимания, так что кто знаком с английским - быстро разберется.
я разобрался,но он работает как моя формула и получает неправильный ответ на третьем тесте.
nonedark2008
623 / 501 / 92
Регистрация: 28.07.2012
Сообщений: 1,338
11.04.2013, 11:36     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #57
Цитата Сообщение от yutr777 Посмотреть сообщение
≤2 63 -2
Эт вообще че?

Добавлено через 37 секунд
И выложи код того, что отправляешь вместе с парсером ввода.
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
11.04.2013, 11:43  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #58
Цитата Сообщение от 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
nonedark2008
623 / 501 / 92
Регистрация: 28.07.2012
Сообщений: 1,338
11.04.2013, 11:58     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #59
Я ж писал, что тебе нужно еще подстроить код под данную задачу. 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 - тогда мы не уйдем из целых чисел.
Короче, нужно тебе побумать как это переделать шоб работало.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.04.2013, 12:18     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000%
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
yutr777
 Аватар для yutr777
4 / 4 / 0
Регистрация: 07.04.2013
Сообщений: 85
11.04.2013, 12:18  [ТС]     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000% #60
Цитата Сообщение от nonedark2008 Посмотреть сообщение
Я ж писал, что тебе нужно еще подстроить код под данную задачу. 2^63 - это точно не int. И даже больше скажу, это точно не unsigned int. T=Единственное что подойдет - это unsigned __int64 (unsigned long long).
Я бы еще переехал с double на long double. Но возможно и его будет нехватать.
Т.е. тебе нужно все это проверить, заметить функции на те, которые работают с long double.
Но если и в этом случае нехватит точности long double, то нужно от него отказаться и реализовывать через целочисленну арифметику.

Вот, например, эту фигню можно заменить просто на height/y - тогда мы не уйдем из целых чисел.
Короче, нужно тебе побумать как это переделать шоб работало.
я трудно понимаю все эту штуку....
решил написать дихотомию....Не поверите, WA 3 тест....это то-то страшное
Yandex
Объявления
11.04.2013, 12:18     Булева алгебра, самое сложное что я видел. H E L P Сложность over 90000000%
Ответ Создать тему
Опции темы

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