View source for 1215 - Mesaj

În țara lui Piticot cuvintele au doar două litere, prima fiind o majusculă (literă mare) iar a doua o minusculă (literă mică). Piticii ''Mi'' și ''Gi'' se distrează și își trimit mesaje ascunzând cuvintele în cadrul unor secvențe transmise sub forma unor șiruri de litere. Piticul ''Mi'' scrie și trimite un mesaj piticului ''Gi'' respectând următoarele reguli:

* un mesaj conține una sau mai multe secvențe;
* orice literă care apare în mesaj, de cel puțin două ori, pe poziții alăturate, este numită terminator;
* o secvență se  încheie când s-a întâlnit o succesiune de litere terminator;
* cuvântul este format din prima majusculă și ultima minusculă din secvență, fără a lua în seamă litera terminator a secvenței;
* o secvență ascunde un cuvânt dacă terminatorul său se repetă de exact două ori și dacă conține cel puțin o literă mare și o literă mică, ignorând terminatorul de secvență;
* costul unui cuvânt este egal cu numărul total de apariții al celor două litere din care este format, în cadrul secvenței în care a fost ascuns, luând în considerare inclusiv literele terminator.

De exemplu secvența  <code>s f u E e t R u E E</code> ascunde un cuvânt deoarece conține și majuscule și minuscule, iar litera terminator de secvență,  <code>E</code>, se repetă de exact două ori. Secvența ascunde cuvântul <code>Eu</code>, iar costul cuvântului este <code>5</code> (<code>3</code> litere <code>E</code> + <code>2</code> două litere <code>u</code>).

La primirea mesajului, piticul ''Gi'' determină, pentru fiecare majusculă, costul maxim al cuvintelor care încep cu aceasta.

= Cerinţe =
Scrieţi un program care determină:

1) numărul de secvențe trimise care nu ascund cuvinte;

2) cuvintele din mesaj, în ordinea în care au fost trimise de piticul ''Mi''; 

3) pentru fiecare majusculă, câte cuvinte care încep cu ea au costul maxim determinat de ''Gi''.

fi afișate în ordine de la <code>A</code> la <code>Z</code>, însă doar cele pentru care au existat în mesaj cuvinte care au început cu ele.

= Date de intrare =
Fișierul de intrare <code>mesaj.in</code> conţine pe prima linie un număr natural <code>P</code>. Pentru toate testele de intrare, numărul <code>P</code> poate avea numai una dintre valorile <code>1</code>, <code>2</code> sau <code>3</code>. Pe a doua linie a fișierului de intrare se găsește  numărul natural N reprezentând numărul de litere folosite de ''Mi'' pentru scrierea mesajului. Pe a treia linie se găsesc <code>N</code> litere mari și mici ale alfabetului englez, separate prin câte un spațiu, reprezentând literele mesajului, în ordinea în care au fost trimise.

= Date de ieșire =
Dacă valoarea lui <code>P</code> este <code>1</code>, se va rezolva numai punctul 1) din cerințe. În acest caz, fişierul de ieşire <code>mesaj.out</code> va conține pe prima linie un număr natural reprezentând răspunsul la cerinţa 1).

Dacă valoarea lui <code>P</code> este <code>2</code>, se va rezolva numai punctul 2) din cerințe. În acest caz, fişierul de ieşire <code>mesaj.out</code> va conține cuvintele din mesaj, fiecare cuvânt scris pe câte o linie, în ordinea în care au fost trimise.

Dacă valoarea lui <code>P</code> este <code>3</code>, se va rezolva numai punctul 3) din cerințe. În acest caz, fişierul de ieşire <code>mesaj.out</code> va conține pe fiecare linie câte o majusculă urmată de un număr natural nenul, separate printr-un spațiu. Majusculele vor fi afișate în ordine de la <code>A</code> la <code>Z</code>, însă doar cele pentru care au existat în mesaj cuvinte care au început cu ele.

= Restricții și precizări =

* <code>1 ≤ N ≤ 2000000</code>
* litera terminator a unei secvențe poate fi ori minusculă ori majusculă;
* ultimele litere din fișier sunt literele terminator ale ultimei secvențe din mesajul trimis; se garantează că în șirul de litere din fișierul de intrare se află ascuns cel puțin un cuvânt;
* majusculele alfabetului englez sunt <code>A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z</code>;
* pentru 50% din teste <code>N ≤ 1000000</code>
* Pentru rezolvarea cerinţei 1) se acordă 20 de puncte, pentru rezolvarea cerinţei 2) se acordă 40 de puncte, iar pentru rezolvarea cerinţei 3) se acordă 40 de puncte.

= Exemplul 1 =
<code>mesaj.in</code>
 1
 34
 w w w w e D o r F D o r r t R n e R e y y j j i M 

 o e i t t t j w w
<code>mesaj.out</code>
 4

=== Explicație ===
Textul conține șase secvențe:

# <code>w w w w</code>
# <code>e D o r F D o r r</code>
# <code>t R n e R e y y</code>
# <code>j j</code>
# <code>i M o e i t t t</code>
# <code>j w w</code>

Sunt <code>4</code> secvențe care nu ascund cuvinte:

* prima secvență și a patra deoarece conțin numai terminatorul;
* secvența a cincea nu se decodifică deoarece terminatorul se repetă de mai mult de două ori;
* secvența a șasea nu conține majuscule.

== Încărcare soluție ==

=== Lipește codul aici ===
<syntaxhighlight lang="python" line="1">
import string

in_file = open("mesaj.in", "r")
out_file = open("mesaj.out", "w")

maj_counts = [0] * 256
min_counts = [0] * 256
max_cost = [0] * 256
max_cost_counts = [0] * 256

P = int(in_file.readline())
N = int(in_file.readline())

num_secvente = 0
num_secvente_cu_cuvinte = 0

ch = '#'
count_ch = 1

maj_ch = '#'
min_ch = '#'

for i in range(N):
    peek_ch = in_file.read(1)
    if i == N - 1:
        peek_ch = '#'

    if ch == peek_ch:
        count_ch += 1
    else:
        if count_ch == 1:
            if P == 1 or P == 2 or P == 3:
                if ch.isupper() and maj_ch == '#':
                    maj_ch = ch
                if ch.islower():
                    min_ch = ch
            if P == 3:
                if ch.isupper():
                    maj_counts[ord(ch)] += 1
                if ch.islower():
                    min_counts[ord(ch)] += 1

        elif count_ch == 2:
            if P == 1:
                num_secvente += 1
                if maj_ch != '#' and min_ch != '#':
                    num_secvente_cu_cuvinte += 1
                maj_ch = min_ch = '#'
            elif P == 2:
                if maj_ch != '#' and min_ch != '#':
                    out_file.write(maj_ch + min_ch + '\n')
                maj_ch = min_ch = '#'
            elif P == 3:
                if ch.isupper():
                    maj_counts[ord(ch)] += 2
                if ch.islower():
                    min_counts[ord(ch)] += 2
                if maj_ch != '#' and min_ch != '#':
                    cost = maj_counts[ord(maj_ch)] + min_counts[ord(min_ch)]
                    if cost > max_cost[ord(maj_ch)]:
                        max_cost[ord(maj_ch)] = cost
                        max_cost_counts[ord(maj_ch)] = 1
                    elif cost == max_cost[ord(maj_ch)]:
                        max_cost_counts[ord(maj_ch)] += 1
                maj_ch = min_ch = '#'
                maj_counts = [0] * 256
                min_counts = [0] * 256

        else:
            if P == 1:
                num_secvente += 1
                maj_ch = min_ch = '#'
            elif P == 2:
                maj_ch = min_ch = '#'
            elif P == 3:
                maj_ch = min_ch = '#'
                maj_counts = [0] * 256
                min_counts = [0] * 256

        count_ch = 1
        ch = peek_ch

if P == 1:
    out_file.write(str(num_secvente - num_secvente_cu_cuvinte) + '\n')
elif P == 3:
    for ch in string.ascii_uppercase:
        if max_cost[ord(ch)]:
            out_file.write(ch + ' ' + str(max_cost_counts[ord(ch)]) + '\n')

in_file.close()
out_file.close()
</syntaxhighlight>