## Wednesday, May 8, 2013

### Google Code Jam 2013 - Round 1B - Osmos

Today, I would like to share my solution to the Google Code Jam 2013's Round 1B's Osmos problem. These are the statistics for that problem
```Small Input : 4668/7250 users correct (64%)
Large Input : 3537/4578 users correct (77%)
```
I believe it was tricky enough for an easy problem. Many people have got atleast one wrong try. Here is how I solved it (I couldn't solve it during the contest).

```# include <iostream>
# include <cstdio>
# include <algorithm>

using namespace std;
int Sizes[101];
int Total, A, N, Temp, Counter;
int getDiff (int A, int B, int & C)
{
while (A <= B)
{
C++;
A += (A-1);
}
return A;
}
int Solve (int idx, int CurrentScore, int Changes)
{
if (idx == N) return Changes;
if (CurrentScore == 1)
return Solve (idx + 1, CurrentScore, Changes + 1);
else if (Sizes[idx] < CurrentScore)
return Solve (idx + 1, CurrentScore + Sizes[idx], Changes);
else
{
int tChanges = 0;
int Diff = getDiff (CurrentScore, Sizes[idx], tChanges) + Sizes[idx];
int Min1 = Solve (idx + 1, Diff, Changes + tChanges);
if (Sizes[idx] > CurrentScore)
return min (Solve (idx + 1, CurrentScore, Changes+1), Min1);
else return Min1;
}
}
int main()
{
//freopen ("Input.txt", "r", stdin);
//freopen ("Scratch.txt", "w", stdout);
scanf ("%d", &Total);
for (int i = 1; i <= Total; i++)
{
scanf ("%d%d", &A, &N);
Temp = A;
Counter = 0;
for (int j = 0; j < N; j++) scanf ("%d", &Sizes[j]);
sort (Sizes, Sizes + N);
printf ("Case #%d: %d\n", i, Solve (0, A, 0));
}
}
```
Here is the ideone URL http://ideone.com/g5qxYd where I tested the program with Google's inputs.