Rezolvare PBinfo #4135

Alexandra citește un text format din litere mici și mari ale alfabetului englez și spații. Fiind interesată de criptografie, ea elimină toate spațiile și apoi încadrează literele, în ordinea în care acestea apar în text, într-un tablou bidimensional, în care numărul de linii este mai mic sau egal decât numărul de coloane. Întrucât pot exista mai multe moduri de încadrare a textului, Alexandra îl alege pe cel pentru care diferența absolută dintre numărul liniilor și al coloanelor tabloului este minimă. Completarea cu literele textului a tabloului bidimensional se face în ordinea crescătoare a liniilor și în cadrul fiecărei linii, în ordinea crescătoare a coloanelor.

Cerința

1) Notând cu N numărul de linii și cu M numărul de coloane ale tabloul bidimensional obținut, afișați elementele acestuia pe primele N linii ale fișierului de ieșire, fiecare linie conținând exact M litere fără spații între ele. Afișarea se va face în ordinea crescătoare a indicilor liniilor și pe fiecare linie în ordinea crescătoare a indicilor coloanelor.

2) Determinați cel mai lung palindrom de pe o linie sau de pe o coloană a tabloului obținut. În cazul în care există mai multe palindromuri de aceeași lungime, se va afișa cel care este cel mai mare din punct de vedere lexicografic conform codului ASCII.

3) Determinați care este numărul maxim de elemente dintr-un subtablou dreptunghiular, ce conține doar vocale.

Date de intrare

Datele de intrare se citesc din fișierul text.in, care are următoarea structură:

• pe prima linie se află numărul natural C care poate avea doar valorile 1, 2 sau 3, semnificând numărul cerinței de rezolvat;
• pe a doua linie se află textul pe care îl va prelucra Alexandra.

Date de ieșire

Datele de ieșire se vor afișa în fișierul text.out, care are următoarea structură:

• dacă C = 1, N linii, fiecare conținând câte M litere, repezentând elementele tabloului obținut;
• dacă C = 2, o singură linie conținând cel mai lung palindrom determinat;
• dacă C = 3, o singură linie conținând un număr natural reprezentând numărul de elemente din subtabloul determinat.

Restricții și precizări

• 2 ≤ numărul total de caractere din textul inițial al Alexandrei ≤ 200.000
• vocalele sunt: {A, E, I, O, U, a, e, i, o, u}
• se garantează că N, numărul de linii ale tabloului obținut este > 1
• Pentru 16 puncte, C = 1 și numărul de caractere din șirul inițial ≤ 10.000
• Pentru 36 puncte, C = 2 și numărul de caractere din șirul inițial ≤ 1000
• Pentru 16 puncte, C = 3 și numărul de caractere din șirul inițial ≤ 1000
• Pentru 16 puncte, C = 3 și numărul de caractere din șirul inițial ≤ 50.000
• Pentru 16 puncte, C = 3, fără restricții suplimentare

Exemplul 1:

text.in

1
Ana nu are mere

text.out

Anan
uare
mere

Explicație

Numărul de caractere după eliminare spațiilor este 12. Textul plasat în tablou conține N=3 linii și M = 4 coloane.

Exemplul 2:

text.in

1
A fost odata ca niciodata

text.out

Afostod
atacani
ciodata

Explicație

Numărul de caractere după eliminare spațiilor este 21. Textul plasat în tablou conține N = 3 linii și M = 7 coloane.

Exemplul 3:

text.in

2
A fost odata ca niciodata

text.out

oao

Explicație

Afostod
atacani
ciodata
Tabloul are pe coloana 3 palindromul oao iar pe liniile 2 și 3 palindromul ata.

Exemplul 4:

text.in

3
Aceasta oaie e alba

text.out

6

Explicație

Acea
stao
aiee
alba