AmebaDiv2
SRM 615 · 2013-12-22 · by snuke
SRM 615 · 2013-12-22 · by snuke · Simulation
Problem Statement
Problem Statement
Monte-Carlo is an amoeba. Amoebas can feed on gel: whenever an amoeba encounters a piece of gel that is exactly as big as the amoeba, the amoeba will consume the gel and thus double its size.
Initially, the size of Monte-Carlo was A. During its lifetime, Monte-Carlo encountered several gels and consumed the ones it could.
You are given aint[] X and the int A. The elements of X are the sizes of gels Monte-Carlo encountered, in chronological order. Compute and return the final size of Monte-Carlo.
Initially, the size of Monte-Carlo was A. During its lifetime, Monte-Carlo encountered several gels and consumed the ones it could.
You are given a
Constraints
- X will contain between 1 and 200 integers, inclusive.
- Each element of X will be between 1 and 1,000,000,000, inclusive.
- A will be between 1 and 1,000,000,000, inclusive.
Examples
0)
{2,1,3,1,2}
1
Returns: 4
Gel #0 is bigger than Monte-Carlo, nothing happens. Monte-Carlo consumes gel #1. Its size is now 1+1 = 2. Gel #2 is bigger than Monte-Carlo, nothing happens. Gel #3 is smaller than Monte-Carlo, nothing happens. Monte-Carlo consumes gel #4. Its size is now 2+2 = 4.
1)
{1,4,9,16,25,36,49}
10
Returns: 10
The size of Monte-Carlo doesn't change.
2)
{1,2,4,8,16,32,64,128,256,1024,2048}
1
Returns: 512
3)
{817,832,817,832,126,817,63,63,126,817,832,287,823,817,574}
63
Returns: 252
4)
{1000000000}
1000000000
Returns: 2000000000
Submissions are judged against all 64 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class AmebaDiv2 with a public method int simulate(vector<int> X, int A) · 64 test cases · 2 s / 256 MB per case