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:
Post a Comment