Alina este mare iubitoare de teatru. Directorul teatrului i-a oferit șansa să joace în mai multe spectacole, ca figurant, deocamdată. Costumiera de scenă a decis să-i dea C costume diferite dintre cele care sunt destinate acestei stagiuni. Alina va duce costumele acasă și le va ajusta ca să-i vină bine. Stagiunea durează Z zile consecutive și în fiecare zi se joacă câte o piesă. Aceeași piesă se va juca, desigur în una sau mai mai multe zile ale stagiunii. Fiecărei piese i se asociază un unic costum de figurant, deci pentru fiecare piesă în care joacă, Alina trebuie să îmbrace un singur costum, acela asociat piesei respective. Costumele de figuranți sunt identificate prin literele mari ale alfabetului englez: A, B, C, …, X, Y, Z. Alina are voie să-și aleagă cele C costume diferite.
Cerința
Cunoscând costumul asociat fiecărei zile a stagiunii, ajutați-o pe Alina să-și aleagă cele C costume diferite, în așa fel încât să poată juca într-un număr cât mai mare de piese consecutive.
Date de intrare
Fișierul de intrare teatru.in conține pe prima linie două numere naturale Z și C despărțite printr-un spațiu. Z este numărul de zile din stagiune iar C este numărul de costume diferite pe care Alina le poate primi. Pe linia a doua, se găsesc Z caractere, litere mari ale alfabetului englez. Caracterul al i-lea identifică costumul de figurant care trebuie îmbrăcat în spectacolul din ziua i.
Date de ieșire
Fișierul de ieșire teatru.out va conține pe prima linie un număr natural N, reprezentând numărul maxim de spectacole consecutive în care Alina poate juca. Pe linia a doua se scriu N caractere, fără spații între ele, corespunzătoare costumelor care vor fi îmbrăcate în cele N piese de teatru alese, în ordinea spectacolelor în care va juca. Dacă există mai multe soluții de lungime N atunci se afișează cea căreia îi corespunde o zi de început mai aproape de începutul stagiunii.
Restricții și precizări
1 <= Z <= 550001 <= C <= 26C <= Z- Pentru 20% dintre teste
Z <= 350
Exemplul 1
teatru.in
10 3 XKUFKFEGXG
teatru.out
5 KUFKF
Exemplul 2
teatru.in
15 4 IAJRAMRCZJJCDNS
teatru.out
6 AJRAMR
Exemplul 3
teatru.in
25 5 LDSDGIFAURLPTZLDLPNLEGFRN
teatru.out
8 LPTZLDLP
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Teatru:
#include <stdio.h>
char s[55001];
long imax, jmax, Lmax, n, k;
long f[91];
void Citeste();
void Afis();
void Calculeaza();
int main()
{
freopen("teatru.in", "r", stdin);
freopen("teatru.out", "w", stdout);
Citeste();
Calculeaza();
Afis();
return 0;
}
void Citeste()
{
scanf("%d%d", &n, &k);
scanf("%c", &s[0]); // citeste '\n'
for (long int i = 0; i < n; i++ )
scanf("%c", s + i);
}
void Afis()
{
printf("%d\n", Lmax);
for (long int i = imax; i <= jmax; i++ )
printf("%c", s[i]);
printf("\n");
}
void Calculeaza()
{
long int i = 0, j = 0, nr = 0;
f[s[0]]++; nr++;
do
{
while (nr <= k && j < n)
{
j++;
if ( j >= n ) break;
if (f[s[j]] == 0)
{
f[s[j]]++;
nr++;
}
else f[s[j]]++;
}
if (j - i > Lmax)
{
Lmax = j - i;
imax = i; jmax = j - 1;
}
while ( nr > k )
{
f[s[i]]--;
if ( f[s[i]] == 0 ) nr--;
i++;
}
} while (i < n && j < n);
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1989 Teatru
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1989 Teatru de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!