== include(page="template/taskheader" task_id="dreptunghi3") ==
Poveste şi cerinţă...
Avem la dispoziţie un dreptunghi de dimensiuni $N * 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 * M$ (cel de sus) şi $(N-k) * M$ (cel de jos) – în cazul unei linii {$(H)$}orizontale, operaţie codificată prin $Hk$
* de dimensiuni $N * k$ (cel din stânga) şi $N * (M-k)$ (cel din dreapta) – în cazul unei linii {$V$}erticale, 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ă $C{~1~}$ si $C{~2~}$ 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 *;
* $HkC{~1~}C{~2~}$ – se trasează linia *orizontală* la poziţia $k$, se segmentează şi numerotează dreptunghiul de sus conform codului $C{~1~}$, apoi se continuă cu segmentarea şi numerotarea dreptunghiului de jos conform codului $C{~2~}$;
* $VkC{~1~}C{~2~}$ – se trasează linia *verticală* la poziţia $k$, se segmentează şi numerotează dreptunghiul din stânga conform codului $C{~1~}$, apoi se continuă cu segmentarea şi numerotarea dreptunghiului din dreapta conform codului $C{~2~}$.
!>problema/dreptunghi3?dreptunghi.png!
De exemplu, dreptunghiul de dimensiuni $8 * 6$ (8 linii, 6 coloane) segmentat şi numerotat conform codului
$C = H5H3V2**V3**V5V2***$, va arăta ca în _Figura 1 (dreapta)_.
Un cod de segmentare şi numerotare $C$ este *valid* pentru un dreptunghi de dimensiuni $N * M$ dacă şi numai dacă pentru fiecare operaţie de tipul $HkC{~1~}C{~2~}$ şi de tipul $VkC{~1~}C{~2~}$ 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 * 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ă:
# $H3V2**H2V3**V2*V3**$
# $H3V2**H2V3**V5V2***$
# $H5H3V2**V3**V2*V3**$
# $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ă:
# $V7*V6**$
# $V13V7***$
şi corespund dreptunghiului de mai jos:
!problema/dreptunghi3?dreptunghi2.png!
h2. Cerinţă
Se dă un cod de segmentare şi numerotare şi se cere să se afle:
# numărul de subdiviziuni pe care acesta le generează;
# dimensiunile unui dreptunghi de arie minimă pentru care acest cod este valid;
# 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);
# primul cod în ordine lexicografică echivalent cu cel dat.
h2. Date de intrare
Fişierul de intrare $dreptunghi3.in$ ...
Fişierul de intrare $dreptunghi3.in$ va conţine:
* pe prima linie valoarea lui $P$;
* de pe linia următoare un şir de caractere reprezentând codul de segmentare şi numerotare $C$.
h2. Date de ieşire
În fişierul de ieşire $dreptunghi3.out$ ...
* *Dacă valoarea citită pentru $P$ este 1*, atunci în fişierul de ieşire $dreptunghi3.out$ se va tipări numărul de subdiviziuni pe care codul $C$ le generează;
* *Dacă valoarea citită pentru $P$ este 2*, atunci în fişierul de ieşire $dreptunghi3.out$ 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 în fişierul de ieşire $dreptunghi3.out$ se va tipări numărul de codificări distincte *modulo 1 000 000 007* echivalente cu codul citit (in acest număr va fi inclus şi codul $C$ citit).
* *Dacă valoarea citită pentru $P$ este 4*, atunci în fişierul de ieşire $dreptunghi3.out$ se va tipări primul cod în ordine lexicografică echivalent cu cel dat;
h2. Restricţii
* $... ≤ ... ≤ ...$
* $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.
h2. Exemplu 1
table(example). |_. dreptunghi3.in |_. dreptunghi3.out |
| 1
H3V2**H2V3**V2*V3**
| 7
|
Explicaţie: În urma segmentării se obţin $7$ dreptunghiuri.
h2. Exemplu
h2. Exemplu 2
table(example). |_. dreptunghi3.in |_. dreptunghi3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
H3V2**H2V3**V2*V3**
| 6 6
|
h3. Explicaţie
Explicaţie: Cel mai mic dreptunghi pentru care codul este valid are $6$ linii şi $6$ coloane.
h2. Exemplu 3
table(example). |_. dreptunghi3.in |_. dreptunghi3.out |
| 3
H3V2**H2V3**V2*V3**
| 4
|
Explicaţie: Numărul codurilor echivalente cu cel citit este 4 (vezi exemplul din enunţ).
h2. Exemplu 4
table(example). |_. dreptunghi3.in |_. dreptunghi3.out |
| 4
H3V2**H2V3**V2*V3**
| H3V2**H2V3**V2*V3**
|
...
Explicaţie: Primul cod în ordine lexicografică echivalent cu cel citit este $H3V2**H2V3**V2*V3**$.
== include(page="template/taskfooter" task_id="dreptunghi3") ==
