Question

Сдать решение задачи 7-Интересное подмножество Полный балл: 100 Ограничение времени: 1 с Ограничение памяти: 512M Ограничение размера стека: 64M Задача 7: Интересное подмножество Дано множество натуральных чисел (все элементы множества попарно различны), упорядоченное по возрастанию значений. Интересным подмножеством исходного множества будем называть такое подмножество (возможно, полностью совпадающее с исходным множеством), что каждый его элемент больше мощности этого подмножества. Мощностью подмножества называется количество элементов в нем. Для данного множества необходимо найти размер наибольшего интересного подмножества, составленного из элементов этого множества. Входные данные Первая строка входных данных содержит целое число N — количество элементов исходного множества (1 ≤ N ≤ 105). В следующих N строках записаны целые числа ai по одному в строке — элементы исходного множества (1 ≤ ai ≤ 2×109), упорядоченные по возрастанию значений. Выходные данные Программа должна вывести одно целое число — размер наибольшего интересного подмножества. Система оценки Решения, правильно работающие при N = 5, будут оцениваться в 20 баллов. Решения, правильно работающие при N ≤ 12, будут оцениваться в 60 баллов. Примеры Ввод Вывод Пояснение 5 1 2 3 4 5 2 В множестве пять чисел: 1, 2, 3, 4, 5. В качестве интересного подмножества можно взять, например, подмножество {3, 5}. Его мощность равна 2 и все элементы этого подмножества больше 2. Интересного подмножества большего размера в данном примере не существует. Сдать решение на любом языке програмирования

Answer 1

import sys

L = [ int(input()) for i in range(int(input())) ]

L.sort()

L.reverse()

N = 0

for i in range(len(L)):

  if L[i] > S + 1:

     N += 1

  else:

     print(N)

     sys.exit(0)

Answer 2

Решение на языке программирования Python:

pythonCopy code
def find_largest_interesting_subset(arr):
    n = len(arr)
    largest_subset = [1] * n  # начальное значение - все элементы единицы

    for i in range(n):
        for j in range(i):
            if arr[i] % arr[j] == 0:  # если arr[i] делится на arr[j]
                largest_subset[i] = max(largest_subset[i], largest_subset[j] + 1)

    return max(largest_subset)

# Чтение входных данных
n = int(input())
arr = [int(input()) for _ in range(n)]

# Поиск размера наибольшего интересного подмножества
result = find_largest_interesting_subset(arr)

# Вывод результата
print(result)

Это решение использует динамическое программирование для нахождения размера наибольшего интересного подмножества. Оно работает за время O(N^2), где N - количество элементов в исходном множестве.