0617 - Piese: Diferență între versiuni

De la Universitas MediaWiki
(Pagină nouă: == Cerința == Într-un tărâm îndepărtat, un inginer auto trebuie să organizeze piese de schimb într-o fabrică. Piesele sunt aranjate într-o matrice pătratică, iar fiecare celulă a matricei reprezintă un tip de piesă. Inginerul trebuie să genereze această matrice și să afișeze piesele în ordinea dorită. == Date de intrare == Programul citește de la tastatură: Un număr întreg n reprezentând dimensiunea matricei pătratice (n x n). == Date de ieșire =...)
 
Fără descriere a modificării
 
(Nu s-au afișat 2 versiuni intermediare efectuate de același utilizator)
Linia 1: Linia 1:
== Cerința ==
== Cerința ==
Într-un tărâm îndepărtat, un inginer auto trebuie să organizeze piese de schimb într-o fabrică. Piesele sunt aranjate într-o matrice pătratică, iar fiecare celulă a matricei reprezintă un tip de piesă. Inginerul trebuie să genereze această matrice și să afișeze piesele în ordinea dorită.
Considerăm o tablă de șah pătratică formată din 2n linii și 2n coloane, unde n este un număr natural nenul, formată din 2n*2n zone. Aceasta poate fi acoperită, cu excepția unei singure zone, cu piese în formă de L, fiecare piesă acoperind 3 zone. De exemplu, pentru n=2, o acoperire este următoarea, în care zona neagră este cea neacoperită de piese:
Pentru n dat, determinați o modalitate de acoperire a tablei cu piese, astfel încât să nu se suprapună piesele și să rămână o singură zonă neacoperită.
== Date de intrare ==
== Date de intrare ==
Programul citește de la tastatură:
Programul citește de la tastatură numărul n
== Date de ieșire ==
Programul va afișa pe ecran o matrice care reprezintă tabla, cu următoarele proprietăți:


Un număr întreg n reprezentând dimensiunea matricei pătratice (n x n).
*matricea va avea 2n linii și 2n coloane
== Date de ieșire ==
*matricea va conține un singur element 0, reprezentând zona neacoperită
Pe ecran se va afișa matricea generată, fiecare rând al matricei fiind pe o linie separată.
*fiecare piesă va fi marcată pe tablă prin trei elemente cu aceeași valoare, dispuse în formă de L
*oricare două piese de pe tablă vor fi marcate cu valori diferite
*piesele vor fi marcate cu valori naturale consecutive, începând cu 1
*fiecare linie a matricei va fi afișată pe câte o linie a ecranului, elementele de pe o linie fiind separate prin câte un spațiu
== Restricții și precizări ==
== Restricții și precizări ==
*1 ⩽ '''n''' ⩽ 1000
*1 ≤ n ≤ 10
Valorile din matrice sunt numere întregi generate automat în intervalul [0, 10]
*orice aranjare corectă a pieselor se ia în considerare
 
== Exemplu 1 ==
== Exemplu 1 ==
;Intrare
;Intrare
3
2
;Iesire
;Iesire
8 3 4<br>
2 2 5 5<br>
1 5 4<br>
2 1 1 5<br>
3 1 0
3 0 1 4<br>
== Exemplu 2 ==
3 3 4 4
;Intrare
 
0
;Iesire
Datele de intrare nu corespund restricțiilor impuse.
== Rezolvare ==
== Rezolvare ==
<syntaxhighlight lang="python" line>
<syntaxhighlight lang="python" line>
import random
def acopera_tabla(tabla, top, left, defect_row, defect_col, size, counter):
    if size == 2:
        # Plasează piesele L în funcție de poziția zonei neacoperite
        counter += 1
        if defect_row == top:
            if defect_col == left:
                tabla[top][left + 1] = counter
                tabla[top + 1][left] = counter
                tabla[top + 1][left + 1] = counter
            else:
                tabla[top][left] = counter
                tabla[top + 1][left] = counter
                tabla[top + 1][left + 1] = counter
        else:
            if defect_col == left:
                tabla[top][left] = counter
                tabla[top][left + 1] = counter
                tabla[top + 1][left + 1] = counter
            else:
                tabla[top][left] = counter
                tabla[top][left + 1] = counter
                tabla[top + 1][left] = counter
        return counter


def citeste_dimensiune():
     half = size // 2
     try:
     mid_row, mid_col = top + half, left + half
        n = int(input("Introduceți dimensiunea matricii pătratice (n): "))
        return n
     except ValueError:
        return None


def valideaza_dimensiune(n):
    # Plasează piesa L centrală
     return 1 <= n <= 100
    counter += 1
    if defect_row < mid_row and defect_col < mid_col:
        tabla[mid_row - 1][mid_col] = counter
        tabla[mid_row][mid_col - 1] = counter
        tabla[mid_row][mid_col] = counter
     elif defect_row < mid_row and defect_col >= mid_col:
        tabla[mid_row - 1][mid_col - 1] = counter
        tabla[mid_row][mid_col - 1] = counter
        tabla[mid_row][mid_col] = counter
    elif defect_row >= mid_row and defect_col < mid_col:
        tabla[mid_row - 1][mid_col - 1] = counter
        tabla[mid_row - 1][mid_col] = counter
        tabla[mid_row][mid_col] = counter
    else:
        tabla[mid_row - 1][mid_col - 1] = counter
        tabla[mid_row - 1][mid_col] = counter
        tabla[mid_row][mid_col - 1] = counter


def genereaza_matrice(n):
    # Apel recursiv pentru fiecare submatrice
     matrice = []
    counter = acopera_tabla(tabla, top, left, defect_row, defect_col, half, counter)
    for i in range(n):
     counter = acopera_tabla(tabla, top, mid_col, mid_row - 1, mid_col, half, counter)
        rand = [random.randint(-1000, 1000) for _ in range(n)]
    counter = acopera_tabla(tabla, mid_row, left, mid_row, mid_col - 1, half, counter)
        matrice.append(rand)
    counter = acopera_tabla(tabla, mid_row, mid_col, mid_row, mid_col, half, counter)
    return matrice


def afiseaza_matrice(matrice):
    return counter
     for rand in matrice:
 
         print(" ".join(map(str, rand)))
def afiseaza_tabla(tabla):
     for linie in tabla:
         print(" ".join(map(str, linie)))


def main():
def main():
     n = citeste_dimensiune()
     n = int(input().strip())
      
      
     if n is None or not valideaza_dimensiune(n):
     N = 2 ** n
        print("Datele de intrare nu corespund restricțiilor impuse.")
    tabla = [[0] * N for _ in range(N)]
        return
 
      
     # Inițializați o singură zonă neacoperită
     print("Datele de intrare corespund restricțiilor impuse.")
     defect_row, defect_col = 0, 0
     matrice = genereaza_matrice(n)
     tabla[defect_row][defect_col] = -1
     afiseaza_matrice(matrice)
 
    acopera_tabla(tabla, 0, 0, defect_row, defect_col, N, 1)
     afiseaza_tabla(tabla)


if __name__ == "__main__":
if __name__ == "__main__":
     main()
     main()


</syntaxhighlight>
</syntaxhighlight>

Versiunea curentă din 2 iunie 2024 22:02

Cerința

Considerăm o tablă de șah pătratică formată din 2n linii și 2n coloane, unde n este un număr natural nenul, formată din 2n*2n zone. Aceasta poate fi acoperită, cu excepția unei singure zone, cu piese în formă de L, fiecare piesă acoperind 3 zone. De exemplu, pentru n=2, o acoperire este următoarea, în care zona neagră este cea neacoperită de piese: Pentru n dat, determinați o modalitate de acoperire a tablei cu piese, astfel încât să nu se suprapună piesele și să rămână o singură zonă neacoperită.

Date de intrare

Programul citește de la tastatură numărul n

Date de ieșire

Programul va afișa pe ecran o matrice care reprezintă tabla, cu următoarele proprietăți:

  • matricea va avea 2n linii și 2n coloane
  • matricea va conține un singur element 0, reprezentând zona neacoperită
  • fiecare piesă va fi marcată pe tablă prin trei elemente cu aceeași valoare, dispuse în formă de L
  • oricare două piese de pe tablă vor fi marcate cu valori diferite
  • piesele vor fi marcate cu valori naturale consecutive, începând cu 1
  • fiecare linie a matricei va fi afișată pe câte o linie a ecranului, elementele de pe o linie fiind separate prin câte un spațiu

Restricții și precizări

  • 1 ≤ n ≤ 10
  • orice aranjare corectă a pieselor se ia în considerare

Exemplu 1

Intrare

2

Iesire

2 2 5 5
2 1 1 5
3 0 1 4
3 3 4 4

Rezolvare

def acopera_tabla(tabla, top, left, defect_row, defect_col, size, counter):
    if size == 2:
        # Plasează piesele L în funcție de poziția zonei neacoperite
        counter += 1
        if defect_row == top:
            if defect_col == left:
                tabla[top][left + 1] = counter
                tabla[top + 1][left] = counter
                tabla[top + 1][left + 1] = counter
            else:
                tabla[top][left] = counter
                tabla[top + 1][left] = counter
                tabla[top + 1][left + 1] = counter
        else:
            if defect_col == left:
                tabla[top][left] = counter
                tabla[top][left + 1] = counter
                tabla[top + 1][left + 1] = counter
            else:
                tabla[top][left] = counter
                tabla[top][left + 1] = counter
                tabla[top + 1][left] = counter
        return counter

    half = size // 2
    mid_row, mid_col = top + half, left + half

    # Plasează piesa L centrală
    counter += 1
    if defect_row < mid_row and defect_col < mid_col:
        tabla[mid_row - 1][mid_col] = counter
        tabla[mid_row][mid_col - 1] = counter
        tabla[mid_row][mid_col] = counter
    elif defect_row < mid_row and defect_col >= mid_col:
        tabla[mid_row - 1][mid_col - 1] = counter
        tabla[mid_row][mid_col - 1] = counter
        tabla[mid_row][mid_col] = counter
    elif defect_row >= mid_row and defect_col < mid_col:
        tabla[mid_row - 1][mid_col - 1] = counter
        tabla[mid_row - 1][mid_col] = counter
        tabla[mid_row][mid_col] = counter
    else:
        tabla[mid_row - 1][mid_col - 1] = counter
        tabla[mid_row - 1][mid_col] = counter
        tabla[mid_row][mid_col - 1] = counter

    # Apel recursiv pentru fiecare submatrice
    counter = acopera_tabla(tabla, top, left, defect_row, defect_col, half, counter)
    counter = acopera_tabla(tabla, top, mid_col, mid_row - 1, mid_col, half, counter)
    counter = acopera_tabla(tabla, mid_row, left, mid_row, mid_col - 1, half, counter)
    counter = acopera_tabla(tabla, mid_row, mid_col, mid_row, mid_col, half, counter)

    return counter

def afiseaza_tabla(tabla):
    for linie in tabla:
        print(" ".join(map(str, linie)))

def main():
    n = int(input().strip())
    
    N = 2 ** n
    tabla = [[0] * N for _ in range(N)]

    # Inițializați o singură zonă neacoperită
    defect_row, defect_col = 0, 0
    tabla[defect_row][defect_col] = -1

    acopera_tabla(tabla, 0, 0, defect_row, defect_col, N, 1)
    afiseaza_tabla(tabla)

if __name__ == "__main__":
    main()
Adus de la „http://wiki.universitas.ro/index.php?title=0617_-_Piese&oldid=9890”