1129 - Tinta

Alex are o pasiune pentru trasul la țintă. Jucându-se cu numere, visează la o nouă tablă pentru pasiunea sa. Tabla visată este de formă pătrată cu n linii și n coloane, iar numerele, de la 1 la n * n, le poziționează în țintă, ca în imaginea alăturată.

Alex, fiind un foarte bun țintaș, nu nimerește niciodată pe pătrățelele de pe contur. Când țintește o pătrățică din interior, el obține drept punctaj suma valorilor din cele opt pătrățele vecine.

Cerinţă

Cunoscând n numărul de linii și de coloane ale țintei:

a. Ajutați-l pe Alex să construiască ținta visată.

b. Câte punctaje distincte poate să obțină Alex dacă are o singură săgeată?

c. Afișați punctajele distincte găsite.

Date de intrare

Fișierul de intrare tinta.in conține pe prima linie numărul natural n, indicând numărul de linii și de coloane ale țintei.

Date de ieșire

Fișierul de ieșire tinta.out va conține pe primele n linii câte n numere naturale, separate prin câte un spațiu, reprezentând numerele de pe cele n linii ale țintei. Pe linia n+1 se va afișa un singur număr p reprezentând numărul de punctaje distincte. Pe linia n+2 se vor afișa p numere naturale separate prin câte un spațiu și ordonate strict crescător, reprezentând punctajele distincte.

Restricții și precizări

• 3 ≤ n ≤ 1000
• Pentru prima cerinţă afişată corect se va acorda 40% din punctaj; pentru a doua cerință se va acorda 20% din punctaj; pentru cea de-a treia cerință se va acorda 40% din punctaj.

Exemplul 1

tinta.in

3

tinta.out

1  2  6  
3  5  7  
4  8  9
1
40

Explicație

Alex poate ținti doar în pătrățelul interior (cel pe care avem 5), deci obține un singur punctaj, iar suma este 40.

Exemplul 2

tinta.in

4

tinta.out

1 2 6 7
3 5 8 13
4 9 12 14
10 11 15 16
3
45 68 91

Explicație

Alex poate ținti doar pătrăţelele 5, 8, 9 sau 12.

def create_spiral_matrix(n):
    matrix = [[0] * n for _ in range(n)]
    num = 1
    left, right, top, bottom = 0, n - 1, 0, n - 1

    while left <= right and top <= bottom:
        for i in range(left, right + 1):
            matrix[top][i] = num
            num += 1
        top += 1
        for i in range(top, bottom + 1):
            matrix[i][right] = num
            num += 1
        right -= 1
        for i in range(right, left - 1, -1):
            matrix[bottom][i] = num
            num += 1
        bottom -= 1
        for i in range(bottom, top - 1, -1):
            matrix[i][left] = num
            num += 1
        left += 1

    return matrix

def calculate_scores(matrix, n):
    scores = set()
    for i in range(1, n - 1):
        for j in range(1, n - 1):
            score = (matrix[i - 1][j - 1] + matrix[i - 1][j] + matrix[i - 1][j + 1] +
                     matrix[i][j - 1] + matrix[i][j + 1] +
                     matrix[i + 1][j - 1] + matrix[i + 1][j] + matrix[i + 1][j + 1])
            scores.add(score)
    return scores

def main():
    n = int(input("Introduceți valoarea lui n: "))
    spiral_matrix = create_spiral_matrix(n)
    
    print("Matricea spirală:")
    for row in spiral_matrix:
        print(' '.join(map(str, row)))

    if n < 3:
        print("Nu există pătrățele din interior pentru n < 3.")
        return
    
    scores = calculate_scores(spiral_matrix, n)
    print(f"Numărul de punctaje distincte: {len(scores)}")
    print("Punctajele distincte sunt:")
    for score in sorted(scores):
        print(score)

main()