ColourOrCountry | Topcoder Archive

Problem Statement

Colour or Country was invented in 1998 by a University of Waterloo student who wanted to come up with a game whose outcome was entirely determined by skill and yet was entirely uninteresting. Gameplay is as follows: play progresses in some order. When it is your turn, you must say either the name of a color or the name of a country. If you say the name of a country, you lose and are eliminated. The last person remaining who is not eliminated is the winner.

The winning strategies for this game are myriad and trivial; this problem will not ask for any of them. Instead, it is now your turn, and you want to say a color. But you don't want to say something mundane like "red" or "blue" or "puce". Instead, you wish to embellish with some number of adjectives, like "light" or "dark" or maybe "greenish".

You will form a color by concatenating up to five adjectives, each separated by one space, and then appending a base word. For example, if possible adjectives were "light" and "dark" and possible base words were "red" and "blue", then "light red", "blue", "light dark light blue", and "light light light light light red" would all be valid colors, but "light light light light light light red", "red blue", and "light" would not.

Given a String[] adjectives, the adjectives you can come up with, a String[] base representing the base words you can come up with, and an int N, your method should return the Nth color that you can form (0-indexed) when all valid colors are sorted lexicographically. If N is greater than or equal to the number of valid colors, your method should return the String "Belgium" (quotes for clarity).

Note that since no two elements of adjectives will be the same, and no two elements of base will be the same, there will be no duplicate color names.

Definition

Class:: ColourOrCountry
Method:: nthColour
Parameters:: String[], String[], int
Returns:: String
Method signature:: String nthColour(String[] adjectives, String[] base, int N)
(be sure your method is public)

Notes

Lexicographical ordering on strings means that if a string A comes before a string B, then either: (a) the first character where A and B differ is less in A than in B, when considered in ASCII, or (b) A is shorter in length than B and the string B can be formed by taking string A and appending at least one character.

Constraints

adjectives will contain between 1 and 6 elements, inclusive.
no element of adjectives will be "Belgium"
each element of adjectives will be between 1 and 20 characters in length and will contain only alphanumeric characters
no two elements of adjectives will be the same
base will contain between 1 and 6 elements, inclusive.
no element of base will be "Belgium"
each element of base will be between 1 and 20 characters in length and will contain only alphanumeric characters
no two elements of base will be the same
N will be between 0 and 10000000, inclusive.

Examples

```
{"dark", "light"}
```
```
{"red", "blue"}
```
```
2
```
```
Returns: "dark dark blue"
```
After creating and sorting all the valid colors (there are 126 of them), the beginning of the list goes: blue, dark blue, dark dark blue, ...
```
{"dark", "light"}
```
```
{"red", "blue"}
```
```
72
```
```
Returns: "light dark dark light blue"
```
The list around element 72 looks like: ..., light dark dark dark light red, light dark dark dark red, light dark dark light blue, light dark dark light dark blue, light dark dark light dark red, ...

{"greenish"}

{"gray", "red", "pink", "lavender", "belgium"}

Returns: "Belgium"

With a maximum of 6 valid colors, there's no way we can ask for color 30000.

{"problem", "isnt", "too", "this", "difficult"}

{"right", "of", "way", "cheese"}

Returns: "this problem isnt too difficult right"

{"onion"}

{"onion"}

Returns: "onion onion onion"

{"A", "b", "C", "dd", "E", "F"}

{"9", "4", "2", "7", "9902", "fortysix"}

Returns: "F C C b A fortysix"

{"belgium", "doesnt", "equal", "capital"}

{"belgium"}

Returns: "Belgium"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.