Jolly Jumpers..~

Problem Statement
    
There is a group of N people numbered from 0 to N-1. Each of them is either an honest person or a liar. You wish to know how many liars are in the group. To do this, you have asked the same question to every person in the group: "What is the number of liars in this group?". The people in the group themselves know the exact number of liars, but since you are a foreigner in the group, they have not told it to you exactly. Instead, the i-th person answered you as follows: "There are at least claim[i] liars in the group." It is known that statements by honest persons are always true. However, statements by liars are always false. So, if a liar claims that there are at least X liars in the group, then in fact there are less than X liars.  Now, given a vector <int> claim containing the N answers that you received, you would like to determine the number of liars in the group. Unfortunately, there's another twist that makes this problem more complicated. The people in the group speak a different language than you, so you might have misunderstood some of their answers. The answers in claim are how you understood them, but they might not match what the people actually told you. If you definitely misunderstood at least one of the answers, return -1. Otherwise, assuming that you understood all answers correctly, return the minimum number of liars that could be in the group.
Definition
    
Class:
MinimumLiars
Method:
getMinimum
Parameters:
vector <int>
Returns:
int
Method signature:
int getMinimum(vector <int> claim)
(be sure your method is public)
    
 
Constraints
-
claim will contain between 2 and 50 elements, inclusive.
-
Each element of claim will be between 0 and 100, inclusive.
Examples
0)
 
    
{1,1,1,2}
Returns: 1
It would be impossible for all the members of the group to be honest because in that case, all of their answers would be 0. It is, however, possible that only the last person is a liar and each of the first three persons is honest. Therefore the correct answer is 1.
1)
 
    
{7,8,1}
Returns: 2
The first two people claim that there are at least 7 and 8 liars, respectively, which is impossible as the group only has three people. Thus, they must be lying. The third person claims there is at least one liar, and this is definitely true since we have already identified two liars, so this person is honest.
2)
 
    
{5,5,5,5,5}
Returns: -1
Everybody agrees that there are at least 5 liars in the group. The group contains exactly 5 people, so in fact all of them claim that everybody is a liar. We can't assume that some person is honest because this person definitely wouldn't have claimed him/herself as being a liar. We also can't assume that all of them are liars because in this case it will appear that all their statements are true. Every scenario we can try leads to a contradiction, so you must have misunderstood at least one of the answers.
3)
 
    
{0,0,0,4,3,0}
Returns: 2
 
4)
 
    
{4,7,5}
Returns: 3
Every claim made is impossible. Therefore all three people in the group must be lying.
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)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
Fox Jiro is going to listen to some music. He has N songs, numbered 0 to N-1, inclusive. The lengths of the songs are given in the vector <int> length, where the i-th element is the length in seconds of song i.
 
The music player he uses has a shuffle feature. Using this feature, he can listen to the songs in random order. More precisely, first the player chooses one song among all songs with equal probability and plays it. When the song ends, the player chooses the next song in the same fashion and plays it immediately. Note that the player may choose the same song more than once in a row.
 
You are given an int T. Return a double[] P, where P[i] indicates the probability that the player is playing the i-th song T+0.5 seconds after Jiro starts listening to the music in shuffle mode.
Definition
    
Class:
FoxListeningToMusic
Method:
getProbabilities
Parameters:
vector <int>, int
Returns:
vector <double>
Method signature:
vector <double> getProbabilities(vector <int> length, int T)
(be sure your method is public)
    
 
Notes
-
Each element of the returned array must have an absolute or relative error less than 1e-9.
Constraints
-
length will contain 1 and 50 elements, inclusive.
-
Each element of length will be between 1 and 80,001, inclusive.
-
T will be between 0 and 80,000, inclusive.
Examples
0)
 
    
{1, 2}
1
Returns: {0.25, 0.75 }
There are three possible scenarios that lead up to time 1.5:
song 0 -> song 0 (with probability 1/4)
song 0 -> song 1 (with probability 1/4)
song 1 (with probability 1/2)
1)
 
    
{1, 10, 100, 1000, 10000}
0
Returns: {0.2, 0.2, 0.2, 0.2, 0.2 }
 
2)
 
    
{5, 8, 4, 7}
10
Returns: {0.1875, 0.3125, 0.1875, 0.3125 }
 
3)
 
    
{10, 1}
9
Returns: {0.9990234375, 9.765625E-4 }
 
4)
 
    
{58, 47, 36, 25, 14, 3}
100
Returns:
{0.32895835374381194, 0.26291497538241776, 0.18463894970453887, 0.1312301113062895,
 0.07518634032025856, 0.017071269542683242 }
 
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)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
Taro and Brus are playing a new game called Square Series. The game involves placing a non-empty sequence of black and white squares following a couple of rules: 
The first square has side length 1.
For i > 1, if the color of square i (1-indexed) is different than the color of square i-1, its side length will be equal to the side length of the previous square plus 1. If the colors are the same, then the side length will be equal to the previous side length minus 1. Note that a side length of 0 would make the shape not a square, so it is not legal to repeat the color after a length 1 square.
 Taro wants to prepare new challenges for Brus and would like you to make a program that will generate valid square series such that it matches string pattern and the length of the last square is equal to lastLength. The pattern contains 'W' and 'B' representing white and black squares respectively and exactly one '?' character. To generate a sequence of strings that matches the pattern, replace the '?' character with a (possibly empty) sequence of white and black squares.  Given the pattern and lastLength, if there is no valid sequence of squares that follows the aforementioned rules, matches the pattern and finishes with a square of side length equal to lastLength, then return "..." (quotes for clarity). Otherwise, return the shortest possible sequence that matches the pattern and finishes with a square of the appropriate side length. In case there is more than one sequence with a length equal to the shortest possible, return the lexicographically first of them.
Definition
    
Class:
SquareSeries
Method:
completeIt
Parameters:
string, int
Returns:
string
Method signature:
string completeIt(string pattern, int lastLength)
(be sure your method is public)
    
 
Notes
-
The lexicographically earlier of two strings of the same length is the one that has the earlier character (using ASCII ordering) at the first position at which they differ.
Constraints
-
lastLength will be between 1 and 100, inclusive.
-
pattern will contain between 1 and 50 characters, inclusive.
-
Each character in pattern will be 'W', 'B' or '?'.
-
pattern will contain exactly one '?' character.
Examples
0)
 
    
"W?B"
2
Returns: "WB"
It is possible to replace the '?' character with an empty sequence. The sequence "WB" is the shortest one that matches the pattern and ends with a square of length 2.
1)
 
    
"?"
5
Returns: "BWBWB"
Any sequence can match the "?" pattern. "BWBWB" and "WBWBW" are the shortest sequences possible that end with a square of size 5. "BWBWB" is the lexicographically earlier of the two.
2)
 
    
"BWBBBBW?WB"
10
Returns: "..."
Every sequence that begins with BWBBBB is invalid because it will require an invalid square of size 0 at position 6 (1-based).
3)
 
    
"BWBWBW?WBWBWBW"
15
Returns: "BWBWBWBBWBWBWBWBW"
 
4)
 
    
"WBWBWBWBWBWWBB?W"
1
Returns: "WBWBWBWBWBWWBBBBBBBBBBBWW"
 
5)
 
    
"?WBWBWBBB"
3
Returns: "..."
 
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)2003, TopCoder, Inc. All rights reserved.