1702 - Cristale

Pietrele preţioase au fascinat omenirea încă din timpuri străvechi iar cele mai renumite dintre ele, cristalele, au devenit atât simbolul durităţii cât şi al eternităţii. În urma unui studiu ştiinţific, pe un eşantion de formă dreptunghiulară se pot observa diferite tipuri de molecule, dispuse într-o geometrie perfectă, pe M rânduri a câte N molecule fiecare, aliniate una lângă alta. O formaţiune cristalizabilă este alcătuită din 3 molecule de acelaşi tip, învecinate două câte două, având una dintre cele patru forme din imaginea alăturată (fig.1).

Fiecare formaţiune este înconjurată de jur-împrejur, ca în fig.2, de un înveliş special format şi el din molecule identice, de alt tip decât cele din formaţiunea cristalizabilă pe care o înconjoară şi o izolează de restul formaţiunilor moleculare. În acest fel, fiecare moleculă din formaţiunea cristalizabilă se învecinează la Nord, Sud, Est şi Vest cu o moleculă din aceeaşi formaţiune cristalizabilă sau cu o moleculă din învelişul special.

Fiecare formaţiune cristalizabilă se bombardează cu raze X şi în acest fel are loc cristalizarea, proces prin care învelişul special se extinde peste formaţiunea cristalizabilă pe care o înconjoară, formând o singură structură din care se va dezvolta cristalul.

Cerințe

1. Determinaţi numărul formaţiunilor cristalizabile ce pot fi identificate pe eşantionul analizat.
2. Afişaţi eşantionul rezultat după cristalizare.

Date de intrare

Fișierul de intrare cristale.in conține pe prima linie un număr natural c reprezentând cerinţa care trebuie să fie rezolvată (1 sau 2). Pe cea de-a doua linie se află două numere naturale M şi N, separate printr-un spaţiu, având semnificaţia din enunţ. Pe următoarele M linii se află câte N numere naturale, separate prin câte un spaţiu, reprezentând moleculele din eşantionul analizat.

Date de ieșire

Dacă valoarea lui c este 1, atunci se va rezolva numai cerinţa 1, caz în care pe prima linie a fişierului cristale.out va fi scris un număr natural reprezentând numărul formaţiunilor cristalizabile identificate pe eşantionul analizat. Dacă valoarea lui c este 2, atunci se va rezolva numai cerinţa 2. În acest caz, fişierul de ieşire cristale.out va conţine pe fiecare dintre primele M linii, câte N numere naturale separate prin câte un spaţiu, reprezentând moleculele eşantionului rezultat după cristalizare.

Restricții și precizări

• 4 ≤ M,N ≤ 800 şi tipul fiecărei molecule este exprimat printr-un număr natural din intervalul [1,16];
• pe marginea eşantionului nu pot fi identificate formaţiuni cristalizabile; există cel puţin o formaţiune cristalizabilă pe eşantionul analizat;
• eşantionul nu conţine formaţiuni cristalizabile lipite (cu celule vecine pe una din cele patru direcţii);
• pentru rezolvarea corectă a cerinţei 1 se acordă 30% din punctaj, iar pentru rezolvarea corectă a cerinţei 2 se acordă 70% din punctaj.

Exemplul 1

cristale.in

1
6 8
5 6 6 1 5 2 6 5
6 9 9 6 1 7 1 2
6 6 9 6 3 4 1 6
2 2 6 3 4 7 4 2
8 8 2 4 7 7 4 6 
8 2 7 2 4 4 2 5

cristale.out

2

Explicație

Se va rezolva cerinţa 1 a problemei.

Eşantionul are 6 rânduri cu câte 8 molecule pe fiecare rând. Pe acest eşantion observăm o formaţiune cristalizabilă cu celule de tip 9, izolată de învelişul special format din celule identice, toate de tip 6 şi o formaţiune cristalizabilă cu celule de tip 7, izolată de învelişul special format din celule identice, toate de tip 4.

Formaţiunea de 3 molecule de tip 8 nu este o formaţiune cristalizabilă întrucât se află pe marginea eşantionului.

Exemplul 1

cristale.in

1
6 8
5 6 6 1 5 2 6 5
6 9 9 6 1 7 1 2
6 6 9 6 3 4 1 6
2 2 6 3 4 7 4 2
8 8 2 4 7 7 4 6 
8 2 7 2 4 4 2 5

cristale.out

2

Explicație

Se va rezolva cerinţa 1 a problemei.

Eşantionul are 6 rânduri cu câte 8 molecule pe fiecare rând. Pe acest eşantion observăm o formaţiune cristalizabilă cu celule de tip 9, izolată de învelişul special format din celule identice, toate de tip 6 şi o formaţiune cristalizabilă cu celule de tip 7, izolată de învelişul special format din celule identice, toate de tip 4.

Formaţiunea de 3 molecule de tip 8 nu este o formaţiune cristalizabilă întrucât se află pe marginea eşantionului.

<syntaxhighlight lang="python" line="1"> def is_valid_position(x, y, M, N):

   return 0 <= x < M and 0 <= y < N

def identify_crystalline_formations(sample, M, N):

   directions = [
       [(0, 0), (0, 1), (0, 2)],  # Orizontal
       [(0, 0), (1, 0), (2, 0)],  # Vertical
       [(0, 0), (0, 1), (1, 0)],  # L form
       [(0, 0), (1, 0), (1, 1)],  # Inverse L form
   ]
   
   formations = []
   
   for i in range(M):
       for j in range(N):
           for direction in directions:
               molecules = set()
               valid = True
               for dx, dy in direction:
                   x, y = i + dx, j + dy
                   if not is_valid_position(x, y, M, N):
                       valid = False
                       break
                   molecules.add(sample[x][y])
               
               if valid and len(molecules) == 1:
                   formations.append((i, j, direction))
   
   return formations

def apply_crystallization(sample, formations, M, N):

   for (i, j, direction) in formations:
       surrounding_type = None
       formation_type = sample[i][j]
       
       # Identify the surrounding type
       for dx, dy in direction:
           x, y = i + dx, j + dy
           for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
               if is_valid_position(nx, ny, M, N) and sample[nx][ny] != formation_type:
                   surrounding_type = sample[nx][ny]
                   break
           if surrounding_type:
               break
       
       # Apply the crystallization
       if surrounding_type:
           for dx, dy in direction:
               x, y = i + dx, j + dy
               sample[x][y] = surrounding_type

def print_sample(sample):

   for row in sample:
       print(' '.join(map(str, row)))

1. Exemplu de utilizare

M = 5 N = 5 sample = [

   [1, 1, 1, 2, 3],
   [1, 4, 2, 3, 2],
   [4, 2, 3, 2, 2],
   [2, 2, 3, 1, 4],
   [3, 1, 4, 4, 4],

]

formations = identify_crystalline_formations(sample, M, N) print(f"Formațiuni cristalizabile: {formations}") apply_crystallization(sample, formations, M, N) print("Eșantion după cristalizare:") print_sample(sample) </syntaxhighlight>