- 내가 처음으로 Petr를 이겨본 매치이고..
- 무려 14개월만에 yellow를 탈환했다..
- Div1 / Div2 이렇게 많이 fail 한게 언제인지.. 완전 crazy match 였다..~
우리방 결과.. 와우.. 정말 아름다운 매치였다..~
Petr가 Fail/Fail/Fail 을 기록한건 최대 이변이닷..~
Level1 - BestApproximationDiv1
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
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.
0.xxxxxx 꼴의 number 가 들어올때, 이 값을 A / B 로 최대한 근사화하고싶다..
가장 적절한 A, B 구하기..
모든 가능한 A, B 에 대해서 다 시도하였다..
이 문제는 precision error 로 fail 한 사람이 무수히 많다..
포럼에 있는 글도 읽어보자..(링크)
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)
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.
to be upated..
Level3 - Sheep
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)
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.
numSheep 만큼의 sheep 이 있는데 얘네들을 전부 배에 태워서 반대편 강변에 내려야 한다..
최대 maxRun 만큼만 왔다갔다 하고싶을때 배의 크기가 얼마나 되야할까..?
배에 sheep 을 태울때는 무조건 가능한 무거운애부터 태운다..~
우리방 결과.. 와우.. 정말 아름다운 매치였다..~
Petr가 Fail/Fail/Fail 을 기록한건 최대 이변이닷..~
