Fase final
Exercici 5
Sumes de veïns
El següent exercici fa referència a la seqüència de punts de coordenades enteres anomenada espiral quadrada que es descriu a continuació.
Si partim del punt (0,0) del pla, i seguim la següent seqüència de punts: (0,0), (1,0), (1,1), (0,1), (-1,1), (0,-1), etc. , recorrem tots els punts de coordenades enteres. Aquesta és una forma de numerar tots els punts de coordenades enteres. Associarem a cadascú dels punts un número natural segons la seva posició en aquesta seqüència, començant pel 0, és a dir:
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
(0,0) |
(1,0) |
(1,1) |
(0,1) |
(-1,1) |
(-1,0) |
(-1,-1) |
(0,-1) |
(1,-1) |
(2,-1) |
(2,0) |
(2,1) |
... |
La interpretació gràfica d’aquesta seqüència és molt intuïtiva i la representem a continuació:
Imaginem aquesta seqüència completa. Ara associarem a cada punt de coordenades enteres la suma de les posicions dels seus 8 punts veïns més propers. Veiem com:
Construïu un programa que, donat un nombre natural, ens torni la posició del primer punt de la seqüència original que tingui aquest número associat.
El fitxer d’entrada, anomenat suma.in, serà un fitxer de text amb un únic nombre natural més petit o igual que 100.000 (per tant, serà necessari una variable entera de 4 bytes per tal d’emmagatzemar el seu valor).
El fitxer de sortida, anomenat suma.out, serà un fitxer de text amb un únic nombre natural corresponent a la posició en la seqüència de l’espiral quadrada del punt que té una suma de posicions dels seus 8 veïns més pròxims igual al número llegit al fitxer d’entrada.
El programa ha de poder determinar si el número no es troba relacionat en cap punt. En aquest cas ha de tornar un 0.
Exemple:
| fitxer d’entrada | fitxer de sortida |
| 208 | 23 |
Tornar