His life-long addiction was solving and making puzzles, locks, and cyphers. Recently, an old farmer in South America, who was a host to the young physicist in 1949, found some papers and notes that is believed to have belonged to Feynman. Among notes about mesons and electromagnetism, there was a napkin where he wrote a simple puzzle: "how many different squares are there in a grid of N ×N squares?".
In the same napkin there was a drawing which is reproduced below, showing that, for N=2, the answer is 5.
Input
The input contains several test cases. Each test case is composed of a single line, containing only one integer N, representing the number of squares in each side of the grid (1 ≤ N ≤ 100).
The end of input is indicated by a line containing only one zero.
Output
For each test case in the input, your program must print a single line, containing the number of different squares for the corresponding input.
Example
Input:
2
1
8
0
Output:
5
1
204
https://www.spoj.pl/problems/SAMER08F/
public class Feynman { public static void main( String args[] ) throws Exception { int num = sig(); int rpta; /* * Para cada caso usamos la formula: * # Cuadrados = n * ( n + 1 ) * ( 2 * n + 1 ) / 3 */ while( num != 0 ) { /* * Si n es par, lo dividimos previamente entre 2. * Si n no es par entonces ( n + 1 ) es par, por ende lo dividimos * entre 2. * La division entre 2 permite que uno de los factores en la formula * sea más pequeño, lo que origina que la multiplicacion sea más rapida. * * Notar que: num & 1 es equivalente a n / 2 * Se usa el operador de bits '&', para que la operacion sea más * eficiente. */ if( ( num & 1 ) == 0 ) rpta = ( num >> 1 )*( num + 1 )*( ( num << 1 ) + 1 )/3; else rpta = num * ( ( num + 1 ) >> 1 ) * ( ( num << 1 ) + 1 )/3; System.out.println( rpta ); num = sig(); } } public static int sig() throws Exception { int car = System.in.read(); int val = 0; while( car != 10 ) { val = val * 10 + ( car - 48 ); car = System.in.read(); } return val; } }
No hay comentarios:
Publicar un comentario