Stacking Cups

Points: 1

Time limit: 2.0s

Memory limit: 256M

Author:

PHPeasant

Problem type

Allowed languages

C, C++, Haskell, ~~Java~~, Python

It's time to do the dishes! The household logistics division (you) have been tasked with stacking the various cups, bowls and other topologically similar vessels to minimise the amount of shelf-space they take up.

There are \(N\) such vessels in the kitchen each with a diameter \(d_i\). It is possible to stack any vessel of a smaller diameter into one with a larger diameter which can, in turn, be stacked into another.

Find the smallest number of stacks you need to store all of your cup-esque vessels.

Input Specification

Two lines. The first contains \(N (1 \leq N \leq 1000)\) the number of vessels in the kitchen. The second contains \(N\) space-separated integers \(d_i (1 \leq d_i \leq 10000)\), the diameter of the ith vessel.

Output Specification

The number of stacks needed to store all items.

Sample Input 1

5
3 2 1 2 1

Sample Output 1

Sample Input 2

3
100 2 2

Sample Output 2

Comments

0

max commented on March 9, 2022, 1:57 a.m.

This problem contains a few test cases with \(N > 1000\) contradicting the Input Specification. See this submission for more information.