Editing 3724 - Dreptunghi 2


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

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

Numerotarea dreptunghiului se realizează cu numerele naturale <code>1</code>, <code>2</code>, <code>3</code>, … în această ordine.

Codul <code>C</code> pentru segmentarea și numerotarea unui dreptunghi se definește recursiv. Dacă <code>C1</code> și <code>C2</code> sunt coduri de segmentare și numerotare, atunci:

* <code>*</code> – î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 <code>*</code>;
* <code>HkC1C2</code> – se trasează linia orizontală la poziția <code>k</code>, se segmentează și numerotează dreptunghiul de sus conform codului <code>C1</code>, apoi se continuă cu segmentarea și numerotarea dreptunghiului de jos conform codului <code>C2</code>;
* <code>VkC1C2</code> – se trasează linia verticală la poziția <code>k</code>, se segmentează și numerotează dreptunghiul din stânga conform codului <code>C1</code>, apoi se continuă cu segmentarea și numerotarea dreptunghiului din dreapta conform codului <code>C2</code>.

De exemplu, dreptunghiul de dimensiuni <code>8 x 6</code> (<code>8</code> linii, <code>6</code> coloane) segmentat și numerotat conform codului <code>C = H5H3V2**V3**V5V2***</code>, va arăta ca în Figura 1.

Un cod de segmentare și numerotare <code>C</code> este valid pentru un dreptunghi de dimensiuni <code>N x M</code> dacă și numai dacă pentru fiecare operație de tipul <code>HkC1C2</code> și de tipul <code>VkC1C2</code> din cadrul lui <code>C</code>, poziția <code>k</code> 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 <code>C</code>).

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

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

1. <code>H3V2**H2V3**V2*V3**</code>

2. <code>H3V2**H2V3**V5V2***</code>

3. <code>H5H3V2**V3**V2*V3**</code>

4. <code>H5H3V2**V3**V5V2***</code>

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

La nivel de caractere ordinea lexicografică este <code>H < V < *</code>. Numerele se vor compara în funcție de valoarea lor, de exemplu <code>1 < 7 < 12</code>. 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. <code>V7*V6**</code>

2. <code>V13V7***</code>

ș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 <code>1.000.000.007</code>, 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 <code>P</code>;
* de pe linia următoare un șir de caractere reprezentând codul de segmentare și numerotare <code>C</code>.

= Date de ieșire =

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

= Restricții și precizări =

* <code>0 < lungimea codului C (număr de caractere) < 350</code>
* Pentru teste în valoare de 14 puncte avem <code>P = 1</code>.
* Pentru teste în valoare de 21 de puncte avem <code>P = 2</code>.
* Pentru teste în valoare de 29 de puncte avem <code>P = 3</code>.
* Pentru teste în valoare de 36 de puncte avem <code>P = 4</code>.

= Exemplul 1: =
Intrare
 1
 H3V2**H2V3**V2*V3**
Ieșire
 7

=== Explicație ===
În urma segmentării se obțin <code>7</code> 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 <code>6</code> linii și <code>6</code> 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>