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.

No comments: