TopCoder problem "TheNumbersLord" used in SRM 381 (Division II Level Three)



Problem Statement

    

Recently, John had a dream where he was a lord in a world of positive integers. As with all lords, he had to solve a very difficult problem.

John has a list of positive integers. He must pick exactly n integers using this list and concatenate them in any order to produce the largest possible number. The same integer in the list can be chosen multiple times, but each integer must be chosen at least once.

You are given a int[] numbers and an int n. Return the largest possible integer that John can create as a String.

 

Definition

    
Class:TheNumbersLord
Method:create
Parameters:int[], int
Returns:String
Method signature:String create(int[] numbers, int n)
(be sure your method is public)
    
 

Notes

-numbers may contain duplicate values. In this case, each integer must be chosen at least as many times as the number of its occurrences in numbers.
 

Constraints

-numbers will contain between 1 and 50 elements, inclusive.
-Each element of numbers will be between 1 and 1,000,000,000, inclusive.
-n will be between the number of elements in numbers and 50, inclusive.
 

Examples

0)
    
{3,2,7}
3
Returns: "732"
Clearly, it is impossible to get a number greater than 732.
1)
    
{4, 7}
4
Returns: "7774"
2)
    
{1, 10, 100}
4
Returns: "110100100"
To get the largest possible number, John must use 100 twice.
3)
    
{4,4,4,4}
9
Returns: "444444444"
Here there is no choice for John at all.
4)
    
{1,1,2}
3
Returns: "211"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8419

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10804&pm=8419

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , Olexiy , ivan_metelsky , ged

Problem categories:

Sorting