3091 - Pavele

Cerinţa

Avem o suprafață dreptunghiulară pătratică de dimensiune n x n (n – impar). Colțul de dimensiune 1 x 1 din stânga-sus lipsește. Se dorește pavarea a cât mai mult din suprafața sa cu dale de dimensiune 1 x 2 (sau 2 x 1). Trebuie folosite cât mai multe dale și în plus, numărul de dale orizontale folosite trebuie să fie egal cu numărul de dale verticale folosite pentru pavare.

Date de intrare

Fișierul de intrare pavele.in conține pe prima linie numărul n.

Date de ieșire

Fișierul de ieșire pavele.out conține pe prima linie un număr r, ce reprezintă numărul de dale verticale (orizontale) folosite. Următoarele n linii conțin câte n numere întregi, separate printr-un spațiu, reprezentând codificarea modului de pavare. Numerele trebuie să fie cuprinse între –r și r. Valoarea 0 semnifică faptul că acea poziție a zonei dreptunghiulare nu se pavează (sau lipsește, întrucât se afișează 0 și în contul colțului stânga sus). Pentru codificarea dalelor orizontale se folosesc câte două numere egale, cuprinse între 1 și r, așezate unul lângă altul pe aceeași linie iar pentru codificarea dalelor verticale se folosesc câte două numere egale cuprinse, cuprinse între –r și -1, așezate unul sub altul.

Restricţii şi precizări

• 5 ≤ n ≤ 299
• n – impar;
• dalele orizontale se codifică folosind valori pozitive iar cele verticale folosind valori negative;
• evident, dalele nu se pot suprapune și trebuie să fie complet incluse în zona dreptunghiulară;

Exemplul 1

pavele.in

 5

pavele.out

 6
  0   1   1 -1 -2
  3  -4  -5 -1 -2
 -3  -4  -5  4  4
  2   2  -6  5  5
  3   3  -6  6  6
 Aici datele sunt indentate doar pentru o mai ușoară înțelegere a exemplului.

Rezolvare

def write_output(file_name, r, pave_layout):
    with open(file_name, 'w') as file:
        file.write(str(r) + '\n')
        for row in pave_layout:
            file.write(' '.join(map(str, row)) + '\n')

def pave_surface(n):
    pave_layout = [[0] * n for _ in range(n)]
    r = n // 2 + 1
    for i in range(n):
        for j in range(n):
            if (i + j) % 2 == 0:
                pave_layout[i][j] = r
            else:
                pave_layout[i][j] = -r
    return r, pave_layout

def main():
    with open("pavele.in", 'r') as file:
        n = int(file.readline().strip())
    r, pave_layout = pave_surface(n)
    write_output("pavele.out", r, pave_layout)

if __name__ == "__main__":
    main()