Fişierul intrare/ieşire:dreptunghi3.in, dreptunghi3.outSursăOJSEPI 2021, clasele 11-12
AutorZoltan SzaboAdăugată deMatteoalexandruMatteo Verzotti Matteoalexandru
Timp execuţie pe test0.25 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Dreptunghi3

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 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 si 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 * 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 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 * 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ţă

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

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.

Date de ieşire

  • 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;

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.

Exemplu 1

dreptunghi3.indreptunghi3.out
1
H3V2**H2V3**V2*V3**
7

Explicaţie: În urma segmentării se obţin 7 dreptunghiuri.

Exemplu 2

dreptunghi3.indreptunghi3.out
2
H3V2**H2V3**V2*V3**
6 6

Explicaţie: Cel mai mic dreptunghi pentru care codul este valid are 6 linii şi 6 coloane.

Exemplu 3

dreptunghi3.indreptunghi3.out
3
H3V2**H2V3**V2*V3**
4

Explicaţie: Numărul codurilor echivalente cu cel citit este 4 (vezi exemplul din enunţ).

Exemplu 4

dreptunghi3.indreptunghi3.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**.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?