Princess | Topcoder Archive

Problem Statement

The time has come for Princess Maria to get married. The suitors are lined up outside the castle. She wants to marry the most generous (rich) one; that is the one with the most expensive gift. By the kingdom's rules, the suitors come to the Princess one by one for an interview (with gifts). At the end of each interview Maria has to either reject or accept the marriage proposal. That is, at the moment of the decision, she doesn't know anything about suitors left in line, and she can't request that a rejected person comes back. She wants to maximize her chance of marrying the most generous/rich one. From her high school probability course she knows that the best strategy is to skip K suitors (K depends on the number of all suitors), to see a sample of what life has to offer, and then to pick the first one which is better than the best of the skipped ones. If there is no such person, then the last one is picked.

Your task is, given an int[] of values of gifts in thousands of dollars in the order the suitors are lined up outside the castle (in the order the suitors will come to greet Maria) and an int representing how many suitors Maria decides to skip, return the index number of her future husband (first suitor is indexed 1, etc.).

Definition

Class:: Princess
Method:: husband
Parameters:: int[], int
Returns:: int
Method signature:: int husband(int[] suitors, int skip)
(be sure your method is public)

Constraints

suitors contains between 1 and 50 elements inclusive
each element of suitors is an integer between 0 and 10000 inclusive
skip is an integer between 0 and the number of suitors minus 1, inclusive

Examples

```
{1}
```
```
0
```
```
Returns: 1
```
She marries the first and the only guy
```
{1,2,3,4,5}
```
```
2
```
```
Returns: 3
```
The first person who comes after skipped ones is better than skipped ones, hence she marries him
```
{6,5,4,3,2,1}
```
```
2
```
```
Returns: 6
```
No one is better than the first person she skipped, hence she marries the last one
```
{1,5,4,3,2,7,1,2,0}
```
```
3
```
```
Returns: 6
```
The best person skipped has gifts for 5K, the next person who is better than that is the suitor number 6 with 7K worth of gifts
```
{1,5,4,3,2,7,1,2,0}
```
```
5
```
```
Returns: 6
```

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.