Сдать решение задачи 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. Интересного подмножества большего размера в данном примере не существует.
Сдать решение на любом языке програмирования
dgadzieva50:
Нужен срочно ответ
Ответы
Ответ дал:
0
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)
Вас заинтересует
1 год назад
1 год назад
7 лет назад