0 / 0 / 0
Регистрация: 06.06.2020
Сообщений: 4
1

Распределить гири по парам так, чтобы суммарный вес гирь в каждой паре выражался простым числом

08.07.2020, 15:48. Показов 1366. Ответов 7
Метки нет (Все метки)

Простые гири

(Время: 1 сек. Память: 16 Мб Сложность: 54%)

Имеются гири с массами: 1 г, 2 г, …, N г .Требуется написать программу, распределяющую эти гири на максимально возможное количество пар так, чтобы суммарный вес гирь в каждой паре выражался простым числом.


Входные данные

Входной файл INPUT.TXT содержит единственное натуральное число N, не превосходящее 500 000.


Выходные данные

В выходной файл OUTPUT.TXT выведите список найденных пар. Каждая пара выводится в одной строке через пробел.



Пытаюсь решить эту задачу уже 2 дня, но все равно WA на 3 тесте + я заметил, что моя программа работает слишком долго
на значениях больше 600 (ограничение - 1 сек). В общем, помогите пожалуйста оптимизировать код и решить проблему с 3 тестом, буду благодарен.
Вот код:
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
#include <iostream>
#include <cmath>
#include <cassert>
#include <algorithm>
#include <vector>
 
#include <_types/_uint32_t.h> /* typedef unsigned int uint32_t, если файл не найден */
 
bool IsPrime(uint32_t num) // проверка на простоту
{
    if (num % 2 == 0 && num != 2)
    {
        return false;
    }
    for (uint32_t i = 3; i <= std::sqrt(num); i += 2)
    {
        if (num % i == 0)
        {
            return false;
        }
    }
    return true;
}
 
int main()
{
    uint32_t n;
    std::cin >> n;
    assert(1 <= n && n <= 500000);
    std::vector<uint32_t> usedWeights; // массив, в котором хранятся «использованные» гири.
    for (uint32_t i = 1; i <= std::floor(n / 2); i++)
    {
        for (uint32_t j = n; j > n / 2; j--)
        {
            if (std::find(usedWeights.begin(), usedWeights.end(), i) != usedWeights.end())
                // если i-ая гиря использовалась, то выходим с цикла.
            {
                break;
            }
            if (std::find(usedWeights.begin(), usedWeights.end(), j) == usedWeights.end())
                // если j-ая гиря не использовалась, то проходим дальше.
            {
                if (IsPrime(i + j))
                    /* если i+j - простое число, то записываем i и j
                       в массив с использованными гирями, после чего выводим i и j. */
                {
                    usedWeights.push_back(i);
                    usedWeights.push_back(j);
                    std::cout << i << " " << j << '\n';
                }
            }
        }
    }
    return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.07.2020, 15:48
Ответы с готовыми решениями:

Надо сделать так чтобы верхний предел интегрирования выражался переменной
Объясните пожалуйста почему данные вычисления не выполняются в MathCAD: Посмотрите вложения! Если...

Распределить числа на несколько групп так, чтобы в каждой группе суммы чисел были наиболее близки
Доброго времени суток! Есть некоторый набор чисел. Нужно распределить эти числа на несколько групп...

Вычислить суммарный вес каждой коробки конфет
Доброго времени суток! помогите пожалуйста найти ошибку в программе! Задание такое: Дан список...

Распределить денежные средства между предприятиями, чтобы суммарный прирост выпуска продукции был максимальным
Для реконструкции и модернизации производства на 4 предприятиях выделены денежные средства в объеме...

7
Модератор
Эксперт С++
12080 / 9759 / 5902
Регистрация: 18.12.2011
Сообщений: 26,196
08.07.2020, 15:56 2
Вот есть на паскале
Распределить гири на максимально возможное количество пар
1
Модератор
Эксперт по электронике
8695 / 6493 / 879
Регистрация: 14.02.2011
Сообщений: 22,714
08.07.2020, 16:03 3
Цитата Сообщение от vpalesos Посмотреть сообщение
bool IsPrime(uint32_t num)
мелочь конечно но 0 и 1 выведутся как простые числа
Цитата Сообщение от vpalesos Посмотреть сообщение
if (num % 2 == 0 && num != 2)
исправь на
C++
1
if (num % 2 == 0 && num>2 || num<2 )
Цитата Сообщение от vpalesos Посмотреть сообщение
for (uint32_t i = 3; i <= std::sqrt(num); i += 2)
на каждой итерации считать корень не жирно ли?
или так
C++
1
2
int MySqrt=std::sqrt(num);
for (uint32_t i = 3; i <=MySqrt; i += 2)
или так
C++
1
for (uint32_t i = 3; i*i <=num; i += 2)
Добавлено через 4 минуты
вот тема где обсуждалось как быстрее проверить число на простоту
Быстрая проверка натурального числа на простоту
1
Диссидент
Эксперт C
26826 / 16735 / 3666
Регистрация: 24.12.2010
Сообщений: 37,464
08.07.2020, 23:39 4
Вот абсолютно идентичная тема
Сумма чисел простое число
Правда решить мне ее не удалось. Так, набросал некоторые соображения и общий подход.
Однако, решение по ссылке в посте 2 представляется слишком простым, чтобы быть верным. Увы! Паскаль я знаю весьма плохо, и ничего конкретнее сказать не могу. Возможно и ошибаюсь.

Добавлено через 7 минут
В любом случае каждый раз определять простоту суммы довольно накладно. Можно составить массив M x K, где M - количество четных чисел, K - количество нечетных. И сразу заполнить его нулями и единичками в зависимости от простоты суммы. Тогда и эффективность определения простоты не имеет решающего значения.

Добавлено через 8 минут
Имхо, код приведенный по ссылке в посте 2, вообще решает какую-то другую задачу. Хоть и помечен, как Лучший ответ.

Добавлено через 14 минут
vpalesos, вот маленький тестик. N = 8. Ответ должен быть
1+6
2+5
3+8
4+7
А что дает ваша программа?

Добавлено через 1 час 39 минут
Однако, решение найдено! Даже вскочил с кровати!
Базируется, правда, на постулате Бертрана, но само по себе чрезвычайно просто.
Оказывается таких пар всегда будет N/2. И их легко построить.
Решение привел в теме по ссылке
1
701 / 523 / 301
Регистрация: 24.02.2017
Сообщений: 1,873
09.07.2020, 13:36 5
Цитата Сообщение от Байт Посмотреть сообщение
Сумма чисел простое число
Начало теории нормальное, а дальше требуются исправления: если P - минимальное простое, большее N то у нас останутся гири 1 ... (P-N-1). И к ним ту же процедуру применять нельзя.
Пример: N=24 и P=29. Остаются гири 1,2,3,4. Минимальное P=5. Применяем ту же процедуру пока N - P - 1 > 0 (правильно будет P-N-1>0) получаем пары 3-2 ; 2-3 и 1-4. Следовательно нужна проверка на одинаковость пар.
И еще поиск простого числа при N=500 000 займет больше 1 секунды времени.
Эта тема обсуждалась еще в 2009г. по этой ссылке https://forum.shelek.ru/index.... 591.0.html

Добавлено через 15 минут
Что бы исключить одинаковые пары надо добавить условие проверки 2N-P=1 где N текущее значение гири.
0
Байт
09.07.2020, 22:42
  #6

Не по теме:

Цитата Сообщение от повар1 Посмотреть сообщение
Эта тема обсуждалась еще в 2009г. по этой ссылке https://forum.shelek.ru/index.... 591.0.html
Такого тягучего бреда я еще не встречал

0
701 / 523 / 301
Регистрация: 24.02.2017
Сообщений: 1,873
09.07.2020, 23:36 7
Цитата Сообщение от Байт Посмотреть сообщение
Даже вскочил с кровати!
там же прелдожен такой же алгоритм что и у Вас. Только минимальное меньше N, но это суть не меняет.
0
0 / 0 / 0
Регистрация: 06.06.2020
Сообщений: 4
13.07.2020, 14:04  [ТС] 8
Большое всем спасибо!
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.07.2020, 14:04
Помогаю со студенческими работами здесь

Для рюкзака с n предметов выбрать такие, чтобы их суммарный вес был не более m кг
Задача о рюкзаке. Нужно для рюкзака с n предметов выбрать такие, чтобы их суммарный вес был не...

Из заданных семи предметов выбрать такие, чтобы их суммарный вес в рюкзаке был менее N кг, а стоимость – наибольшей.
Ввод входных данных: может быть организован как с клавиатуры, так и из текстового файла. Вывод...

Распределить гири на максимально возможное количество пар
Имеются гири с массами 1г, 2г, ...,N г (N &lt;= 10000). Написать алгоритм и программу, распределяющую...

Распределить гири на максимально возможное количество пар
Имеются гири с массами: 1г, 2г,..., N г (N меньше или равно 500000). Написать программу,...

Для каждого статуса поставщика посчитать суммарный вес, средний вес и количество уникальных заказных товаров
Вот таблицы spool cre_demo.log CONNECT demo/demo@ORCL prompt prompt Creating table ПОСТАВЩИКИ...

Собрать заданный вес из массива гирь
Имеются десять гирь весом a1, a2, ..., a10. Обозначим через ck — число способов, которыми можно...


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

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

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