Here is the problem statament
http://www.spoj.com/problems/CRDS/
The pyramid of level N is being build in this way
/\ /\ /\ /\ /\ (N /\ s)
then between every pair we put one more card on theit tops and then we put n-1 /\ s and again and again until we reach the final level .
Here is a picture
As we can see easily we need n-1+n-2+n-3....+1 cards for building the "floor" (cards that we put on pairs to form a floor the horizontal cards) and 2*(n+n-1+n-2+....+1 ) cards to build the /\ pairs. The formula for calculating the sum of numbers from 1 to k is ( k*(k+1) )/2 .
Be certain that you do the division first because the numbers are too big you might get a wrong answer.
http://www.spoj.com/problems/CRDS/
The pyramid of level N is being build in this way
/\ /\ /\ /\ /\ (N /\ s)
then between every pair we put one more card on theit tops and then we put n-1 /\ s and again and again until we reach the final level .
Here is a picture
As we can see easily we need n-1+n-2+n-3....+1 cards for building the "floor" (cards that we put on pairs to form a floor the horizontal cards) and 2*(n+n-1+n-2+....+1 ) cards to build the /\ pairs. The formula for calculating the sum of numbers from 1 to k is ( k*(k+1) )/2 .
Be certain that you do the division first because the numbers are too big you might get a wrong answer.
No comments:
Post a Comment