TopCoder problem "CardsAndSlots" used in TCCC07 Semi 1 (Division I Level One)



Problem Statement

    

You have n cards. Each card has some integer value, and some letter written on it. You also have n slots in a row. Each slot has some required value.

You must place the cards in the slots such that each slot contains a card with a value greater than or equal to the required value of that slot. You must order the cards such that the string formed by reading the letters on the cards from left to right comes as early as possible lexicographically while not violating the first rule.

You are given a int[] values and a String letters, the i-th elements of which are the value and letter, respectively, of the i-th card. You are also given a int[] required, the i-th element of which is the required value of the i-th slot. The slots are ordered from left to right. Place the cards into the slots as described above and return the resulting string. If there is no valid way to fill the slots, return an empty string instead.

 

Definition

    
Class:CardsAndSlots
Method:firstValid
Parameters:int[], String, int[]
Returns:String
Method signature:String firstValid(int[] values, String letters, int[] required)
(be sure your method is public)
    
 

Constraints

-values will contain between 1 and 50 elements, inclusive.
-Each element of values will be between 1 and 1000, inclusive.
-letters will contain exactly n characters, where n is the number of elements in values.
-letters will contain only uppercase letters ('A'-'Z').
-required will contain the same number of elements as values.
-Each element of required will be between 1 and 1000, inclusive.
 

Examples

0)
    
{1, 2, 3}
"ABC"
{2, 2, 1}
Returns: "BCA"
1)
    
{1, 2, 3, 4, 5}
"BBBAA"
{1, 1, 1, 1, 5}
Returns: "ABBBA"
Note that there can be equal letters on different cards.
2)
    
{1, 1}
"AA"
{2, 2}
Returns: ""
No card fits any slot.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10956&pm=8256

Writer:

andrewzta

Testers:

PabloGilberto , Olexiy , Jan_Kuipers , misof , ivan_metelsky

Problem categories:

Search