The grand formula

Level starting point = B, Desired level = Y, Number of halls needed = H

(Bx(Y-B)) + (((Y-B)/2)x(Y-B+1))= H

In order to make it easier to remember I will attempt to explain what is logically happening.

If you have a lvl 3 building and you want to take it to lvl 9, then lets start with what we do know.

1st We do know that a lvl 3 building takes 3 halls... so to upgrade 6 more times it will obviously take at least 3 halls per upgrade. Which would be for this example, 3 x 6... or 18.

2nd We know that for every upgrade it costs 1 more then the last. So it is the (B)ase which is 3 in this example, plus 1+2+3+4+5+6

Next let us try and simplify the steps of what we know.

Bx(Y-B) where Y is the desired level number is simple enough. 3 x 6 in this example

the 1+...etc is a little more time consuming. So lets focus on that.

In order to simplify we could easily find the average of the total sum in the series set. A quick way to find the average is to find the Mid point and multiply the Mid point by 2 and add 1.

So for this example there are 6 upgrades desired. Midpoint is 3, midpoint xs 2 + 1 is 7

3x7=21

Adding the Base number of halls (18 in this example) we get 21+18= 39 halls needed.

So in may be easier to remember two equations.

BxN Where B is the base or starting level, N is the number of upgrades needed. If you want an equation for that, Y being the desired level B being the base then N= Y-B

so BxN+ AVG = H

AVG equation can be two fold to make it easy to do in your head. But the AVG is simply

N/2 or M midpoint. Mx(2M+1)

I mentioned that the AVG equation could be twofold because in the case where N is an odd number, M is a fraction.

So if N=11 then the midpoint is 5.5. So you could still use (5.5 x ((2(5.5))+1) or

5.5 x 12 or you could follow this trick which is rounding up the M and multiplying by N

So in this example where N= 11. M is 5.5 but we round to 6. And then we multiply that by N (11 in this case) Simply 6x11.

Mostly this is an explanation to keep it easy to remember. What I keep in my head is

Where N is even

(BxN) + (Mx(2M+1)) = H

Where N is odd

(BxN) + (M rounded up x N) = H

Hope that is clear and easy to remember, it comes in handy.

1 more attempt at simplifying and making shorthand.

There are 2 plug in numbers Starting level and desired level. You only need to calculate 1 more number. Lets call it N or the (N)umber of upgrades.

Which is simply Y-B=N

Then you are ready to plugin to this equation.

BxN + ((N/2) x N+1) = Halls

N/2 you could easily just call M or (M)idpoint to make the equation N/2=M

BxN + (Mx(N+1))

and Where M is a fraction you could just follow this equation.

BxN + ((M+0.5)xN)

I find adding up the series using the standard forumula easier to remember:

Level * (Level + 1)/2 = Halls needed for that level

And just subtract where you already are.

(Goal * (Goal+1)/2) - (Base * (Base+1)/2) = Halls needed to go from Base to Goal

Lemmings in Spaaaacccce!

Or if you have perl with the GLC library, just run

./examples/cost_halls_upgrade.pl X Y

where X = current level + 1
and Y = target level

---

Contest Code:  ZZSP4A1