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)