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***, va arăta ca în Figura 1.

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***

și corespund dreptunghiului de mai jos:

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.

Exemplul 1:

Intrare

1
H3V2**H2V3**V2*V3**

Ieșire

7

Explicație

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

Exemplul 2:

Intrare

2
H3V2**H2V3**V2*V3**

Ieșire

6 6

Explicație

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

Rezolvare

<syntaxhighlight lang="python" line="1"> MOD = 1000000007

class RetType:

   def __init__(self, type, offset, cnt, s1, s2):
       self.type = type
       self.offset = offset
       self.cnt = cnt
       self.s1 = s1
       self.s2 = s2

sir = "" din = [0] * 355 pos = 0 cntDrept = 0 cntStr = 1 lenH = 0 lenV = 0

def parseInt():

   global pos
   s = 0
   while pos < len(sir) and '0' <= sir[pos] <= '9':
       s = s * 10 + int(sir[pos]) - int('0')
       pos += 1
   return s

def solve(h, v):

   global pos, cntDrept, cntStr, lenH, lenV, din
   currType = sir[pos]
   pos += 1
   if currType == '*':
       cntDrept += 1
       lenH = max(lenH, h + 1)
       lenV = max(lenV, v + 1)
       return RetType('*', 0, 0, "", "*")
   k = parseInt()
   ret = RetType(currType, k, 1, "", "")

   aux1 = solve(h, v)
   if aux1.type == currType:
       ret.cnt += aux1.cnt
       ret.s1 += aux1.s1
       ret.s1 += currType
       ret.s1 += str(k - aux1.offset)
       ret.s1 += aux1.s2
   else:
       cntStr = (1 * cntStr * din[aux1.cnt]) % MOD
       ret.s1 += currType
       ret.s1 += str(k)
       ret.s1 += aux1.s1 + aux1.s2

   newH = h
   newV = v
   if currType == 'H':
       newH += k
   else:
       newV += k
   aux2 = solve(newH, newV)
   if aux2.type == currType:
       ret.cnt += aux2.cnt
       ret.offset += aux2.offset
       ret.s1 += aux2.s1
       ret.s2 += aux2.s2
   else:
       cntStr = (1 * cntStr * din[aux2.cnt]) % MOD
       ret.s2 += aux2.s1 + aux2.s2

   return ret

def restrictii(type, sir):

   if not (1 <= type <= 4):
       print("Datele nu corespund restrictiilor impuse")
       return False
   if not (0 < len(sir) < 350):
       print("Datele nu corespund restrictiilor impuse")
       return False
   return True

def main():

   global pos, sir, cntStr, din
   type = int(input())
   sir = input().strip()
   
   if not restrictii(type, sir):
       return
   
   din[0] = din[1] = 1
   for i in range(2, 351):
       din[i] = 0
       for j in range(i):
           din[i] = (din[i] + 1 * din[j] * din[i - j - 1]) % MOD
   
   aux = solve(0, 0)
   cntStr = (1 * cntStr * din[aux.cnt]) % MOD
   
   if type == 1:
       print(cntDrept)
   elif type == 2:
       print(lenH, lenV)
   elif type == 3:
       print(cntStr)
   else:
       print(aux.s1 + aux.s2)

if __name__ == "__main__":

   main()

</syntaxhighlight>