# PBinfo #4135 – text3 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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

## Cod sursă C++

```cpp
/// Dana Lica - C.J. Ex. PH
#include <fstream>
#include <cstring>
#include <cassert>
using namespace std;
ifstream f("text.in");
ofstream g("text.out");
const int NMAX = 2e5 + 1;
const int INF = 1e9;
int P;
int T;
char V[NMAX];
int N, M;
int pal_Max = 0;
string Container, Sol;
int H[NMAX];
int K, Stack[NMAX];
int Left[NMAX], Right[NMAX];
void Read ()
{
    assert(f >> P);
    assert(P == 1 || P == 2 || P == 3);
    assert(f.get());
    bool spaces = 0;
    bool minn = 0;
    bool maxn = 0;
    bool en = 0;
    int TOTAL = 0;
    char Ch = 0;
    while(f.get(Ch))
    {
        if(Ch == '\n')
        {
            en = 1;
            break;
        }
        ++TOTAL;
        assert(Ch == ' ' || (Ch >= 'a' && Ch <= 'z') || (Ch >= 'A' && Ch <= 'Z'));
        spaces |= (Ch == ' ');
        minn |= (Ch >= 'a' && Ch <= 'z');
        maxn |= (Ch >= 'A' && Ch <= 'Z');
        if((Ch >= 'a' && Ch <= 'z') || (Ch >= 'A' && Ch <= 'Z'))
            V[++T] = Ch;
    }
    assert(spaces && minn && maxn && en);
    assert(TOTAL >= 2 && TOTAL <= 2e5);
    return;
}
void Max_Pal (string S)
{
    int Size = (int)S.size() - 1;
    /// LUNGIME == 1 (MODULO 2):
    for(int i = 1; i <= Size; ++i)
    {
        int lg = 1;
        int left = i - 1, right = i + 1;
        while(left >= 1 && right <= Size && S[left] == S[right])
            lg += 2, --left, ++right;
        string now;
        for(int pos = left + 1; pos < right; ++pos)
            now += S[pos];
        if(lg > pal_Max || (lg == pal_Max && now > Sol))
            pal_Max = lg, Sol = now;
    }
    ///
    /// LUNGIME == 0 (MODULO 2):
    for(int i = 1; i < Size; ++i)
        if(S[i] == S[i + 1])
        {
            int lg = 2;
            int left = i - 1, right = i + 2;
            while(left >= 1 && right <= Size && S[left] == S[right])
                lg += 2, --left, ++right;
            string now;
            for(int pos = left + 1; pos < right; ++pos)
                now += S[pos];
            if(lg > pal_Max || (lg == pal_Max && now > Sol))
                pal_Max = lg, Sol = now;
        }
    ///
    return;
}
int MAX (int a, int b)
{
    return ((a > b) ? a : b);
}
int main()
{
    Read();
    int Min = INF;
    for(int d1 = 1; d1 * d1 <= T; ++d1)
        if(T % d1 == 0)
        {
            int d2 = T / d1;
            if((d2 - d1) < Min)
                Min = (d2 - d1), N = d1, M = d2;
        }
    assert(N > 1);
    char A[N + 1][M + 1];
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            A[i][j] = V[((i - 1) * M + j)];
    if(P == 1)
    {
        for(int i = 1; i <= N; ++i)
        {
            for(int j = 1; j <= M; ++j)
                g << A[i][j];
            g << '\n';
        }
        return 0;
    }
    if(P == 2)
    {
        for(int i = 1; i <= N; ++i)
        {
            Container = "0";
            for(int j = 1; j <= M; ++j)
                Container.push_back(A[i][j]);
            Max_Pal(Container);
        }
        for(int j = 1; j <= M; ++j)
        {
            Container = "0";
            for(int i = 1; i <= N; ++i)
                Container.push_back(A[i][j]);
            Max_Pal(Container);
        }
        g << Sol << '\n';
        return 0;
    }
    int ans = 0;
    for(int i = 1; i <= N; ++i)
    {
        for(int j = 1; j <= M; ++j)
        {
            char X = A[i][j];
            if(X >= 'A' && X <= 'Z')
                X = tolower(X);
            if(X == 'a' || X == 'e' || X == 'i' || X == 'o' || X == 'u')
                ++H[j];
            else
                H[j] = 0;
        }
        K = 0;
        for(int j = 1; j <= M; ++j)
        {
            while(K && H[j] < H[Stack[K]])
                Right[Stack[K]] = j, --K;
            Stack[++K] = j;
        }
        for(int x = 1; x <= K; ++x)
            Right[Stack[x]] = (M + 1);
        K = 0;
        for(int j = M; j >= 1; --j)
        {
            while(K && H[j] < H[Stack[K]])
                Left[Stack[K]] = j, --K;
            Stack[++K] = j;
        }
        for(int x = 1; x <= K; ++x)
            Left[Stack[x]] = 0;
        for(int j = 1; j <= M; ++j)
        {
            int now = ((Right[j] - 1) - (Left[j] + 1) + 1);
            ans = MAX(ans, H[j] * now);
        }
    }
    g << ans << '\n';
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4135)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4135/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4135/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)