3724 - Dreptunghi 2

Avem la dispoziție un dreptunghi de dimensiuni N x M. Ne este util ca dreptunghiul nostru să se asemene cu o matrice, de aceea vom considera că are N linii și M coloane. Vom segmenta si numerota dreptunghiul nostru după un anumit cod C. Prin segmentare se înțelege trasarea unei linii orizontale sau verticale la o anumită poziție k, ce va despărți dreptunghiul nostru în alte două dreptunghiuri mai mici:

• de dimensiuni k x M (cel de sus) și (N - k) x M (cel de jos) – în cazul unei linii (H)orizontale, operație codificată prin Hk
• de dimensiuni N x k (cel din stânga) și N x (M - k) (cel din dreapta) – în cazul unei linii Verticale, operație codificată prin Vk

Numerotarea dreptunghiului se realizează cu numerele naturale 1, 2, 3, … în această ordine. Codul C pentru segmentarea și numerotarea unui dreptunghi se definește recursiv. Dacă C1 și C2 sunt coduri de segmentare și numerotare, atunci:

• – în fiecare căsuță a dreptunghiului se va scrie valoarea curentă a numerotării. După aceea, această valoare este incrementată pentru a fi folosită de o ulterioară operație de tipul *;
• HkC1C2 – se trasează linia orizontală la poziția k, se segmentează și numerotează dreptunghiul de sus conform codului C1, apoi se continuă cu segmentarea și numerotarea dreptunghiului de jos conform codului C2;
• VkC1C2 – se trasează linia verticală la poziția k, se segmentează și numerotează dreptunghiul din stânga conform codului C1, apoi se continuă cu segmentarea și numerotarea dreptunghiului din dreapta conform codului C2.

De exemplu, dreptunghiul de dimensiuni 8 x 6 (8 linii, 6 coloane) segmentat și numerotat conform codului C = H5H3V2**V3**V5V2*** Un cod de segmentare și numerotare C este valid pentru un dreptunghi de dimensiuni N x M dacă și numai dacă pentru fiecare operație de tipul HkC1C2 și de tipul VkC1C2 din cadrul lui C, poziția k la care se trage linia orizontală, sau verticală respectiv, se află strict în interiorul dreptunghiului curent (adică pe ambele părți ale liniei trasate există cel puțin o linie si cel puțin o coloană rămase care vor fi ulterior numerotate conform definiției recursive a codului C).

Un cod de segmentare și numerotare C valid pentru un dreptunghi de dimensiuni N x M generează mai multe subdiviziuni (dreptunghiuri mai mici) delimitate de liniile orizontale și verticale trasate în cadrul lui C. De exemplu, pentru dreptunghiul din Figura 1 codul C din exemplul de mai sus generează 7 subdiviziuni.

Codul C nu este unic determinat. Pentru dreptunghiul segmentat și numerotat din Figura 1 există 4 coduri echivalente, pe care le scriem în ordine lexicografică în cele ce urmează:

1. H3V2**H2V3**V2*V3**
2. H3V2**H2V3**V5V2***
3. H5H3V2**V3**V2*V3**
4. H5H3V2**V3**V5V2***

Pentru stabilirea ordinii lexicografice a două codificări, fiecare informație compactă ce face parte din secvență se va considera entitate separată: adică simbolurile H, V, * de tip caracter, respectiv numerele k de tip întreg, indiferent de numărul de cifre din care sunt formate.

La nivel de caractere ordinea lexicografică este H < V < *. Numerele se vor compara în funcție de valoarea lor, de exemplu 1 < 7 < 12. Vom considera că un caracter este mai mic lexicografic decât un număr întreg.

De exemplu, următoarele două coduri echivalente sunt scrise în ordine lexicografică:

1. V7*V6**
2. V13V7***

Cerința

Se dă un cod de segmentare și numerotare și se cere să se afle:

1. numărul de subdiviziuni pe care acesta le generează;
2. dimensiunile unui dreptunghi de arie minimă pentru care acest cod este valid;
3. numărul de codificări distincte modulo 1.000.000.007, echivalente cu codul citit (în acest număr va fi inclus și codul inițial);
4. primul cod în ordine lexicografică echivalent cu cel dat.

Date de intrare

De la intrarea standard se vor citi:

• de pe prima linie valoarea lui P;
• de pe linia următoare un șir de caractere reprezentând codul de segmentare și numerotare C.

Date de ieșire

• Dacă valoarea citită pentru P este 1, atunci la ieșirea standard se va tipări numărul de subdiviziuni pe care codul C le generează;
• Dacă valoarea citită pentru P este 2, atunci la ieșirea standard se vor tipări două numere N și M separate printr-un spațiu, dimensiunile unui dreptunghi de arie minimă pentru care codul C citit este valid. În caz că există mai multe, se acceptă oricare;
• Dacă valoarea citită pentru P este 3, atunci la ieșirea standard se va tipări numărul de codificări distincte modulo 1.000.000.007 echivalente cu codul citit (în acest număr va fi inclus și codul C citit).
• Dacă valoarea citită pentru P este 4, atunci la ieșirea standard se va tipări primul cod în ordine lexicografică echivalent cu cel dat;

Restricții și precizări

• 0 < lungimea codului C (număr de caractere) < 350

• Pentru teste în valoare de 14 puncte avem P = 1. • Pentru teste în valoare de 21 de puncte avem P = 2. • Pentru teste în valoare de 29 de puncte avem P = 3. • Pentru teste în valoare de 36 de puncte avem P = 4.

Exemplu 1

Intrare

1

H3V2**H2V3**V2*V3**

Ieșire

7

Explicatie

În urma segmentării se obțin 7 dreptunghiuri.

Exemplu 2

Intrare

2

H3V2**H2V3**V2*V3**

Ieșire

6 6

Explicatie

Cel mai mic dreptunghi pentru care codul este valid are 6 linii și 6 coloane.

Rezolvare

<syntaxhighlight lang="python" line>

1. 3724 - Dreptunghi 2

MOD = 1000000007

def count_subdivisions(code):

   return count_subdivisions_helper(code) % MOD

def dimensions_of_minimal_rectangle(code):

   _, _, min_area_rectangle = dimensions_of_minimal_rectangle_helper(code)
   return min_area_rectangle

def count_equivalent_codes(code):

   equivalent_codes = set()
   generate_equivalent_codes(code, "", equivalent_codes)
   return len(equivalent_codes) % MOD

def lexicographically_first_equivalent_code(code):

   equivalent_codes = set()
   generate_equivalent_codes(code, "", equivalent_codes)
   return min(equivalent_codes)

def count_subdivisions_helper(code):

   if not (0 < len(code) < 350):
       return 0

   if code[0] == 'H':
       k, rest = get_number(code[1:])
       count_upper = count_subdivisions_helper(rest)
       count_lower = count_subdivisions_helper(rest[1:])
       return (count_upper * count_lower) % MOD
   elif code[0] == 'V':
       k, rest = get_number(code[1:])
       count_left = count_subdivisions_helper(rest)
       count_right = count_subdivisions_helper(rest[1:])
       return (count_left * count_right) % MOD
   elif code[0] == '*':
       return 1
   else:
       return 0

def dimensions_of_minimal_rectangle_helper(code):

   if not (0 < len(code) < 350):
       return 0, 0, 0

   if code[0] == 'H':
       k, rest = get_number(code[1:])
       _, _, area_upper = dimensions_of_minimal_rectangle_helper(rest)
       _, _, area_lower = dimensions_of_minimal_rectangle_helper(rest[1:])
       return k, max(area_upper, area_lower), area_upper + area_lower
   elif code[0] == 'V':
       k, rest = get_number(code[1:])
       _, _, area_left = dimensions_of_minimal_rectangle_helper(rest)
       _, _, area_right = dimensions_of_minimal_rectangle_helper(rest[1:])
       return max(area_left, area_right), k, area_left + area_right
   elif code[0] == '*':
       return 1, 1, 1
   else:
       return 0, 0, 0

def generate_equivalent_codes(code, current, equivalent_codes):

   if not (0 < len(code) < 350):
       return

   if code[0] == 'H':
       k, rest = get_number(code[1:])
       generate_equivalent_codes(rest, current + 'H' + str(k), equivalent_codes)
       generate_equivalent_codes(rest[1:], current + 'V' + str(k), equivalent_codes)
   elif code[0] == 'V':
       k, rest = get_number(code[1:])
       generate_equivalent_codes(rest, current + 'H' + str(k), equivalent_codes)
       generate_equivalent_codes(rest[1:], current + 'V' + str(k), equivalent_codes)
   elif code[0] == '*':
       equivalent_codes.add(current)
   else:
       generate_equivalent_codes(code[1:], current + code[0], equivalent_codes)

def get_number(s):

   num = 0
   i = 0
   while i < len(s) and s[i].isdigit():
       num = num * 10 + int(s[i])
       i += 1
   return num, s[i:]

if __name__ == "__main__":

   P = int(input())
   C = input()

   if P == 1:
       print(count_subdivisions(C))
   elif P == 2:
       N, M, _ = dimensions_of_minimal_rectangle(C)
       print(N, M)
   elif P == 3:
       print(count_equivalent_codes(C))
   elif P == 4:
       print(lexicographically_first_equivalent_code(C))

</syntaxhighlight>