Найдите количество чисел в максимальном подмножестве данного множества

@Евгений309 · Регистрация: 13.06.2023

Студворк — интернет-сервис помощи студентам

Вам дан список целых положительных чисел -ударная сила различных типов оружия в игре. Найдите количество чисел в максимальном подмножестве данного множества, обладающем тем свойством что и все числа из этого подмножества могут быть расположены в цепочку так что каждое число либо делит либо делится на своего соседа
Первая строка ввода содержит T (1<T<35).Каждая из следующих T строк содержит количество элементов множества N (1<N<17) и N целых положительных чисел, каждое от 1 до 10^9 включительно.
Выведите T строки вида Case # A: B, где A - номер текста (начиная с 1), B - искомая величина для данного текста. С++

standard input
2

3123

523456

standard output
Case#1: 3
Case#2: 4

Вот вариант моего кода но мне дает результат только изменение кол-ва строк но сами значения не изменяются.

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
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int N;
        cin >> N;
        vector<int> a(N);
        for (int i = 0; i < N; i++) {
            cin >> a[i];
        }
        vector<int> dp(N, 1);
        int ans = 1;
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (a[i] > a[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        cout << "Case #" << t << ": " << ans << endl;
    }
    return 0;
}

@KSergey9 · 13.06.2023, 12:19

Сообщение от Евгений309

standard input
2
3123
523456

Потеряны пробелы? или как интерпретировать эти строки?

Добавлено через 7 минут

Сообщение от Евгений309

dp[i] = max(dp[i], dp[j] + 1);

Вы ищите какой-то максимум между числами, а задании что-то явно другое (только с трудом понимаю что):

Сообщение от Евгений309

обладающем тем свойством что и все числа из этого подмножества могут быть расположены в цепочку так что каждое число либо делит либо делится на своего соседа

Вероятно "делится нацело"?
Если так - надо здорово покумекать над алгоритмом, у меня как-то не с ходу идей как такое проверять / считать

@gunslinger · 13.06.2023, 14:11

Да, там (полагаю) потеряны пробелы:

2
3 1 2 3
5 2 3 4 5 6

Суть задачи, видимо, в том, чтобы выполнялось следующее условие (при итоговом расположении) для соседних чисел:

Code
1
(НОД(a, b) == a || НОД(a, b) == b)

Для примера выше это будет (как вариант) так:

2 1 3 -> 3 числа
3 6 2 4 5 -> 4 числа (кроме 5-ки - она "выпадает")

И, как всегда, главный вопрос - способ расположения чисел "оптимальным" образом - остается открытым (по крайней мере для меня).

@KSergey9 · 13.06.2023, 14:15

Сообщение от gunslinger

способ расположить числа "оптимальным" образом - остается открытым

И я о той же проблеме.
Есть ли способ эффективнее полного перебора?

Добавлено через 1 минуту

Сообщение от gunslinger

Code
1
(НОД(a, b) == a || НОД(a, b) == b)

Ну прям НОД искать не обязательно. Просто a%b == 0 || b%a == 0

@gunslinger · 13.06.2023, 14:33

Насчет НОД согласен. Только тогда уж проверять остатки от деления: a%b и b%a (очевидно, один из них должен быть равен 0).
А касаемо способа "кроме перебора" - тут хз, можно находить делители чисел и как-то подбирать "соседей", но четкого алгоритма придумать не могу.

Добавлено через 11 минут
Можно вокруг бОльшего числа (рядом с ним) ставить числа, являющиеся его делителями.
В начале ставить число, у которого мало (или нет) делителей, и оно само мало для кого является делителем.
В конце такой же принцип соблюдаем.
Но все это какой-то "набросок идеи".
Могу предположить, что в теории подойдет использование чего-то вроде std::next_permutation (или как там точно), но полностью в этом не уверен.

@KSergey9 · 13.06.2023, 14:34

Сообщение от gunslinger

Только тогда уж проверять остатки от деления: a%b и b%a

Я написал деление, подумал и исправил.
Видимо вы успели прочитать исходный текст

@gunslinger · 13.06.2023, 14:47

Не по теме:

Успел...

Добавлено через 9 минут
А хотя чем не подойдет какое-то подобие перебора?
В каждой строке N < 17 элементов. Пусть даже строк T < 35.
Но если для отдельной строки "перебор" будет работать достаточно шустро, то и для всех строк суммарное время особо большим не станет.

Байт · 13.06.2023, 19:05

ИМХО, Суть задачи в том, чтобы найти цепь максимальной длины в неориентированном графе

@gunslinger · 14.06.2023, 16:43

Сделал набросок - генерация чисел-элементов для отдельной строки, плюс некое "подобие графа" (в виде диагональной матрицы), если я правильно понимаю суть.

Остается найти цепь макс. длины (и тут "мои полномочия всё").

C++
1
2
3
4
5
6
7
8
9
10
11
12
  const N = 16;
  unsigned long num[N], max_val = 1000;  // вплоть до 10^9
  bool arr[N][N];
 
  for (int i = 0; i < N; i++)
    num[i] = random(max_val) + 1;
 
  std::sort(num, num + N);
 
  for (int i = N - 1; i >= 1; i--)
    for (int j = i - 1; j >= 0; j--)
      arr[i][j] = !(num[i] % num[j]);

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@gunslinger place status here 3186 / 2220 / 640 Регистрация: 20.07.2013 Сообщений: 6,008
	13.06.2023, 14:33
	Насчет НОД согласен. Только тогда уж проверять остатки от деления: a%b и b%a (очевидно, один из них должен быть равен 0). А касаемо способа "кроме перебора" - тут хз, можно находить делители чисел и как-то подбирать "соседей", но четкого алгоритма придумать не могу. Добавлено через 11 минут Можно вокруг бОльшего числа (рядом с ним) ставить числа, являющиеся его делителями. В начале ставить число, у которого мало (или нет) делителей, и оно само мало для кого является делителем. В конце такой же принцип соблюдаем. Но все это какой-то "набросок идеи". Могу предположить, что в теории подойдет использование чего-то вроде std::next_permutation (или как там точно), но полностью в этом не уверен. 0

@gunslinger place status here 3186 / 2220 / 640 Регистрация: 20.07.2013 Сообщений: 6,008
	13.06.2023, 14:47
	Не по теме: Успел... Добавлено через 9 минут А хотя чем не подойдет какое-то подобие перебора? В каждой строке N < 17 элементов. Пусть даже строк T < 35. Но если для отдельной строки "перебор" будет работать достаточно шустро, то и для всех строк суммарное время особо большим не станет. 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	13.06.2023, 19:05
	ИМХО, Суть задачи в том, чтобы найти цепь максимальной длины в неориентированном графе 1

Найдите количество чисел в максимальном подмножестве данного множества

Решение