# PBinfo #4468 – teatru1 – Rezolvare C++

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

## Enunț

Marele dramaturg BONIFACCI a uimit lumea teatrului cu noua sa capodoperă, Dada?!. Pentru că teatrul modern este un pic minimalist, piesa are un singur actor. Pentru că teatrul modern este un pic absurd, Actul 1 constă doar din replica A, iar Actul 2 constă doar din replica D. După cum vedeți, în această piesă de teatru replica este descrisă printr-un singur caracter. Și, pentru că teatrul modern este un pic repetitiv, fiecare act K, începând cu al treilea inclusiv, este obținut prin concatenarea actelor K - 2 și K - 1, în această ordine. Piesa are N acte, numerotate începând de la 1 până la N, toate construite după această regulă. În cadrul fiecărui act, replicile sunt numerotate începând tot de la 1.

De exemplu, primele 7 acte sunt (vă rugăm să nu aplaudați până la final):

Actul	Textul
------------------
1	A
2	D
3	AD 
4	DAD 
5	ADDAD 
6	DADADDAD 
7	ADDADDADADDAD

Cerința
La repetiție, actorul și-a propus să recite, cu intonație, L replici alăturate din actul al N-lea, începând cu replica numărul P, până la replica cu numărul P+L-1. Determinați secvența de caractere rostite de actor la repetiție.

Date de intrare
Fișierul de intrare teatru.in conține pe prima linie trei numere naturale nenule N, P și L, separate între ele prin câte un spațiu, având semnificațiile de mai sus.

Date de ieșire
Fișierul de ieșire teatru.out va conține pe prima linie L caractere A sau D, reprezentând, în ordine, replicile spuse de actor la repetiție.

Restricții și precizări

Fie SN numărul de replici din actul al N-lea. Se garantează că SN ≤ 1018.
1 ≤ L ≤ 2.000.000
1 ≤ P ≤ SN − L + 1 (cu alte cuvinte, există L replici în actul N începând cu replica numărul P).
Pentru 7 puncte, N ≤ 35, L = 1
Pentru 13 puncte, N ≤ 35, L ≤ 200.000
Pentru 17 puncte, N ≤ 40, L ≤ 200.000
Pentru 19 puncte, N ≤ 46, L ≤ 200.000
Pentru 21 puncte, L ≤ 200.000
Pentru 23 puncte, nu există restricții suplimentare.

Exemplul 1:
teatru.in

7 3 9
teatru.out

DADDADADD
Explicație
Actul al șaptelea are textul complet ADDADDADADDAD. Trebuie afișate caracterele de pe pozițiile 3 - 11.

Exemplul 2:
teatru.in

12 80 8
teatru.out

ADDADADD

## Cod sursă C++

```cpp
#include <cstdio>
#define NRMAX 2000004
FILE *fin=fopen("teatru.in","r");
FILE *fout=fopen("teatru.out","w");
long long int N, P, L, nr;
struct segm {long long int st, dr, poz;
             segm * urm;
};
typedef segm * Lista;
long long int lg[3];
Lista f;
char sir[NRMAX];
int main()
{int ia, ib, ic, aux;
 long long int i, pas;
 Lista p, q;
 segm s;
 fscanf(fin,"%lld %lld %lld", &N, &P, &L);
 //fin>>N>>P>>L;
 //determin lungimile ultimelor 3 acte
 ia=2; ib=0; ic=1;
 lg[0]=lg[1]=1;
 for (i=3; i<=N; i++)
     {aux=ia; ia=ib; ib=ic; ic=aux; lg[ic]=lg[ia]+lg[ib];}
 //ic indica lungimea actului N, ib a actului N-1, iar ia a actului N-2
 f=new segm;
 f->st=P; f->dr=P+L-1; f->poz=N; f->urm=NULL;
 pas=N;
 while (pas>2)
       {//din ic generez segmente pentru ib / ia
        for (p=f; p; p=p->urm)
            if (p->poz==pas)
                {
                  //lg[ic]=lungimea pentru pas
                  if (p->dr<=lg[ia]) {p->poz-=2;}
                     else
                     if (p->st>lg[ia])
                        {p->poz--; p->st-=lg[ia]; p->dr-=lg[ia];}
                        else
                        {q=new segm;
                         q->st=1; q->dr=p->dr-lg[ia]; q->poz=p->poz-1;
                         p->dr=lg[ia]; p->poz-=2;
                         q->urm=p->urm;
                         p->urm=q;
                        }
                }
         /* for (it=f.begin(); it != f.end(); ++it)
               fout<<it->st<<' '<<it->dr<<' '<<it->poz<<'\n';
          fout<<'\n';*/
         //ma pregatesc pentru pasul urmator
         aux=ic; ic=ib; ib=ia; ia=aux;
         lg[ia]=lg[ic]-lg[ib];
         pas--;
       }
 nr=0;
 for (p=f; p; p=p->urm)
     if (p->poz==1)
         for (i=p->st; i<=p->dr; i++)
             sir[nr++]='A';
             else
             for (i=p->st; i<=p->dr; i++)
                 sir[nr++]='D';
sir[nr]=0;
fprintf(fout,"%s",sir);
fclose(fout);
return 0;
}
```

## Resurse

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