Fișierul intrare/ieșire virus1.in, virus1.out Sursă ONSEPI 2021 clasa a 7-a
Autor Adrian Pintea Adăugată de avatar mircea_007 Mircea Rebengiuc mircea_007
Timp de execuție pe test 0.3 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Virus1 (clasa a 7-a)

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ță

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 virus1.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 virus1.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 si Precizări

  • 2 ≤ N ≤ 50000
  • Lungimea maximă a codului unui virus este 200
  • Daca a și b sunt două șiruri de lungime lg, spunem că șirul a = a0a1a2a{l[g]−1} este mai mic din punct de vedere lexicografic decât șirul b = b0b1b2b{l[g]−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.
  • Pentru teste valorând 31 de puncte: C = 1
  • Pentru alte teste valorând 16 de puncte: C = 2, N ≤ 500 și lungimea maxima a codului unui virus este 40.
  • Pentru alte teste valorând 53 de puncte: C = 2 și nu există restricții suplimentare.

Exemplu

virus1.in virus1.out
1
abac
5
Abbbq
Zbac
abbC
aBac
Zbac
3
2
abcD
8
abcdD
XbcD
Xc
XbcD
aXcD
aXcD
aXc
ab
XbcD

Explicație

Pentru exemplul 1 mutațiile sunt Zbac, aBac și Zbac.
Pentru exemplul 2 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’

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 5 categorii