Саша

собирался на международную олимпиаду по информатике. Ему очень хотелось

подружиться с ребятами из разных стран и подарить каждому новому другу по

матрешке. Однако дорожная сумка была забита уже почти до отказа, и Саша решил

как можно лучше упаковать имеющиеся у него n матрешек.

Известно,

что одна матрешка помещается в другую, если ее размер строго меньше этой матрешки.

Например, матрешка размером 20 помещается в матрешку размером 25, но не

помещается в матрешку размером 20 или 10.

Формат входных данных:

Сначала

вводится n - количество матрешек (1 ≤ n ≤ 10000). Затем в одну строку через

пробел вводятся n

натуральных чисел m[i] (1 ≤ m[i ] ≤ 106).

Формат результата:

Вывести

одно натуральное число, являющееся минимальным количеством матрешек, в которые сможет Саша упаковать все

матрешки.

Question

Информатика

Минодора

8 апреля, 17:02

Саша

собирался на международную олимпиаду по информатике. Ему очень хотелось

подружиться с ребятами из разных стран и подарить каждому новому другу по

матрешке. Однако дорожная сумка была забита уже почти до отказа, и Саша решил

как можно лучше упаковать имеющиеся у него n матрешек.

Известно,

что одна матрешка помещается в другую, если ее размер строго меньше этой матрешки.

Например, матрешка размером 20 помещается в матрешку размером 25, но не

помещается в матрешку размером 20 или 10.

Формат входных данных:

Сначала

вводится n - количество матрешек (1 ≤ n ≤ 10000). Затем в одну строку через

пробел вводятся n

натуральных чисел m[i] (1 ≤ m[i ] ≤ 106).

Формат результата:

Вывести

одно натуральное число, являющееся минимальным количеством матрешек, в которые сможет Саша упаковать все

матрешки.

+4

Ответы (2)

Знаете ответ?

Корнюша · Answer 1

38 матрёшек поместется в сумку

Хиония · Answer 2

А m[i] от 1 до 106 или от 1 до 10^6?

Вообще-то неизвестно, сколько поместится, если не знать:

1) Сколько места осталось в сумке

2) Размер самой большой матрешки

3) Учтите, что может быть несколько групп матрешек, например

(25, 20, 18, 10) и (20, 18, 15, 10, 8) и (10, 8, 5, 3)

И все три группы могут влезть в сумку независимо друг от друга.

И еще. Вы понимаете, что если матрешек 10000 и их размеры от 1 до 10000 мм,

то самая крупная имеет диаметр 10000 мм = 10 м и не поместится ни в какую сумку?