# PBinfo #3765 – virus1 – Rezolvare C++

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

## Enunț

Un laborator specializat studiază mutațiile unui virus pandemic pentru a găsi cel mai bun vaccin pentru combaterea acestuia. Codul unui virus este un șir format din litere (mari și mici) ale alfabetului englez. Numim mutație a virusului pandemic un șir de caractere care are aceeași lungime cu codul virusului și care conține o singură poziție pentru care litera din șir este diferită de litera situată pe poziția respectivă în codul virusului pandemic. De exemplu, pentru virusul pandemic având codul abac, șirul Bbac reprezintă o mutație, deoarece are aceeași lungime și diferă doar prin litera de pe prima poziție. Laboratorul primește o listă conținând codurilor mai multor viruși descoperiți în urma testărilor.

Cerința
Scrieți un program care, cunoscând codul virusului pandemic și lista codurilor virușilor descoperiți în urma testărilor, rezolvă următoarele cerințe:

1. Determină numărul de mutații ale virusului pandemic existente în listă, mutații nu neapărat distincte;
2. Determină mutația cu număr maxim de apariții în listă; dacă există mai multe mutații cu același număr maxim de apariții, se va determina prima mutație, în ordine lexicografică.

Date de intrare
Fișierul de intrare virus.in conține pe prima linie un număr natural C reprezentând cerința care trebuie să fie rezolvată (1 sau 2). Pe cea de a doua linie se află codul virusului pandemic. Pe a treia linie se află un număr natural N, reprezentând numărul de viruși existenți în lista primită de laborator. Pe următoarele N linii se află codurile virușilor din listă, câte un cod pe o linie.

Date de ieșire
Fișierul de ieșire virus.out va conține o singură linie:


Dacă C = 1, pe prima linie va fi scris un număr natural care reprezintă câte elemente din listă sunt mutații ale virusului pandemic.
Dacă C = 2, pe prima linie va fi scris un șir de caractere care reprezintă mutația cu număr maxim de apariții. Dacă există mai multe mutații cu număr maxim de apariții, va fi afișată prima (cea mai mică), în ordine lexicografică.

Restricții și precizări

2 ≤ N ≤ 50.000
Lungimea maximă a codului unui virus este 200
Daca a și b sunt două șiruri de lungime lg, spunem că șirul a = a0 a1 a2 ... alg-1 este mai mic din punct de vedere lexicografic decât șirul b = b0 b1 b2 ... blg-1, dacă există o poziție k ∈{0, 1, ...,  lg - 1} astfel încât ai = bi pentru orice 0 ≤ i < k și ak < bk.
În codul ASCII codurile literelor mari sunt mai mici decât codurile literelor mici.

Exemplul 1:
virus.in

1
abac
5
Abbbq
Zbac
abbC
aBac
Zbac
virus.out

3
Explicație
Mutațiile sunt Zbac, aBac și Zbac.

Exemplul 2:
virus.in

2
abcD
8
abcdD
XbcD
Xc
XbcD
aXcD
aXcD
aXc
ab
virus.out

XbcD
Explicație
Mutațiile XbcD și aXcD apar fiecare de câte 2 ori, prima în ordine lexicografică fiind XbcD. XbcD este mai mic lexicografic decât aXcD, deoarece în codul ASCII: 'A' < 'B' < ... < 'Z' < 'a' < 'b' < ... < 'z'

## Cod sursă C++

```cpp
#include <fstream>
#include <cstring>
#define LGMAX 202
#define CMAX 100002
using namespace std;
ifstream fin("virus.in");
ofstream fout("virus.out");
int n, rez, P, lgv, lgc;
int nr[CMAX];
char v[LGMAX], c[LGMAX], cmaxim[LGMAX];
void mutatie (int & poz, int& litera);
void codul(int x,char s[LGMAX]);
int main()
{int i, litera, poz, maxim;
 fin>>P>>v>>n;
 lgv=strlen(v);
 for (i=1; i<=n; i++)
     {fin>>c; lgc=strlen(c);
      mutatie(poz, litera);
      if (poz!=-1)
         {
          rez++;
          nr[poz*100+litera]++;
         }
     }
if (P==1)
   fout<<rez<<'\n';
   else
   {
    maxim=0;
    for (i=0; i<CMAX; i++)
        if (nr[i]>maxim)
            maxim=nr[i];
    cmaxim[0]='z'+1;
    for (i=0; i<CMAX; i++)
        if (nr[i]==maxim)
               {
                codul(i,c);
                if (strcmp(c,cmaxim)<0) strcpy(cmaxim,c);
               }
    fout<<cmaxim<<'\n';
   }
return 0;
}
void mutatie (int & poz, int &litera)
{int i;
 poz=-1;
 if (lgv!=lgc) return;
 for (i=0; i<lgv; i++)
      if (v[i]!=c[i])
         if (poz==-1) poz=i;
            else {poz=-1; return; }
 if (poz==-1) return;
 if (c[poz]>='A' && c[poz]<='Z') litera=c[poz]-'A';
    else litera=c[poz]-'a'+26;
}
void codul(int x,char s[LGMAX])
{int poz; char litera;
 strcpy(s,v);
 poz=x/100;
 if (x%100<26) litera='A'+x%100;
    else litera='a'+(x%100-26);
 s[poz]=litera;
}
```

## Resurse

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