3244 - tabla: Difference between revisions

From Bitnami MediaWiki
No edit summary
Line 1: Line 1:
== Enunt ==
== Enunt ==


O tablă de șah de dimensiune n x n conține pe toate pătrățelele câte o piesă cu una din culorile: alb, negru, roșu, verde sau albastru. Pe tablă nu există 3 piese consecutive pe aceeași linie sau coloană de aceeași culoare. O mutare presupune interschimbarea a două piese alăturate, fie pe o linie, fie pe o coloană. După mutare se acordă punctaj dacă se obțin următoarele situații și nu numai:
O tablă de șah de dimensiune '''n x n''' conține pe toate pătrățelele câte o piesă cu una din culorile: alb, negru, roșu, verde sau albastru. Pe tablă nu există 3 piese consecutive pe aceeași linie sau coloană de aceeași culoare. O mutare presupune interschimbarea a două piese alăturate, fie pe o linie, fie pe o coloană. După mutare se acordă punctaj dacă se obțin următoarele situații și nu numai:


*3 piese de aceeași culoare consecutive pe o linie sau o coloană = 1 punct;
*'''3''' piese de aceeași culoare consecutive pe o linie sau o coloană '''= 1''' punct;
*3 piese de aceeași culoare consecutive pe o linie și o coloană = 5 puncte;
*'''3''' piese de aceeași culoare consecutive pe o linie și o coloană '''= 5''' puncte;
La orice situație de mai sus, o piesă în plus de aceeași culoare mai contribuie cu încă 1 la punctaj. De exemplu, 4 piese de aceeași culoare consecutive pe o linie sau o coloană = 2 puncte. Punctajele obținute de piesele interschimbate se adună. Punctajul este 0 dacă nu se obțin măcar 3 piese consecutive de aceeași culoare.
La orice situație de mai sus, o piesă în plus de aceeași culoare mai contribuie cu încă 1 la punctaj. De exemplu, 4 piese de aceeași culoare consecutive pe o linie sau o coloană '''= 2''' puncte. Punctajele obținute de piesele interschimbate se adună. Punctajul este 0 dacă nu se obțin măcar 3 piese consecutive de aceeași culoare.


== Cerinta ==
== Cerinta ==
Line 13: Line 13:
== Date de intrare ==
== Date de intrare ==


Fișierul de intrare tabla.txt conține, pe prima linie, numărul natural n, ce reprezintă dimensiunea tablei. Pe fiecare dintre următoarele n linii se află câte n valori separate prin spatii. Valorile posibile pot fi: 1, 2, 3, 4 și 5. Valoarea 1 reprezintă piesa de culoare albă, 2 piesa de culoare neagră etc.
Fișierul de intrare '''tablain.txt''' conține, pe prima linie, numărul natural '''n''', ce reprezintă dimensiunea tablei. Pe fiecare dintre următoarele '''n''' linii se află câte '''n''' valori separate prin spatii. Valorile posibile pot fi: '''1, 2, 3, 4 și 5'''. Valoarea '''1''' reprezintă piesa de culoare albă, '''2''' piesa de culoare neagră etc.


== Date de iesire ==
== Date de iesire ==


Fișierul de ieșire tabla.txt va conține cel mai mare punctaj obținut.
Fișierul de ieșire '''tablaout.txt''' va conține cel mai mare punctaj obținut.


== Restrictii si precizari ==
== Restrictii si precizari ==


*1 n 20
*1 ⩽ n ⩽ 20


== Exemplul 1 ==
== Exemplul 1 ==
;Intrare
;tablain.txt
:3
:3
:1 1 2
:1 1 2
Line 30: Line 30:
:3 4 5
:3 4 5


;Iesire
;tablaout.txt
;Datele introduse corespund restrictiilor impuse
:Datele introduse corespund restrictiilor impuse
:2
:2


== Exemplul 2 ==
== Exemplul 2 ==
;Intrare
;tablain.txt
:3
:3
:0 0 0
:0 0 0
:-10 23 3
:-10 23 3
:1 72 0
:1 72 0
;Iesire
 
;Datele introduse nu corespund restrictiilor impuse
:Datele introduse nu corespund restrictiilor impuse





Revision as of 09:42, 27 December 2023

Enunt

O tablă de șah de dimensiune n x n conține pe toate pătrățelele câte o piesă cu una din culorile: alb, negru, roșu, verde sau albastru. Pe tablă nu există 3 piese consecutive pe aceeași linie sau coloană de aceeași culoare. O mutare presupune interschimbarea a două piese alăturate, fie pe o linie, fie pe o coloană. După mutare se acordă punctaj dacă se obțin următoarele situații și nu numai:

  • 3 piese de aceeași culoare consecutive pe o linie sau o coloană = 1 punct;
  • 3 piese de aceeași culoare consecutive pe o linie și o coloană = 5 puncte;

La orice situație de mai sus, o piesă în plus de aceeași culoare mai contribuie cu încă 1 la punctaj. De exemplu, 4 piese de aceeași culoare consecutive pe o linie sau o coloană = 2 puncte. Punctajele obținute de piesele interschimbate se adună. Punctajul este 0 dacă nu se obțin măcar 3 piese consecutive de aceeași culoare.

Cerinta

Găsiți cel mai mare punctaj obținut în urma unei singure mutări.

Date de intrare

Fișierul de intrare tablain.txt conține, pe prima linie, numărul natural n, ce reprezintă dimensiunea tablei. Pe fiecare dintre următoarele n linii se află câte n valori separate prin spatii. Valorile posibile pot fi: 1, 2, 3, 4 și 5. Valoarea 1 reprezintă piesa de culoare albă, 2 piesa de culoare neagră etc.

Date de iesire

Fișierul de ieșire tablaout.txt va conține cel mai mare punctaj obținut.

Restrictii si precizari

  • 1 ⩽ n ⩽ 20

Exemplul 1

tablain.txt
3
1 1 2
2 2 1
3 4 5
tablaout.txt
Datele introduse corespund restrictiilor impuse
2

Exemplul 2

tablain.txt
3
0 0 0
-10 23 3
1 72 0
Datele introduse nu corespund restrictiilor impuse


Rezolvare

<syntaxhighlight lang="python3" line="1"> def calculeaza_punctaj(tabla):

   punctaj = 0
   n = len(tabla)
   for i in range(n):
       for j in range(n - 2):
           # Verificare pe linii
           if tabla[i][j] == tabla[i][j + 1] == tabla[i][j + 2]:
               punctaj += 1
               if j + 3 < n and tabla[i][j] == tabla[i][j + 3]:
                   punctaj += 1
           # Verificare pe coloane
           if tabla[j][i] == tabla[j + 1][i] == tabla[j + 2][i]:
               punctaj += 1
               if j + 3 < n and tabla[j][i] == tabla[j + 3][i]:
                   punctaj += 1
   return punctaj


def maxim_punctaj_dupa_mutare(tabla):

   n = len(tabla)
   max_punctaj = 0
   for i in range(n):
       for j in range(n - 1):
           # Efectuare interschimbare pe linii
           tabla[i][j], tabla[i][j + 1] = tabla[i][j + 1], tabla[i][j]
           punctaj_linii = calculeaza_punctaj(tabla)
           # Efectuare interschimbare pe coloane
           tabla[i][j], tabla[i][j + 1] = tabla[i][j + 1], tabla[i][j]
           tabla[j][i], tabla[j + 1][i] = tabla[j + 1][i], tabla[j][i]
           punctaj_coloane = calculeaza_punctaj(tabla)
           # Restaurare tabla la starea initiala
           tabla[i][j], tabla[i][j + 1] = tabla[i][j + 1], tabla[i][j]
           tabla[j][i], tabla[j + 1][i] = tabla[j + 1][i], tabla[j][i]
           # Actualizare punctaj maxim
           max_punctaj = max(max_punctaj, punctaj_linii, punctaj_coloane)
   return max_punctaj


  1. Citire date de intrare

with open("tabla.txt", "r") as fin:

   n = int(fin.readline())
   tabla = [list(map(int, fin.readline().split())) for _ in range(n)]
  1. Calcul maxim punctaj dupa o mutare

rezultat = maxim_punctaj_dupa_mutare(tabla)

  1. Scriere rezultat in fisier

with open("tabla.txt", "w") as fout:

   fout.write(str(rezultat))

</syntaxhighlight>

Explicatie

Prin interschimbarea elementului (1,3) cu (2,3) se obține:

1 1 1
2 2 2
3 4 5

și am 1 punct din prima linie și 1 punct din a doua linie.