Саша
собирался на международную олимпиаду по информатике. Ему очень хотелось
подружиться с ребятами из разных стран и подарить каждому новому другу по
матрешке. Однако дорожная сумка была забита уже почти до отказа, и Саша решил
как можно лучше упаковать имеющиеся у него n матрешек.
Известно,
что одна матрешка помещается в другую, если ее размер строго меньше этой матрешки.
Например, матрешка размером 20 помещается в матрешку размером 25, но не
помещается в матрешку размером 20 или 10.
Формат входных данных:
Сначала
вводится n – количество матрешек (1 ≤ n ≤ 10000). Затем в одну строку через
пробел вводятся n
натуральных чисел m[i] (1 ≤ m[i] ≤ 106).
Формат результата:
Вывести
одно натуральное число, являющееся минимальным количеством матрешек, в которые сможет Саша упаковать все
матрешки.
собирался на международную олимпиаду по информатике. Ему очень хотелось
подружиться с ребятами из разных стран и подарить каждому новому другу по
матрешке. Однако дорожная сумка была забита уже почти до отказа, и Саша решил
как можно лучше упаковать имеющиеся у него n матрешек.
Известно,
что одна матрешка помещается в другую, если ее размер строго меньше этой матрешки.
Например, матрешка размером 20 помещается в матрешку размером 25, но не
помещается в матрешку размером 20 или 10.
Формат входных данных:
Сначала
вводится n – количество матрешек (1 ≤ n ≤ 10000). Затем в одну строку через
пробел вводятся n
натуральных чисел m[i] (1 ≤ m[i] ≤ 106).
Формат результата:
Вывести
одно натуральное число, являющееся минимальным количеством матрешек, в которые сможет Саша упаковать все
матрешки.
Answers & Comments
Вообще-то неизвестно, сколько поместится, если не знать:
1) Сколько места осталось в сумке
2) Размер самой большой матрешки
3) Учтите, что может быть несколько групп матрешек, например
(25, 20, 18, 10) и (20, 18, 15, 10, 8) и (10, 8, 5, 3)
И все три группы могут влезть в сумку независимо друг от друга.
И еще. Вы понимаете, что если матрешек 10000 и их размеры от 1 до 10000 мм,
то самая крупная имеет диаметр 10000 мм = 10 м и не поместится ни в какую сумку?
Verified answer
38 матрёшек поместется в сумку