Дано множество натуральных чисел (все элементы множества попарно различны), упорядоченное по возрастанию значений. Интересным подмножеством исходного множества будем называть такое подмножество (возможно, полностью совпадающее с исходным множеством), что каждый его элемент больше мощности этого подмножества. Мощностью подмножества называется количество элементов в нем. Для данного множества необходимо найти размер наибольшего интересного подмножества, составленного из элементов этого множества.
Входные данные
Первая строка входных данных содержит целое число N — количество элементов исходного множества (1 ≤ N ≤ 105).
В следующих N строках записаны целые числа ai по одному в строке — элементы исходного множества (1 ≤ ai ≤ 2×109), упорядоченные по возрастанию значений.
Выходные данные
Программа должна вывести одно целое число — размер наибольшего интересного подмножества.
Система оценки
Решения, правильно работающие при N = 5, будут оцениваться в
Решения, правильно работающие при N ≤ 12, будут оцениваться в
Примеры
Ввод
Вывод
Пояснение
5
1
2
3
4
5
2
В множестве пять чисел: 1, 2, 3, 4, 5. В качестве интересного подмножества можно взять, например, подмножество {3, 5}. Его мощность равна 2 и все элементы этого подмножества больше 2. Интересного подмножества большего размера в данном примере не существует
В Вашем задание напитки стоят в следующем порядке по предпочтению
'Кон Панна', 'Латте Маккиато', 'по-венски', 'Маккиато', 'Капучино', 'Эспрессо '
однако в приведённом примере [4, 4, 0] 'Капучино' почему то находится предпочтительнее 'Маккиато', что противоречит условию задачи. Ну да ладно.
Сделал на Python с применением рекурсии. Всё считается замечательно. Если будут вопросы - задавайте.
Объяснение:
Espresso=(1,0,0)
Capuchino=(1,3,0)
Maciato=(2,1,0)
Viena=(1,0,2)
LateMak=(1,2,1)
ConPanna=(1,0,1)
mss=(ConPanna, LateMak, Viena, Maciato, Capuchino, Espresso)
mssName=('Кон Панна', 'Латте Маккиато', 'по-венски', 'Маккиато', 'Капучино', 'Эспрессо ')
coff, milk, sl = map(int, input('Введите количество кофе_молока_сливок: ').split() )
def choose_coffee(ind, var, preference0, preference1, preference2):
if ((mss[ind][0] <= preference0) and (mss[ind][1]<=preference1) and (mss[ind][2]<=preference2)):
preference0 = preference0 - mss[ind][0]
preference1 = preference1 - mss[ind][1]
preference2 = preference2 - mss[ind][2]
print(mssName[ind])
var += 1
ind += 1
if ind<6:
choose_coffee(ind, var, preference0 , preference1, preference2)
if (var==0)and(ind==6):
print('Вариантов нет')
exit
choose_coffee(0, 0, coff, milk, sl)
надеюсь