Connection Status:
Competition Arena > TypoCoderDiv1

TypoCoderDiv1

SRM 602 · 2013-11-22 · by snuke

SRM 602 · 2013-11-22 · by snuke · Dynamic Programming
Class Name: TypoCoderDiv1
Return Type: int
Method Name: getmax
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

TypoCoder is a programming contest like TopCoder. TypoCoder also has a rating system. There are two types of coders in TypoCoder: brown coders and ciel coders. A brown coder is a coder whose rating is greater than or equal to 2200. A ciel coder is a coder whose rating is less than 2200.

Cat Lower competes in TypoCoder. He is currently a ciel coder. His rating at the end of the current year is X.

Next year there will be some contests. In each of those contests, Cat Lower can either try his best or lose on purpose. For each i, the i-th contest (0-based index) has weight D[i]. If Cat Lower tries his best in the i-th contest, his rating will increase by D[i]. If he decides to lose on purpose instead, his rating will decrease by D[i], but not below zero. Formally, his rating will decrease by min(D[i],his rating before the contest).

Cat Lower loves being a ciel coder. Therefore, he must never be a brown coder twice in a row. That is, whenever Cat Lower becomes a brown coder, he must be ciel again after the next contest (if there are any contests left).

TypoCoder awards "Chameleon coder of the year" to the coder whose color changed the most times during the year.

You are given the int[] D and the int X. Return the maximal number of color changes Cat Lower can have next year.

Constraints

  • D will contain between 1 and 50 elements, inclusive.
  • Each element of D will be between 0 and 1,000,000,000 (10^9), inclusive.
  • X will be between 0 and 2199, inclusive.
Examples
0)
{100,200,100,1,1}
2000
Returns: 3

When he increase at the second, the third and the last competition and decrease at the first and the fourth competition, he can change the color 3 times and this is the maximal.

1)
{0,0,0,0,0}
2199
Returns: 0

He cannot be a brown coder in this case.

2)
{90000,80000,70000,60000,50000,40000,30000,20000,10000}
0
Returns: 1

Note that Cat Lower always has at least one valid strategy: if he decides to lose in all contests, he will remain ciel forever. In this test case, the optimal strategy for him is to lose in the first eight contests and then to win in the last one. Note that before the last contest his rating will be 0.

3)
{1000000000,1000000000,10000,100000,2202,1}
1000
Returns: 4
4)
{2048,1024,5012,256,128,64,32,16,8,4,2,1,0}
2199
Returns: 0

Submissions are judged against all 93 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TypoCoderDiv1 with a public method int getmax(vector<int> D, int X) · 93 test cases · 2 s / 256 MB per case

Submitting as anonymous