오랜만에 회사에서 참가했다..
500 이 나름 쉬운게 나왔는데 점화식까지 찾았는데 코딩이 늦는바람에 결국 서밋 실패했다..
나이를 먹어서 그런지.. 계속 코딩속도가 느려지고있다.. ㅠ_ㅠ;;
250 도 그닥 만족스럽지 못하게 풀었는데.. 좀 틀려주는 사람이 많아서 rating 을 조금 올렸다..~
yellow 턱밑까지 올라오긴 했는데.. 쩝
Level1 - FoxPlayingGame
Problem Statement
Fox Ciel was very bored, so she invented a single player game. The rules of the game are:
You start with 0 points.
You make exactly nA+nB moves.
You have two types of moves available. These are called move A and move B.
Exactly nA times you will make move A. Exactly nB times you will make move B. The moves can be in any order.
The moves affect your score in the following ways:
Each time you make move A, you add scoreA to your score.
Each time you make move B, you multiply your score by scoreB.
You are given int nA, int nB, int paramA and int paramB. Calculate scoreA and scoreB as follows ("/" denotes exact division, without any rounding):
scoreA = paramA/1000.0
scoreB = paramB/1000.0
Return the maximum possible score after nA+nB moves.
Definition
Class:
FoxPlayingGame
Method:
theMax
Parameters:
int, int, int, int
Returns:
double
Method signature:
double theMax(int nA, int nB, int paramA, int paramB)
(be sure your method is public)
Notes
-
The returned value must have an absolute or relative error less than 1e-9.
Constraints
-
nA will be between 0 and 50, inclusive.
-
nB will be between 0 and 50, inclusive.
-
paramA will be between -10000 and 10000, inclusive.
-
paramB will be between -2000 and 2000, inclusive.
Examples
0)
3
3
2000
100
Returns: 6.0
scoreA = 2000/1000 = 2 scoreB = 100/1000 = 0.1 Multiplying the score by scoreB decreases its absolute value, so it's better to do all multiplications before additions. Thus, the optimal order of operations is: 0 * 0.1 * 0.1 * 0.1 + 2 + 2 + 2 = 6
2)
4
3
-2000
2000
Returns: -8.0
Multiplying the score by scoreB increases its absolute value, but given that scoreA is negative, the overall score will be negative as well, so it's better to do multiplications before additions again to keep the absolute value small.
3)
5
5
2000
-2000
Returns: 160.0
Multiplication increases the absolute value of the score, but if you do all 5 multiplications after additions, you'll end up with negative score. Thus, the optimal order of operations is: (0 * (-2) + 2 + 2 + 2 + 2 + 2) * (-2) * (-2) * (-2) * (-2) = 160
4)
50
50
10000
2000
Returns: 5.62949953421312E17
5)
41
34
9876
-1234
Returns: 515323.9982341775
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.
scoreA 를 nA 번 add, scoreB 를 nB 번 multiply 해서 얻을 수 있는 최대값 구하기..
이 문제는 DP로 복잡하게 푼 사람이 많던데.. greedy 로 풀 수 있다는 것만 간파하면 매우 간단히 풀 수 있다..
일단 더하기 연산부터 다 하고,
곱하기를 0번 적용, 1번 적용, 2번 적용, ... nB번 적용 .. 한것중에 최대값을 구하면 된다..
왜 그럴까..?
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <queue>
7 using namespace std;
8 //#define min(x, y) ((x) > (y) ? (y) : (x))
9 //#define max(x, y) ((x) > (y) ? (x) : (y))
10 #define INF 9999999999999.0
11 //#define EPS 1e-14
12
13 class FoxPlayingGame {
14 public:
15
16 double theMax(int nA, int nB, int paramA, int paramB)
17 {
18 double sa, sb;
19 double sum, max1;
20 int i, j;
21 sa = (double)paramA / 1000.0;
22 sb = (double)paramB / 1000.0;
23 max1 = -INF;
24 for (i = 0; i <= nB; i++) {
25 sum = 0;
26 for (j = 0; j < i; j++) {
27 sum *= sb;
28 }
29 for (j = 0; j < nA; j++) {
30 sum += sa;
31 }
32 for (j = i; j < nB; j++) {
33 sum *= sb;
34 }
35 printf("i = %d, sum = %lf\n", i, sum);
36 if (sum > max1)
37 max1 = sum;
38 }
39 return max1;
40 }
41
42 };
Level2 - FoxAverageSequence
Problem Statement
Fox Ciel likes sequences of integers. She especially likes sequences which she considers to be beautiful. A sequence (A[0], A[1], ..., A[N-1]), N >= 1, is beautiful if and only if it satisfies the following conditions:
Each element of the sequence is an integer between 0 and 40, inclusive.
Each element of the sequence is less than or equal to the arithmetic mean of the previous elements. That is, for each i, 1 <= i < N, we have A[i] <= (A[0] + A[1] + ... + A[i-1]) / i.
There are no three consecutive elements in the sequence that follow in strictly decreasing order. In other words, there must be no index i, 0 <= i < N-2, such that A[i] > A[i+1] > A[i+2].
You are given a vector <int> seq that describes some sequences. Each element in seq is between -1 and 40, inclusive. You can change each occurrence of -1 in seq into an arbitrary integer between 0 and 40, inclusive. Different occurrences can be changed into different integers.
Return the number of different beautiful sequences that can be obtained in this way, modulo 1,000,000,007.
Definition
Class:
FoxAverageSequence
Method:
theCount
Parameters:
vector <int>
Returns:
int
Method signature:
int theCount(vector <int> seq)
(be sure your method is public)
Notes
-
Two sequences of the same length are different if there is at least one position at which their elements are different.
Constraints
-
seq will contain between 1 and 40 elements, inclusive.
-
Each element of seq seq will be between -1 and 40, inclusive.
Examples
0)
{3, -1}
Returns: 4
{3, 0}, {3, 1}, {3, 2} and {3, 3} are valid sequences.
1)
{5, 3, -1}
Returns: 2
{5, 3, 3} and {5, 3, 4} are valid sequences.
2)
{-1, 0, 40}
Returns: 0
There are no valid sequences.
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.
1) A[i] <= (A[0] + A[1] + ... + A[i-1]) / i
2) there must be no index i, 0 <= i < N-2, such that A[i] > A[i+1] > A[i+2]
요 두 조건을 만족하는 가능한 seq 의 개수 구하기..
Level3 - FoxSearchingRuins
Problem Statement
Fox Ciel has a map of some underground ruins. It describes the position of several jewels and their values. She wants to collect some of the jewels. The map is a rectangle with width W and height H. It contains W*H cells. The cell in the upper left corner has the coordinates (0,0) and the cell in the lower right corner has coordinates (W-1,H-1). There are jewelCount jewels. The i-th jewel is located at coordinates (x[i],y[i]) and has a value of v[i]. 0, 1, 2 or more jewels may be in the same cell.
Ciel starts from any cell in the top row (any cell whose y-coordinate is 0 and x-coordinate is arbitrary). She has a super drill so she can move down any number of times, but she can move to the left or right at most LR times. Moving up is not allowed. She collects all the jewels in a cell by moving to that cell (or starting in that cell). Moving down takes timeY seconds and moving left or right takes timeX seconds. Collecting jewels takes no time.
Calculate and return the minimum time required to collect enough jewels so that the sum of the values of the collected jewels is greater than or equal to goalValue. If she can't collect enough jewels then return -1.
You can calculate x[i], y[i], and v[i] as follows:
x[0] = (seeds[1] * seeds[0] + seeds[2]) mod W
y[0] = (seeds[4] * seeds[3] + seeds[5]) mod H
v[0] = (seeds[7] * seeds[6] + seeds[8]) mod seeds[9]
for i=1 to jewelCount-1:
x[i] = (seeds[1] * x[i-1] + seeds[2]) mod W
y[i] = (seeds[4] * y[i-1] + seeds[5]) mod H
v[i] = (seeds[7] * v[i-1] + seeds[8]) mod seeds[9]
Definition
Class:
FoxSearchingRuins
Method:
theMinTime
Parameters:
int, int, int, int, int, int, int, vector <int>
Returns:
long long
Method signature:
long long theMinTime(int W, int H, int jewelCount, int LR, int goalValue, int timeX, int timeY, vector <int> seeds)
(be sure your method is public)
Constraints
-
W will be between 1 and 1,000, inclusive.
-
H will be between 1 and 1,000,000,000, inclusive.
-
jewelCount will be between 1 and 1,000, inclusive.
-
LR will be between 0 and 1,000, inclusive.
-
timeX and timeY will each be between 1 and 100, inclusive.
-
goalValue will be between 1 and 1,000,000,000, inclusive.
-
seeds will contain exactly 10 elements.
-
for i=0..8, seeds[i] will be between 0 and 1,000,000,000, inclusive.
-
seeds[9] will be between 2 and 1,000,000, inclusive.
Examples
0)
5
8
5
7
10
3
1
{979, 777, 878, 646, 441, 545, 789, 896, 987, 10}
Returns: 5
The map of the ruins is as follows:
3....
...5.
....7
.9...
.....
.....
.....
.1...
Ciel's optimal moves:
Start from (3, 0). (time = 0)
Move to (3, 1) and collect the jewel whose value is 5. (time = 1)
Move to (4, 1). (time = 4)
Move to (4, 2) and collect the jewel whose value is 7. (time = 5)
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.
