http://mirror.codeforces.com/problemset/problem/282/B

I thought of a slight modification to the problem to be "How many solutions are there", where a solution is defined as a string like "AGA".

-------------------my (possibly incorrect) approach

Due to the nice property of this problem, I think this is the sum from i= lo to hi of (n choose i) where lo = Math.ceil((aSum-500.0)/1000.0), and hi = Math.floor((aSum+500.0)/1000.0)

I found it really interesting that the permutation of A's and G's don't matter as long as number of G is in between lo and hi. Or maybe it's just because I'm slow and easily amused lol. Proof:

|sum a — sum g| <= 500

but sum g = sum a in B of(1000-ai)

|A — |B| 1000|<=500 -> then get lower and upper bound for B

where B is the set that you choose 'G' to have, and A is the sum of all values of ai

lol messy notations, but yeah

Not really the point of this problem, but is there a good way to calculate sum of combinations in sequence? Like sum from i=0 to j of (N choose i)