Magic stones
Statement
Goal
You have a number N of magic stones each of which has a level with a positive integer value.The stones are very heavy and cumbersome to carry around.
Luckily you can use your magic powers to combine two stones of level
Use your power to minimise the number of stones that you have.
Input
Line 1: An integer N for the number of magic stones you have.
Line 2: N space separated integer values
Line 2: N space separated integer values
Output
Line 1: The minimum number of stones you can have.
Constraints
0 < N < 1000
Example
Input
2 1 1
Output
1
Tags
Greedy algorithms
Difficulty
Medium
Test cases
Axiom Test
Input
2
1 1
Output
1
Axiom Validator
Input
2
2 2
Output
1
Add me up Test
Input
3
1 2 1
Output
1
Add me up Validator
Input
3
4 3 3
Output
1
Too far Test
Input
3
1 1 5
Output
2
Too far Validator
Input
3
2 2 28
Output
2
Odd Test
Input
9
1 1 1 2 2 3 3 4 4
Output
5
Odd Validator
Input
11
1 5 4 3 2 1 5 4 3 2 1
Output
6
Powerless Test
Input
4
1 2 3 4
Output
4
Powerless Validator
Input
7
2 4 6 8 10 12 14
Output
7
Complex Test
Input
16
1 1 2 3 3 3 5 6 6 6 6 6 6 6 6 9
Output
2
Complex Validator
Input
18
2 5 2 4 2 4 2 1 2 1 2 2 2 2 3 3 3 3
Output
2
Huge Test
Input
1000
1 8 7 3 18 7 15 14 6 13 4 12 7 4 10 5 19 10 13 11 14 13 13 6 9 11 5 17 12 4 17 13 1 11 13 20 11 9 14 16 14 11 5 9 9 2 12 3 15 8 10 11 19 10 13 15 5 7 2 20 16 19 8 14 2 14 20 12 3 19 15 1 11 4 6 9 10 7 17 13 3 19 1 16 10 2 20 7 15 3 10 12 19 8 5 4 2 15 13 10 16 19 11 15 13 9 5 12 8 11 10 1 4 14 5 11 15 4 6 12 12 2 16 17 15 6 3 17 4 8 2 2 18 18 14 11 8 15 16 2 3 7 6 12 9 7 12 19 17 3 10 3 4 19 16 18 2 9 7 3 3 6 16 3 16 20 2 11 3 4 4 7 13 12 14 19 6 5 20 6 4 20 4 11 6 20 8 7 9 5 5 11 16 19 9 4 15 12 12 16 20 20 4 18 17 12 3 18 5 15 18 6 15 11 20 19 9 17 2 2 17 10 19 10 14 13 10 15 9 4 2 16 15 12 14 11 18 10 16 9 16 4 14 10 1 15 14 2 5 8 2 18 18 8 14 8 12 12 18 8 12 5 2 14 20 7 3 4 18 6 15 1 2 18 12 18 5 3 11 19 7 7 13 6 13 18 4 16 2 2 8 15 2 6 11 12 19 6 18 5 15 18 2 12 15 8 10 15 15 16 16 7 5 7 3 10 14 17 3 18 20 14 6 19 16 5 9 17 12 16 19 6 19 18 12 6 14 9 8 9 12 20 20 14 11 19 10 10 14 4 5 14 14 6 7 13 17 10 3 14 19 19 14 12 4 7 19 4 2 5 8 14 20 17 4 20 12 7 10 9 11 9 17 3 4 2 9 11 8 7 6 10 8 10 6 9 6 7 15 19 17 20 9 6 19 2 8 18 14 16 1 18 4 13 18 10 17 14 19 5 16 3 4 14 19 15 14 15 19 7 20 16 7 9 18 7 7 14 15 6 13 2 6 18 16 19 19 10 5 5 13 6 3 16 7 4 16 8 1 11 10 4 18 3 5 5 5 6 3 10 3 20 15 2 14 8 10 5 16 15 7 19 2 7 9 18 13 12 7 14 8 7 9 13 2 11 7 15 19 3 17 6 7 12 4 12 11 14 19 2 11 8 3 15 8 14 8 13 16 13 4 4 11 4 12 12 12 19 3 3 19 11 18 5 18 16 18 18 1 13 18 19 8 8 7 6 7 14 7 2 16 17 2 12 2 15 6 13 11 17 13 7 2 13 10 14 13 14 14 11 4 6 20 17 11 14 3 11 16 17 10 10 13 8 5 9 16 17 15 14 8 2 7 5 10 16 3 7 13 7 11 11 10 11 17 19 11 15 16 7 14 1 2 16 11 3 2 15 10 16 17 8 16 19 14 3 4 9 4 3 8 16 16 15 13 3 1 9 19 16 17 9 7 6 16 6 15 13 3 18 15 18 12 4 9 7 6 15 6 9 13 4 10 7 4 20 10 11 18 14 2 13 13 10 3 5 14 6 15 7 15 7 7 16 12 12 6 20 4 1 4 6 3 12 9 18 13 4 9 10 2 15 13 9 14 9 2 16 20 9 6 4 13 17 18 20 5 9 7 8 1 5 3 8 3 15 11 1 15 1 13 14 19 17 9 4 4 14 6 12 14 9 5 8 6 16 4 13 4 3 13 14 18 18 8 1 15 2 6 4 2 5 14 14 15 19 3 14 14 5 2 16 2 14 11 1 16 12 17 8 18 4 16 3 15 13 17 19 4 14 8 1 7 15 17 15 5 11 5 13 9 10 14 11 15 11 17 8 11 18 3 1 12 12 14 17 16 7 15 11 15 1 3 10 2 18 5 16 9 2 7 19 3 19 15 5 6 12 4 6 4 13 15 16 13 9 11 16 3 20 5 9 3 15 2 15 8 19 20 6 13 4 4 10 16 6 7 6 10 6 7 4 8 11 13 9 16 18 20 14 18 8 11 7 11 11 9 2 10 9 12 20 7 14 8 13 9 6 10 16 18 13 16 8 10 10 18 18 5 11 9 1 2 6 10 19 6 4 3 8 20 2 20 17 1 6 15 14 17 3 7 12 16 2 12 5 5 16 15 16 15 6 11 14 3 7 12 19 13 15 11 7 6 12 18 12 5 4 8 19 8 9 18 19 4 14 3 8 13 8 10 2 16 9 14 11 17 16 14 18 9 6 15 5 13 16 9 18 18 5 6 10 5 14 3 9 20 9 6 14
Output
12
Huge Validator
Input
1000
24 24 15 7 26 20 2 14 20 3 30 14 22 13 22 26 12 30 20 27 27 26 22 28 12 12 5 29 8 16 24 12 5 4 4 18 23 26 7 7 14 26 21 14 8 16 22 23 12 19 30 8 21 28 17 28 22 6 15 8 24 8 15 6 5 28 20 21 18 30 21 12 26 1 18 5 25 15 14 16 22 19 2 29 3 7 29 5 29 15 6 17 16 20 16 16 8 25 18 11 12 14 20 2 3 16 17 7 8 21 9 20 12 11 18 6 21 2 13 23 11 21 22 5 28 26 7 17 21 22 5 26 4 4 9 17 21 9 14 20 17 18 16 17 21 27 13 29 3 29 22 7 6 16 19 14 7 28 24 3 14 28 22 24 9 26 20 22 17 28 18 20 16 17 12 12 18 15 11 26 15 20 25 30 20 28 17 8 20 4 29 2 30 5 28 13 23 17 19 9 4 2 26 14 28 5 26 21 22 10 21 14 4 19 28 8 19 23 11 20 30 16 29 10 23 14 15 4 27 19 20 15 15 30 8 7 2 16 12 8 13 22 3 6 3 5 23 1 4 9 16 26 6 22 4 26 27 17 28 23 25 27 17 22 20 9 26 14 20 25 20 23 13 17 15 22 14 23 27 15 4 8 14 25 2 28 4 10 12 24 5 23 15 4 14 26 19 9 21 12 30 4 24 23 14 21 16 19 13 12 12 7 10 3 27 8 22 15 26 13 6 18 27 25 21 10 6 8 24 9 12 3 19 20 10 11 26 14 4 25 10 29 2 20 22 12 23 12 11 7 12 19 24 25 12 18 4 8 19 29 28 5 17 19 16 8 29 30 30 11 29 20 5 21 21 16 22 16 10 18 8 28 26 1 28 30 18 18 10 16 11 8 20 3 4 21 30 7 16 14 6 26 3 16 25 30 5 24 27 18 21 4 4 3 21 14 20 1 6 18 12 19 14 13 21 4 10 4 20 7 20 21 17 10 12 20 7 20 13 14 9 22 26 28 24 7 3 30 17 11 14 16 28 23 19 6 16 29 14 25 26 9 18 3 25 2 19 3 22 27 19 27 5 9 9 14 9 25 13 12 1 5 23 3 28 4 21 9 5 3 2 5 3 28 15 6 16 9 19 23 2 2 6 16 29 20 3 30 10 7 12 3 8 14 11 28 18 19 13 5 13 26 12 7 10 9 17 25 15 8 17 15 28 16 1 14 9 26 13 7 22 15 7 10 2 23 19 28 12 2 23 13 3 5 2 11 10 25 11 25 16 23 13 14 24 10 18 3 15 3 22 23 14 22 20 2 5 10 4 1 8 3 3 17 13 6 29 7 21 5 8 17 9 27 30 30 15 30 24 16 30 1 6 14 24 13 27 20 25 4 17 13 13 2 21 17 17 12 14 2 6 1 15 22 22 20 25 2 15 16 15 21 19 14 27 8 24 6 27 1 6 29 8 15 11 4 8 10 23 22 4 23 26 20 26 13 25 30 18 26 2 11 22 13 27 25 17 25 20 2 2 18 16 15 17 6 5 1 28 11 8 19 22 18 8 22 25 23 8 11 13 22 5 8 21 21 29 2 3 3 25 26 3 18 14 27 16 26 19 2 26 19 5 5 10 9 14 3 30 24 1 14 12 19 19 20 20 6 28 7 24 15 22 27 15 26 14 10 19 5 13 13 9 26 20 5 12 17 23 1 25 4 14 8 2 11 7 18 26 3 12 9 17 2 22 15 9 26 27 19 28 19 15 12 9 4 28 13 17 23 21 23 24 25 8 16 17 17 5 19 23 15 7 13 21 25 24 28 23 12 9 15 3 29 12 19 3 18 26 16 9 21 23 4 17 25 2 22 29 4 4 26 17 14 12 16 13 24 3 29 25 5 24 11 27 7 18 17 22 8 29 1 17 1 15 3 3 26 14 2 30 24 12 14 2 24 11 8 20 18 20 15 26 19 8 13 23 26 11 7 4 12 18 12 27 22 6 16 22 3 25 17 21 15 8 23 12 2 22 16 17 3 15 23 22 22 4 4 3 22 17 9 25 4 14 1 11 5 8 28 6 7 1 8 19 6 15 25 19 6 22 8 11 23 18 20 7 18 21 8 15 23 15 5 30 22 9 3 24 20 29 5 3 13 2 8 9 23 22 27 18 14 12 29 15 20 30 30 16 17 16 4 10 20 28 4 3 13 8 25 17 26 4 15 28 12 13 6 12 15 17 27 12 16 25 1 7 20 22 16 18 10 14 6 16 15 2 11 16 10
Output
18
Solution language
Solution
Stub generator input