Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
1 / 1 / 0
Регистрация: 17.10.2014
Сообщений: 16
1

Создать set с комбинацией из цифр

17.10.2014, 16:17. Показов 1035. Ответов 13
Метки нет (Все метки)

Добавлено через 11 минут
В общем какая задача:

Кликните здесь для просмотра всего текста
Жители планеты ФОРМИН готовятся к встрече землян и благоустраивают свой космодром.
Земляне, зная, что самый устойчивый вариант при посадке — это тренога (три ноги, основания
которых лежат в вершинах треугольника), попросили, чтобы жители ФОРМИНа учли все вари-
анты расположения оснований посадочной треноги. Зная, что времени до встречи осталось совсем
немного, жители ФОРМИНа обратились к Вам за помощью. Вам предстоит посчитать количество
всевозможных вариантов расположения оснований ног треноги (количество невырожденных тре-
угольников).
Космодром расположен таким образом, что координаты точек посадочной площадки удовлетво-
ряют условиям: 0 <= x <= n, 0 <= y <= m, где n;m — заданные целые числа. Во избежание ошибок при
посадке, будем рассматривать только целочисленные координаты. Обратите внимание на то, что
если Вы поставите треногу так, что все основания ног треноги будут на одной прямой или какие-
либо основания сойдутся в одной точке, то космический корабль землян может упасть. А это не
приветствуется ЗЕМКОСМОСом.
Два варианта расположения треноги считаются различными, если множества точек, занимаемых
основаниями треноги в первом случае, не совпадает с множеством точек, занимаемых основаниями
треноги во втором случае.

Формат входных данных
В единственной строке даны записанные через пробел два натуральных числа n и m — размеры
посадочной площадки (0 <= n;m <= 100).

Формат выходных данных
Выведите количество вариантов расположения оснований ног треноги космического корабля с
целочисленными координатами.

Входные данные | Выходные данные
1 1 | 4
2 1 | 18


Она была на школьной олимпиаде, её я не решил, пришёл домой, спросил у знающего человека как её решать, он говорит, что надо пройти все точки, добавив их в set, однако он был очень занят и не объяснил подробно, поэтому обращаюсь сюда.

Про set я тогда услышал впервые, сейчас почитал о нём, порешал пару задач с его использованием и решил вернуться к этой задаче. Думал, думал, решил, что надо создать k = (m+1)*(m+1) точек, т.е. для каждой имя будет 0..k-1 , потом добавить через тройной вложенный цикл все комбинации из этих точек, и вот тут проблемка. Я не в курсе, как добавить эти 3 точки в одну ячейку set.

Ваши предположения, советы и, возможно, решение данной задачи с объяснениями (желательно под спойлером весь код программы, а без спойлера принцип её решения).

Буду очень благодарен.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.10.2014, 16:17
Ответы с готовыми решениями:

Создать класс Set (множество)
Сделал все что мог нужно помочь сделать выделение памяти под элементи динамически и перегрузки...

Перегрузка функций (Создать класс Set )
Создать класс Set – множество целых чисел, используя динамическую память. Определить операторы...

Создать шаблон класса Set (множество)
Нужно реализовать: Класс •множество set. Дополнительно перегрузить следующие операции: + ...

Union(Set set1, Set set2) и intersect(Set set1, Set set2)
Напишите методы union(Set set1, Set set2) и intersect(Set set1, Set set2), реализующих операции...

13
Эксперт по математике/физикеЭксперт С++
1967 / 1300 / 375
Регистрация: 16.05.2013
Сообщений: 3,369
Записей в блоге: 6
17.10.2014, 16:54 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
#include <iostream>
#include <set>
int main() {
    int count = 0;
    int n;
    int m;
    std::cout << "n = "; std::cin >> n;
    std::cout << "m = "; std::cin >> m;
    ++n; ++m;
    std::set<std::set<int>> set;
    std::set<int> comb;
    for(int i = 0; i < n * m; ++i)
        for(int j = 0; j < n * m; ++j)
            for(int k = 0; k < n * m; ++k)
                if(((k%n - j%n) * (i/n - j/n) - (k/n - j/n) * (i%n - j%n)) != 0) {
                    comb.insert(i);
                    comb.insert(j);
                    comb.insert(k);
                    set.insert(comb);
                    comb.clear();
                }
    std::cout << set.size() << std::endl;
    return 0;
}
1
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
17.10.2014, 16:59 3
Ilot, это не пройдет по времени.
0
1 / 1 / 0
Регистрация: 17.10.2014
Сообщений: 16
17.10.2014, 17:09  [ТС] 4
Да, я б не догадался использовать сет сетов, довольно-таки интересно, но уж очень долго
0
Эксперт по математике/физикеЭксперт С++
1967 / 1300 / 375
Регистрация: 16.05.2013
Сообщений: 3,369
Записей в блоге: 6
17.10.2014, 17:16 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
#include <iostream>
#include <set>
int main() {
    int count = 0;
    int n;
    int m;
    std::cout << "n = "; std::cin >> n;
    std::cout << "m = "; std::cin >> m;
    ++n; ++m;
    std::set<std::set<int>> set;
    std::set<int> comb;
    for(int i = 0; i < n * m; ++i)
        for(int j = i + 1; j < n * m; ++j)
            for(int k = j + 1; k < n * m; ++k)
                if(((k%n - j%n) * (i/n - j/n) - (k/n - j/n) * (i%n - j%n)) != 0) {
                    comb.insert(i);
                    comb.insert(j);
                    comb.insert(k);
                    set.insert(comb);
                    comb.clear();
                }
    std::cout << set.size() << std::endl;
    return 0;
}
Сейчас подумаю может еще как упростить можно...
0
Форумчанин
Эксперт CЭксперт С++
8178 / 5028 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
17.10.2014, 17:21 6
Например, если нужна лишь уникальность, то можно использовать std::unordered_set.

Но суть задачи в нахождении оптимального алгоритма, а не знании STL.
0
220 / 165 / 47
Регистрация: 17.07.2012
Сообщений: 587
17.10.2014, 17:31 7
может это чушь, но больше похоже на правду xD

переберем пару точек, и посчитаем сколько треугольников с целочисленными координатами имеют вершины именно в этих 2 точках. Это будут все точки минус наши 2 и минус все те которые лежат на этой прямой(проходящей через нашу пару). Потом суммируем ответы для каждой пары, Ну и в конце на что-нибудь поделить надо, т.к. несколько раз учли одни и те же треугольники. Теперь осталось узнавать сколько точек лежат с целыми координатами лежат на нашей прямой, я пока не знаю, но может существует формула?
0
1 / 1 / 0
Регистрация: 17.10.2014
Сообщений: 16
17.10.2014, 22:19  [ТС] 8
Ну ребят, может у кого ещё есть догадки? Попробуйте решить. Я уже ничего придумать не могу
0
2827 / 1636 / 253
Регистрация: 03.12.2007
Сообщений: 4,222
17.10.2014, 23:36 9
Можно из всех сочетаний по 3 точки вычесть сочетания по 3 точки на одной прямой. 100/100 за 6 секунд на моём компе уже хотя бы; если только результат вообще верный... (Для начала тут можно проверку чисел на взаимную простоту оптимизировать.)

Добавлено через 13 секунд
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
#include <cstdlib>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
bool Coprime(int a, int b)
{
    return b == 0 ? abs(a) == 1 : Coprime(b, a % b);
}
 
int main()
{
    int n, m;
    std::cin >> n >> m;
    n++, m++;
    int np = n * m;
    long long c = (long long)np * (np - 1) * (np - 2) / 6;
    c -= m * (n * (n - 1) * (n - 2) / 6);
    c -= n * (m * (m - 1) * (m - 2) / 6);
    for (int y0 = 0; y0 < m; y0++)
    {
        for (int x0 = 0; x0 < n; x0++)
        {
            for (int y1 = y0 + 1; y1 < m; y1++)
            {
                int dy = y1 - y0;
                for (int x1 = 0; x1 < n; x1++)
                {
                    int dx = x1 - x0;
                    if ((y0 - dy >= 0 && x0 - dx >= 0 && x0 - dx < n) ||
                            dx == 0 || !Coprime(dx, dy))
                        continue;
                    int np = min((m - 1 - y0) / dy + 1, dx >= 0 ?
                        (n - 1 - x0) / dx + 1 :
                        x0 / -dx + 1);
                    c -= np * (np - 1) * (np - 2) / 6;
                }
            }
        }
    }
    cout << c << endl;
}
0
1 / 1 / 0
Регистрация: 17.10.2014
Сообщений: 16
17.10.2014, 23:40  [ТС] 10
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
0
2427 / 1828 / 403
Регистрация: 15.12.2013
Сообщений: 8,060
18.10.2014, 01:09 11
Использовать set обязательно?
В исходном условии говорится,что нужно найти только количество.
По 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
using namespace System;
using namespace System::Numerics;
# include <ctime>
 
 int main(array<System::String ^> ^args)
{
    std::clock_t start;
    start = std::clock();
double duration;
BigInteger fact1=1;
BigInteger fact2=1;
BigInteger var3;
for (int  i = 1;  i <= 100 ;  ++i ) fact1 *= i;//перебираем до 2+заданное большее число
 
for (int  i = 1;  i <= 58 ;  ++i ) fact2 *= i;//перебираем до предыдущего числа - 2 заданное
 
var3=fact1-fact2;
Console::WriteLine(var3);
duration = ( std::clock() - start ) / (double) CLOCKS_PER_SEC;
 
Console::WriteLine(duration);
Console::ReadKey();
return 0;
}
P.S Код конечно странный,но под рукой не было библиотеки для длинной арифметики для чистых ++,а стопватч я запустить не смог
0
2827 / 1636 / 253
Регистрация: 03.12.2007
Сообщений: 4,222
18.10.2014, 13:52 12
Предыдущий код с оптимизированной Coprime, 0,92 секунды на не самом новом компе:
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
60
#include <cstdint>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <iostream>
 
using namespace std;
 
using int64 = int_fast64_t;
const int MAX_SIZE = 101;
 
bool Coprime(int a, int b)
{
    struct NumberDivisors : array<int64, MAX_SIZE>
    {
        NumberDivisors()
        {
            for (int i = 1; i <= MAX_SIZE / 2; i++)
                for (int j = i; j <= MAX_SIZE / 2; j += i)
                    (*this)[j] |= (int64)1 << i;
        }
    };
    static const NumberDivisors divisors;
    a = abs(a);
    b = abs(b);
    return a == b ? a == 1 : (divisors[a] & divisors[b]) == (1 << 1);
}
 
int main()
{
    int n, m;
    std::cin >> n >> m;
    n++, m++;
    int np = n * m;
    int64 c = (int64)np * (np - 1) * (np - 2);
    c -= m * (n * (n - 1) * (n - 2));
    c -= n * (m * (m - 1) * (m - 2));
    for (int y0 = 0; y0 < m; y0++)
    {
        for (int x0 = 0; x0 < n; x0++)
        {
            for (int y1 = y0 + 1; y1 < m; y1++)
            {
                int dy = y1 - y0;
                for (int x1 = 0; x1 < n; x1++)
                {
                    int dx = x1 - x0;
                    if ((y0 - dy >= 0 && x0 - dx >= 0 && x0 - dx < n) ||
                            dx == 0 || !Coprime(dx, dy))
                        continue;
                    int np = min((m - 1 - y0) / dy + 1, dx >= 0 ?
                        (n - 1 - x0) / dx + 1 :
                        x0 / -dx + 1);
                    c -= np * (np - 1) * (np - 2);
                }
            }
        }
    }
    cout << c / 6 << endl;
}
С bitset'ами помедленнее
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 <cstdint>
#include <cstdlib>
#include <algorithm>
#include <array>
#include <bitset>
#include <iostream>
 
using namespace std;
 
using int64 = int_fast64_t;
const int MAX_SIZE = 101;
 
bool Coprime(int a, int b)
{
    struct NumberDivisors : array<bitset<MAX_SIZE>, MAX_SIZE>
    {
        NumberDivisors()
        {
            for (int i = 1; i <= MAX_SIZE / 2; i++)
                for (int j = i; j <= MAX_SIZE; j += i)
                    (*this)[j].set(i);
        }
    };
    static const NumberDivisors divisors;
    return (divisors[abs(a)] & divisors[abs(b)]).reset(1).none();
}
 
int main()
{
    int n, m;
    std::cin >> n >> m;
    n++, m++;
    int np = n * m;
    int64 c = (int64)np * (np - 1) * (np - 2) / 6;
    c -= m * (n * (n - 1) * (n - 2) / 6);
    c -= n * (m * (m - 1) * (m - 2) / 6);
    for (int y0 = 0; y0 < m; y0++)
    {
        for (int x0 = 0; x0 < n; x0++)
        {
            for (int y1 = y0 + 1; y1 < m; y1++)
            {
                int dy = y1 - y0;
                for (int x1 = 0; x1 < n; x1++)
                {
                    int dx = x1 - x0;
                    if ((y0 - dy >= 0 && x0 - dx >= 0 && x0 - dx < n) ||
                            dx == 0 || !Coprime(dx, dy))
                        continue;
                    int np = min((m - 1 - y0) / dy + 1, dx >= 0 ?
                        (n - 1 - x0) / dx + 1 :
                        x0 / -dx + 1);
                    c -= np * (np - 1) * (np - 2) / 6;
                }
            }
        }
    }
    cout << c << endl;
}
0
1 / 1 / 0
Регистрация: 17.10.2014
Сообщений: 16
18.10.2014, 13:58  [ТС] 13
В 1 секнду при вводе 100 100 всё равно не укладывается
0
2827 / 1636 / 253
Регистрация: 03.12.2007
Сообщений: 4,222
18.10.2014, 14:10 14
g++ (i686-posix-dwarf-rev2, Built by MinGW-W64 project) 4.9.0
-O3
Pentium D 2,8 ГГц
На 100/100: 0.92-0.93 секунды без ввода данных.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.10.2014, 14:10
Помогаю со студенческими работами здесь

создать проект, который из цифр вводимого с клавиатуры будет считать количество цифр, которые принадлежат [15
Помогите !!! Создать проект, который из цифр вводимого с клавиатуры будет считать количество цифр,...

Из цифр двух натуральных чисел создать наибольшее возможное число, сохраняя порядок следования цифр
Есть задача: Требуется написать программу, которая из цифр двух натуральных чисел создает...

Ошибка SQL запрос: SET CHARACTER SET 'utf8';
Два года назад на одном из форумов некто задал вопрос (см. ниже), на который так никто и не...

Вводятся 3 натуральных числа. Найти сумму цифр каждого из них *(создать рекурсивную функцию для нахождения *суммы цифр п
#include &lt;iostream&gt; using namespace std; int Sum(int n) { int Summa=0; if(n&lt;10)...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru