Jolly Jumpers..~

Problem Statement
     
Elly is not a big fan of mathematical constants. Most of them are infinite, and therefore hard to memorize. Fractions, on the other hand, are often easier to remember and can provide good approximations. For example, 22/7 = 3.1428... is one way to approximate Pi. Unfortunately, it's only accurate to 2 places after the decimal point, so it doesn't help at all. A slightly better example is 355/113 = 3.14159292... which is correct up to 6 digits after the decimal point.  Elly understands that working with infinite decimal fractions is going to be very difficult, so she first wants to find a good way to approximate floating point numbers with decimal representations that are finite. Your task is to help her in this mission. You will be given a string number containing the decimal representation of a non-negative fraction strictly less than 1. There will be exactly 6 digits after the decimal point in number (trailing zeros are possible and significant). More precisely, number will be formatted "0.dddddd" (quotes for clarity) where each d is a decimal digit ('0'-'9').  Given a fraction F = A/B, where 0 <= A < B, its quality of approximation with respect to number is calculated as follows:
Let S be the decimal fraction (infinite or finite) representation of F.
If S is infinite or the number of digits after the decimal point in S is greater than 6, only consider the first 6 decimals after the decimal point in S. Truncate the rest of the digits without performing any kind of rounding.
If the number of digits after the decimal point in S is less than 6, append trailing zeroes to the right side until there are exactly 6 digits after the decimal point.
The quality of approximation is the number of digits in the longest common prefix of S and number. The longest common prefix of two numbers is the longest string which is a prefix of the decimal representations of both numbers with no extra leading zeroes. For example, "3.14" is the longest common prefix of 3.1428 and 3.1415.
Elly doesn't like long approximations either, so you are only allowed to use fractions where the denominator is less than or equal to maxDen. Find an approximation F = A/B of number such that 1 <= B <= maxDen, 0 <= A < B, and the quality of approximation is maximized. Return a string formatted "A/B has X exact digits" (quotes for clarity) where A/B is the approximation you have found and X is its quality. If there are several such approximations, choose the one with the smallest denominator among all of them. If there is still a tie, choose the one among those with the smallest numerator.
Definition
    
Class:
BestApproximationDiv1
Method:
findFraction
Parameters:
int, string
Returns:
string
Method signature:
string findFraction(int maxDen, string number)
(be sure your method is public)
    
 
Constraints
-
maxDen will be between 1 and 1000, inclusive.
-
number will contain exactly 8 characters.
-
number will consist of a digit '0', followed by a period ('.'), followed by exactly six digits ('0'-'9').
Examples
0)
 
    
42
"0.141592"
Returns: "1/7 has 3 exact digits"
3 plus the current approximation yields an approximation of Pi.
1)
 
    
3
"0.133700"
Returns: "0/1 has 1 exact digits"
Not a lot of options here.
2)
 
    
1000
"0.123456"
Returns: "10/81 has 7 exact digits"
 
3)
 
    
1000
"0.420000"
Returns: "21/50 has 7 exact digits"
This one can be represented in more than one way. Be sure to choose the one with the lowest denominator.
4)
 
    
100
"0.909999"
Returns: "10/11 has 4 exact digits"
Even though 91/100 is a much closer approximation, 10/11 matches up to 3 digits, and 91/100 only to one.
5)
 
    
115
"0.141592"
Returns: "16/113 has 7 exact digits"
A better approximation for the decimal part of Pi.
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
     
The Government in Bulgaria is elected every four years. When an election is held, most people don't vote. They then complain about the new government for the entire time they're in charge, but when the next elections are held four years later, they again don't vote.  Elleonora plans to use this low voter turnout to her advantage. She has found the key to the prime minister's chair: bribes. To ensure that she will win the election, she has decided to bribe all people, who show up on the day of elections, into voting for her. Due to the so called "shurobadjanashtina" (a Bulgarian term meaning that each person is related in some way to all other people), she doesn't even need to pay every voter. For example, if a young couple shows up to vote, bribing just one of them might be sufficient since the other will voluntarily vote for the same candidate.  All voters are lined up in front of the voting place. They are numbered 0 to N-1 from left to right. Each voter has two integer attributes - influence and resistance. They are given in vector <int>s influence and resistance, the i-th elements of which are the influence and resistance, respectively, of the i-th voter. Influence is a measure of how much a person can affect the decisions of the people surrounding him. Resistance is a measure of a person's will to vote for different candidate. If a person's resistance ever falls to zero or less, he will vote for Elleonora. If Elly bribes the i-th person in line, that person's resistance will be reduced by influence[i]. Since that person affects the people around him, the resistances of the person directly to his left and the person directly to his right (the (i-1)-th and (i+1)-th person, respectively) will each be reduced by influence[i]/2. All division in this problem is integer division, meaning that any fractional parts are discarded. The resistances of the (i-2)-th and (i+2)-th people will be reduced by influence[i]/4, and so on. More formally, when the i-th person is bribed, the resistance of the j-th person is reduced by influence[i]/2^(abs(i-j)), where abs(i-j) is the absolute value of i-j. If, after a number of bribes, everybody's resistance is less than or equal to zero, she has won all the votes, and therefore the election.  Return the minimum number of people she must bribe to win the election. She can't bribe the same person more than once. To win the election, every single person must vote for her. If this is impossible, return -1 instead.
Definition
    
Class:
Bribes
Method:
minBribes
Parameters:
vector <int>, vector <int>
Returns:
int
Method signature:
int minBribes(vector <int> influence, vector <int> resistance)
(be sure your method is public)
    
 
Constraints
-
influence and resistance will each contain between 1 and 50 elements, inclusive.
-
influence and resistance will contain the same number of elements.
-
Each element of influence and resistance will be between 1 and 500, inclusive.
Examples
0)
 
    
{ 10, 3, 5, 3, 1 }
{ 11, 2, 7, 3, 1 }
Returns: 2
The influence can be less than, equal or greater than the resistance of a given person. Here the optimal strategy is to bribe the people with indices 0 and 2, decreasing the resistances of the people by {10, 5, 2, 1, 0} and {1, 2, 5, 2, 1}, respectively, making the final resistances {0, -5, 0, 0, 0}.
1)
 
    
{ 15, 15, 15 }
{ 13, 42, 13 }
Returns: -1
This one is impossible. Even when bribing all of them, the final resistance is {-12, 13, -12}. The cake is a lie.
2)
 
    
{ 10, 16, 4, 7, 1, 1, 13 }
{ 10, 16, 4, 7, 1, 1, 13 }
Returns: 4
After bribing the people with influence 16, 13, and 10, only one person remains with barely positive resistance. She still has to bribe that one person to have full support and win the election.
3)
 
    
{ 479, 340, 398, 40, 477, 181, 422, 377, 60, 486, 15, 500, 307, 1, 2, 65, 411, 374, 446, 401 }
{ 402, 87, 20, 76, 468, 493, 252, 98, 216, 58, 89, 500, 89, 26, 8, 125, 269, 116, 426, 81 }
Returns: 7
 
4)
 
    
{ 21, 196, 401, 157, 9, 497, 371, 84, 395, 495, 401, 190, 465, 359, 47, 441, 245, 487, 118, 405 }
{ 127, 313, 376, 94, 66, 37, 237, 142, 315, 495, 257, 153, 437, 339, 483, 356, 16, 132, 231, 342 }
Returns: 8
 
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
     
After a long bout of sleeplessness, Elleonara has finally fallen asleep. To accomplish this, she had to count sheep until the number overflowed and became negative. She is now in the middle of a strange dream. She is on the bank of a river with a flock of numSheep sheep, and across the river are endless grass fields. She wants to take all her sheep across the river to the fields using a single boat. Elly wonders what the minimum weight capacity of the boat must be for her to accomplish this by making at most maxRuns runs. Crossing the river to the fields and then coming back again counts as a single run.  Her sheep are of varying weights. She decides to use the following greedy strategy to determine the order in which to take them. In each run, she first chooses the heaviest remaining sheep that can fit in the boat. Then, after putting that sheep in the boat, she again chooses the heaviest remaining sheep that can fit in the boat along with the previously chosen sheep. She repeats this process until no other sheep can fit in the boat. She then takes the boat to the other side, drops off the sheep, and comes back. For example, if the boat's capacity is 42 and the sheep have weights of 30, 15, 13, 8, 5, 3, 2 and 2, she would pick the sheep with weights 30, 8 and 3. If after maxRuns runs, there are still sheep remaining on the bank, this means the capacity of the boat is not high enough.  You are given vector <string>s part1, part2, part3 and part4. Concatenate the elements in each vector <string> in the same order as they are given without any delimiters between its elements to get four long strings. Then, concatenate those strings to get a space separated list of integers. Each integer is the weight of one sheep in her flock. Return the minimum weight capacity of a boat that will accomplish Elly's goal.
Definition
    
Class:
Sheep
Method:
minCapacity
Parameters:
int, int, vector <string>, vector <string>, vector <string>, vector <string>
Returns:
int
Method signature:
int minCapacity(int numSheep, int maxRuns, vector <string> part1, vector <string> part2, vector <string> part3, vector <string> part4)
(be sure your method is public)
    
 
Notes
-
Elly's weight is a constant and can be ignored.
-
Although her strategy of matching sheep into the boat is not always optimal, she will use it anyway.
-
The capacity of the boat should be at least as much as the largest sheep (otherwise it couldn't be moved on any run) and no more than the sum of the weights of all sheep (which guarantees that they can be moved on the first run).
Constraints
-
numSheep will be between 1 and 2,000, inclusive.
-
maxRuns will be between 1 and 2,000, inclusive.
-
part1, part2, part3 and part4 will each contain between 0 and 50 elements, inclusive.
-
Each element of part1, part2, part3 and part4 will contain between 1 and 50 characters, inclusive.
-
After concatenating the elements of part1-part4, and then concatening those strings, the final string will be a single space separated list of integers.
-
There will be exactly numSheep integers in the list.
-
Each integer in the list will be between 1 and 2,000, inclusive.
-
Integers in the list will have no leading zeros.
Examples
0)
 
    
6
2
{ "26 7 10 30 5 4" }
{ }
{ }
{ }
Returns: 42
The capacity of the boat should be at least 30, but this is not enough for all sheep to be taken with only 2 runs. Indeed, in this case Elleonora would need three runs - first, she would transfer the sheep with weight 30, then the sheep with weights 26 and 4 and finally the sheep with weights 10, 7 and 5. The smallest capacity that satisfies Elleonora is 42 - the first run will be (30, 10) and the second will be (26, 7, 5, 4). Note that there exists a strategy where the boat of size 41 is enough - the runs are (30, 7, 4) and (26, 10, 5), but Elly will not use it.
1)
 
    
6
2
{ "4 8 15 16 23 42" }
{ }
{ }
{ }
Returns: 54
With capacity 54 the runs are (42, 8, 4) and (23, 16, 15). Since in both of them the boat is completely filled, this guarantees that the answer is optimal.
2)
 
    
15
4
{ "666 42 7 13 400 511 600 200 202 111 313 94 280", " 72 42" }
{ }
{ }
{ }
Returns: 896
We can have equal numbers in the input.
3)
 
    
7
6
{ "200 2", "01 202 203" }
{ " 204 " }
{ }
{ "205", " ", "206" }
Returns: 401
Don't forget to concatenate the elements correctly.
4)
 
    
200
20
{ "42 468 335 501 1170 1725 1479 1359 963 465 1706",
  " 146 1282 828 1962 492 996 1943 828 1437 392 605",
  " 1903 154 293 383 1422 717 1719 1896 1448 1727",
  " 772 1539 1870 1913 1668 300 1036 1895 704 1812",
  " 1323 334 1674 665 1142 1712 254 869 1548 1645",
  " 663 758 38 860 724 1742 1530 779 317 1036 191",
  " 1843 289 107 1041 943 1265 649 1447 1806 1891",
  " 730 371 1351 1007 1102 394 1549 1630 624 85 1955",
  " 757 1841 967 1377 1932 309 945 440 627 1324 1538",
  " 1539 119 83 930 542 834 1116 640 1659 705 1931",
  " 1978 307 1674 387 1022 746 925 1073 271 1830 778",
  " 1574 1098 513 1987 1291 1162 637 356 768 1656",
  " 1575 32 53 1351 1151 942 1725 1967 1431 1108 192",
  " 8 1338 1458 288 1754 384 946 910 210 1759 222",
  " 589 423 947 1507 1031 414 1169 901 592 763 1656",
  " 1411 360 1625 538 1549 484 1596 42 1603 351 292",
  " 837 1375 1021 597 22 1349 1200 1669 485 282 735",
  " 54 2000 419 1939 901 1789 128 468 1729 894 649",
  " 484 1808 422 311 618 814 1515" }
{ }
{ }
{ }
Returns: 9986
 
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.