UVA Problem 12149 – Feynman Solution

UVA Problem 12149 – Feynman Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

The problem asks given a number n how many squares are there in n by n grid. The relation can be found out by drawing n*n sqares and counting the squares. Since it will be very hard to draw and count more than 4 by 4 grid. We can try 1 by 1, 2 by 2, 3 by 3, 4 by 4 grid and count the number of squares. From there we can try to guess an equation.

For,
1*1 grid =   1 Square = 1
2*2 grid =   5 Square = 1 + 2^2
3*3 grid = 14 Square = 1 + 2^2 + 3^2
4*4 grid = 30 Square = 1 + 2^2 + 3^2 + 4^2

Here the series is,
1^2 + 2^2 + 3^2 + 4^2 + ….. n^2
Which is the sum of first n squares.

Instead of calculating with this formula a simpler formula exists.
1^2 + 2^2 + … + n^2 = n(n + 1)(2n + 1) / 6

The proof for this formula can be found here.

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.


Input:

2
1
8
0

Output:

5
1
204

Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: UVA 12149 Feynman
 * Type:    Mathematics ( 1^2 + 2^2 + .... + n^2 )
 */

#include<stdio.h>

int main(){
    static unsigned n;

    while(scanf("%u",&n) && n)
        printf("%u\n", n * (n + 1) * (2 * n + 1 ) / 6 );

    return 0;
}
Advertisements