Gigel a inventat un nou joc, de această dată utilizând un rebus sub forma de tablă pătratică cu n x n căsuțe. Fiecare căsuță conține câte o literă mare din alfabetul englez sau caracterul '.'. Literele formează pe orizontală sau pe verticală cuvinte delimitate prin caractere punct sau prin marginile tablei. Cel care joacă trebuie să determine cuvintele speciale din careu. Punctajul unui cuvânt se calculează ca suma codurilor ASCII ale literelor distincte care apar în acel cuvânt. Punctajul total al jocului se calculează însumând punctajele literelor distincte ale cuvintelor speciale distincte. Un cuvânt special îndeplinește simultan condițiile:

• este palindrom
• are lungime maximă relativ la alte cuvinte palindrom

Cerința

Să se scrie un program care sa determine, pentru un careu dat, punctajul maxim și cuvintele care permit obținerea punctajului maxim. Dacă nu există astfel de cuvinte se va afișa valoarea 0.

Date de intrare

Fișierul de intrare careu.in conține pe prima linie un număr natural n reprezentând dimensiunea careului. Următoarele n linii conțin fiecare câte n caractere, neseparate prin spații, reprezentând careul. Ultima linie a fișierului de intrare conține una dintre valorile 1 sau 2 reprezentând cerința.

Date de ieșire

Fișierul de ieșire careu.out conține pentru cerința 1, pe prima linie numărul de cuvinte speciale de valoare maximă găsite, iar pe următoarele linii se vor scrie aceste cuvinte în ordine alfabetică, câte unul pe linie; pentru cerința 2, pe prima linie a fișierului de ieșire se va scrie punctajul maxim determinat.

Restricții și precizări

• 2 <= n <= 50
• Cuvintele sunt scrise cu litere mari și lungimea cuvintelor din soluție trebuie să fie cel puțin 2.
• Pentru cerința 1 se acordă 60% din punctaj, iar pentru cerința 2 se acordă 30% din punctaj
• În concurs s-au acordat 10 puncte din oficiu; aici se acordă 10 puncte pentru cele trei exemple.

Exemplul 1:

careu.in

3
A.A
B.A
..C
1

careu.out

0

Explicație

Nu există nici un cuvânt special de lungime mai mare sau egală cu 2.

Exemplul 2:

careu.in

10
VERDE.CRIN
DANA.DDDDD
VOI.AOQOA.
NU.AAOTE..
.UBOBU.AIA
EZNGAIETAR
ORIOATZULI
TURN.NNNNN
O.ZZCZZ.IU
ELEGATEL.O
1

careu.out

8
AABAA
AOQOA
DDDDD
EOTOE
EZNZE
NNNNN
UBOBU
ZZCZZ

Explicație

Cerința 1. Au fost determinate 8 cuvinte speciale

Exemplul 3:

careu.in

10
VERDE.CRIN
DANA.DDDDD
VOI.AOQOA.
NU.AAOTE..
.UBOBU.AIA
EZNGAIETAR
ORIOATZULI
TURN.NNNNN
O.ZZCZZ.IU
ELEGATEL.O
2

careu.out

832

Explicație

Cerința 2. Punctajul maxim pentru cele 8 cuvinte speciale este 832.

Gigel a inventat un nou joc, de această dată utilizând un rebus sub forma de tablă pătratică cu n x n căsuțe. Fiecare căsuță conține câte o literă mare din alfabetul englez sau caracterul '.'. Literele formează pe orizontală sau pe verticală cuvinte delimitate prin caractere punct sau prin marginile tablei. Cel care joacă trebuie să determine cuvintele speciale din careu. Punctajul unui cuvânt se calculează ca suma codurilor ASCII ale literelor distincte care apar în acel cuvânt. Punctajul total al jocului se calculează însumând punctajele literelor distincte ale cuvintelor speciale distincte. Un cuvânt special îndeplinește simultan condițiile:

• este palindrom
• are lungime maximă relativ la alte cuvinte palindrom

Cerința

Să se scrie un program care sa determine, pentru un careu dat, punctajul maxim și cuvintele care permit obținerea punctajului maxim. Dacă nu există astfel de cuvinte se va afișa valoarea 0.

Date de intrare

Fișierul de intrare careu.in conține pe prima linie un număr natural n reprezentând dimensiunea careului. Următoarele n linii conțin fiecare câte n caractere, neseparate prin spații, reprezentând careul. Ultima linie a fișierului de intrare conține una dintre valorile 1 sau 2 reprezentând cerința.

Date de ieșire

Fișierul de ieșire careu.out conține pentru cerința 1, pe prima linie numărul de cuvinte speciale de valoare maximă găsite, iar pe următoarele linii se vor scrie aceste cuvinte în ordine alfabetică, câte unul pe linie; pentru cerința 2, pe prima linie a fișierului de ieșire se va scrie punctajul maxim determinat.

Restricții și precizări

• 2 <= n <= 50
• Cuvintele sunt scrise cu litere mari și lungimea cuvintelor din soluție trebuie să fie cel puțin 2.
• Pentru cerința 1 se acordă 60% din punctaj, iar pentru cerința 2 se acordă 30% din punctaj
• În concurs s-au acordat 10 puncte din oficiu; aici se acordă 10 puncte pentru cele trei exemple.

Exemplul 1:

careu.in

3
A.A
B.A
..C
1

careu.out

0

Explicație

Nu există nici un cuvânt special de lungime mai mare sau egală cu 2.

Exemplul 2:

careu.in

10
VERDE.CRIN
DANA.DDDDD
VOI.AOQOA.
NU.AAOTE..
.UBOBU.AIA
EZNGAIETAR
ORIOATZULI
TURN.NNNNN
O.ZZCZZ.IU
ELEGATEL.O
1

careu.out

8
AABAA
AOQOA
DDDDD
EOTOE
EZNZE
NNNNN
UBOBU
ZZCZZ

Explicație

Cerința 1. Au fost determinate 8 cuvinte speciale

Exemplul 3:

careu.in

10
VERDE.CRIN
DANA.DDDDD
VOI.AOQOA.
NU.AAOTE..
.UBOBU.AIA
EZNGAIETAR
ORIOATZULI
TURN.NNNNN
O.ZZCZZ.IU
ELEGATEL.O
2

careu.out

832

Explicație

Cerința 2. Punctajul maxim pentru cele 8 cuvinte speciale este 832.
832 = 65+66+67+68+69+78+79+81+84+85+90
A B C D E N O Q T U Z

#include <bits/stdc++.h>

using namespace std;
ifstream cin("careu.in");
ofstream cout("careu.out");
int pal(char a[256] , int x , int y)
{
    for(int i = x , j = y; i < j ; i++ , j--)
        if(a[i] != a[j]) return 0;
    return 1;
}
void ordonare(char a[][100] , int n)
{
    for(int i = 1 ; i <= n ; i++)
        for(int j = i + 1 ; j <=n ; j++)
            if(strcmp(a[i] , a[j]) > 0)
            {
                char aux[201];
                strcpy(aux , a[i]);
                strcpy(a[i] , a[j]);
                strcpy(a[j] , aux);
            }
}
int main()
{
    int n , cer , cnt = 0 , lmax = 0;
    cin >> n;
    char s[55][100] , b[10000][100] = {};
    for(int i = 0 ; i < n ; i++)
        cin >> s[i];
    cin >> cer;
        for(int i = 0 ; i < n ; i++)
        {
            int l = 0;
            for(int j = 0 ; j < n ; j++)
            {
                if(s[i][j] != '.') l++;
                else
                {
                    if(pal(s[i] , j - l , j - 1) && l >= 2)
                    {
                        if(l > lmax)
                        {
                            lmax = l;
                            cnt = 0;
                            strncpy(b[++cnt] , s[i] + j - l , l);
                        }
                        else if(l == lmax)
                        {
                            strncpy(b[++cnt] , s[i] + j - l , l);
                        }
                    }
                    l = 0;
                }
            }
            if(pal(s[i] , n - l , n - 1) && l >= 2)
            {
                if(l > lmax)
                    {
                        lmax = l;
                        cnt = 0;
                        strncpy(b[++cnt] , s[i] + n - l , l);
                    }
                else if(l == lmax)
                {
                        strncpy(b[++cnt] , s[i] + n - l , l);
                }
            }
        }
        for(int i =  0 ; i < n ; i++)
            for(int j = 0 ; j < i ; j++)
                swap(s[i][j] , s[j][i]);
        for(int i = 0 ; i < n ; i++)
        {
            int l = 0;
            for(int j = 0 ; j < n ; j++)
            {
                if(s[i][j] != '.') l++;
                else
                {
                    if(pal(s[i] , j - l , j - 1) && l >= 2)
                    {
                        if(l > lmax)
                        {
                            lmax = l;
                            cnt = 0;
                            strncpy(b[++cnt] , s[i] + j - l , l);
                        }
                        else if(l == lmax)
                        {
                            strncpy(b[++cnt] , s[i] + j - l , l);
                        }
                    }
                    l = 0;
                }
            }
            if(pal(s[i] , n - l , n - 1) && l >= 2)
            {
                if(l > lmax)
                    {
                        lmax = l;
                        cnt = 0;
                        strncpy(b[++cnt] , s[i] + n - l , l);
                    }
                else if(l == lmax)
                {
                        strncpy(b[++cnt] , s[i] + n - l , l);
                }
            }
        }
        if(cer == 1)
        {
            ordonare(b , cnt);
            int ok = 0;
            for(int i = 1 ; i <= cnt ; i++)
                if(strcmp(b[i] , b[i-1]) == 0)ok++;
            cout << cnt-ok << '\n';
            for(int i = 1 ; i <= cnt ; i++)
                if(strcmp(b[i] , b[i-1]) != 0)cout << b[i] << '\n';
        }
        else
        {
            int f[1000] = {0};
            for(int i = 1 ; i <= cnt ; i++)
            {
                int m = strlen(b[i]);
                for(int j = 0 ; j < m ; j++)
                    f[(int)b[i][j]]++;
            }
            long long s = 0;
            for(int i = 50 ; i <= 256 ; i++)
            {
                if(f[i] != 0) s+=i;
            }
            cout << s;
        }
}