지난 수요일 8시에 열린 매치..~
방배정 운도 없어서.. 5번방 -_- 타겟 두명이 있더라..~
그래도 250 이 좀 어려웠는지 낮은 점수를 맞고도 rating 이 상승했다..~
Level1 - CarrotJumping
Problem Statement
Rabbits often feel hungry, so when they go out to eat carrots, they jump as quickly as possible. Initially, rabbit Hanako stands at position init. From position x, she can jump to either position 4*x+3 or 8*x+7 in a single jump. She can jump at most 100,000 times because she gets tired by jumping. Carrots are planted at position x if and only if x is divisible by 1,000,000,007 (i.e. carrots are planted at position 0, position 1,000,000,007, position 2,000,000,014, and so on). Return the minimal number of jumps required to reach a carrot. If it's impossible to reach a carrot using at most 100,000 jumps, return -1.
Definition
Class:
CarrotJumping
Method:
theJump
Parameters:
int
Returns:
int
Method signature:
int theJump(int init)
(be sure your method is public)
Constraints
-
init will be between 1 and 1,000,000,006, inclusive.
Examples
0)
125000000
Returns: 1
She can jump from 125000000 to 1000000007.
1)
852808441
Returns: -1
She can't reach any carrot by making at most 100,000 jumps.
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.
현재 위치가 x 라면 4 * x + 3 또는 8 * x + 7 의 위치로 갈 수 있다.. x = 0 (mod 100000007) 의 위치로 가위해한 최소 jump 구하기..
상태공간이 최대 1000000007 개 나올 수 있을거같아서 한참 고민하다가.. 잘 생각해보니 상태가 겹치는게 많아서 그냥 fail 을 각오하고 BFS 로 풀었다.. 근데 그냥 pass 해버렸다.. ㅋㅋ
우리방에서 저렇게 푼 사람은 나밖에 없었다.. -_-;;
다른 풀이법은 잘 모르겠음.. -_-;; 참고
Taro has prepared delicious kiwi fruit juice. He poured it into N bottles numbered from 0 to N-1. Each bottle has a capacity of C liters, and he poured bottles[i] liters of kiwi juice into the i-th bottle initially. Taro will sell these bottles after performing an arbitrary number of operations of the following type (possibly zero). In each operation, he chooses two distinct bottles A and B, and pours kiwi juice from bottle A to bottle B until either bottle A becomes empty or bottle B becomes full, whichever happens earlier. If a bottle contains x liters of kiwi juice at the end (where x is an integer between 0 and C, inclusive), then Taro can sell the bottle for prices[x] dollars. Return the maximum amount of money he can earn.
Definition
Class:
KiwiJuice
Method:
theProfit
Parameters:
int, vector <int>, vector <int>
Returns:
int
Method signature:
int theProfit(int C, vector <int> bottles, vector <int> prices)
(be sure your method is public)
Constraints
-
C will be between 1 and 49, inclusive.
-
bottles will contain between 1 and 15 elements, inclusive.
-
Each element of bottles will be between 0 and C, inclusive.
-
prices will contain exactly C + 1 elements.
-
Each element of prices will be between 0 and 1,000,000, inclusive.
Examples
0)
10
{5, 8}
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10}
Returns: 10
If Taro pours kiwi juice from bottle 0 to bottle 1, then bottle 0 will contain 3 liters of kiwi juice and bottle 1 will contain 10 liters of kiwi juice. He can sell bottle 1 for 10 dollars.
1)
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 updated..
Level3 - RandomApple
Problem Statement
Taro likes apples very much. He has N boxes numbered from 0 to N-1. There are K different types of apples numbered from 0 to K-1. You are given three vector <string>s, hundred, ten and one. Concatenate j-th characters in hundred[i], ten[i] and one[i] in this order to get a string that represents the number of j-th type apples in Box i (it may have leading zero(s)). This number will be between 0 and 199, inclusive. He decided to choose one apple from his boxes, and he does so in the following way:
First Step: He chooses a non-empty subset of his N boxes randomly and transfers all apples from those boxes to another box (this is a box other than the original N boxes and it is initially empty). Each non-empty subset of boxes has the same probability of being chosen.
Second Step: He chooses one apple from the new box randomly. Each apple in the box has the same probability of being chosen.
Return a vector <double> that contains exactly K elements and whose i-th element is the probability that Taro chooses an i-th type apple.
Definition
Notes
-
Your return value must have an absolute or relative error less than 1e-9.
Constraints
-
N will be between 1 and 50, where N is the number of elements in hundred.
-
K will be between 1 and 50, where K is the number of characters in hundred[0].
-
ten and one will contain exactly N elements.
-
Each element in hundred, ten and one will contain exactly K characters.
-
Each character in hundred will be '0' or '1'.
-
Each character in ten and one will be a digit ('0'-'9').
-
Each box will contain at least one apple.
Examples
0)
{"00"}
{"00"}
{"58"}
Returns: {0.38461538461538464, 0.6153846153846154 }
There is only one box which contains 5 type-0 apples and 8 type-1 apples. The probability of choosing a type-0 apple is 5 / 13.
1)
{"00", "00"}
{"00", "00"}
{"21", "11"}
Returns: {0.5888888888888889, 0.4111111111111111 }
If he chooses only box 0 in the first step, the probability of choosing a type-0 apple is 2 / 3. If he chooses only box 1 in the first step, the probability of choosing a type-0 apple is 1 / 2. If he chooses both boxes in the first step, the probability of choosing a type-0 apple is 3 / 5. So the probability of choosing a type-0 apple is (2 / 3 + 1 / 2 + 3 / 5) / 3 = 53 / 90.
2)
{"10"}
{"00"}
{"00"}
Returns: {1.0, 0.0 }
One box with 100 type-0 apples and no type-1 apples.
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.
