virus

Time limit: 0.1s Memory limit: 8MB Input: virus.in Output: virus.out

Există azi mulţi viruşi care acţionează în diferite moduri asupra informaţiei stocate într-un calculator. Printre aceştia există şi unii mai puţin periculoşi, care se mulţumesc doar să simuleze o anumită alterare a informaţiei. Să presupunem că dorim să scriem un astfel de virus care acţionează doar asupra informaţiei de tip text de pe ecranul calculatorului. În mod text, ecranul este constituit din nn linii pe fiecare aflându-se câte mm caractere. Caracterele sunt reţinute în memoria calculatorului prin codul lor ASCII, reprezentat în binar pe 88 biţi. Biţii sunt numerotaţi de la 00 la 77 de la dreapta către stânga, cel din stânga fiind cel mai semnificativ bit.

La fiecare secundă, virusul transformă simultan toate caracterele de pe ecran după următoarele reguli:

  1. virusul afectează doar caracterele ale căror coduri nu are toți biții egali cu 00; caracterul al cărui cod are toţi biţii egali cu 00 se numește inatacabil;
  2. se determină caracterele ale căror coduri au număr maxim de biți egali cu 11; pentru fiecare astfel de caracter cei mai semnificativi 22 biţi egali cu 11 din cod se transformă în 00, iar dacă nu are în cod 22 biţi egali cu 11, se va transforma în 00 singurul bit 11 existent;
  3. pentru toate celelalte caractere atacabile, bitul cel mai puţin semnificativ egal cu 00 al codului se transformă în 11;
  4. unele caractere pot genera erori în execuţia virusului deoarece transformând succesiv codurile lor se pot obţine cicluri; aceste caractere au codurile ASCII 11, 33, 77, 1515, 3131, 6363, 127127 şi virusul le transformă imediat în 00 (adică devin inatacabile), indiferent când un astfel de caracter apare (adică dacă el există iniţial pe ecran sau apare după o transformare).

Cerinţă

Cunoscând configuraţia iniţială a ecranului, scrieţi un program care să rezolve următoarele două cerinţe:

  1. determină numărul de caractere inatacabile obţinute în prima secundă (adică după prima transformare);
  2. determină după câte secunde toate caracterele de pe ecran sunt inatacabile.

Date de intrare

Fișierul de intrare virus.in conţine pe prima linie două numere naturale separate printr-un spațiu nn, mm, reprezentând dimensiunile ecranului. Pe fiecare dintre următoarele nn linii se află câte mm caractere, reprezentând caracterele existente iniţial pe ecran. Ultima linie a fișierului de intrare conține cerinţa care trebuie să fie rezolvată (11 sau 22).

Date de ieșire

Fișierul de ieșire virus.out va conține o singură linie pe care va fi scris un număr natural, reprezentând răspunsul la cerinţa specificată în fişierul de intrare.

Restricții și precizări

  • 1n,m1001 \leq n, m \leq 100
  • Caracterele aflate inițial pe ecran au coduri cuprinse între 3232 şi 127127.
  • Pentru teste valorând 3030 de puncte, cerința este 11.

Exemplul 1

virus.in

2 2
AA
AA
1

virus.out

4

Explicație

Caracterul AA are codul 0100000101000001, deci numărul maxim de biți egali cu 11 este 22 (egal pentru toate caracterele); după o secundă toate cele 44 caractere vor avea codul 0000000000000000 (deci devin inatacabile).

Exemplul 2

virus.in

3 3
AAC
AAC
CCC
2

virus.out

2

Explicație

În prima secundă:

  • numărul maxim de biți egali cu 11 în codurile caracterelor este 33 (CC având codul 0100001101000011); după eliminarea celor mai semnificativi doi biți 11 codul lui CC devine 0000000100000001, deci devine un caracter care generează erori şi virusul îl transformă imediat în 0000000000000000 (inatacabil);
  • celelalte caractere AA (cu codul 0100000101000001) devin CC (codul 0100001101000011).

În a doua secundă numărul maxim de biți egali cu 11 este 33, se elimină cei mai semnificativi doi biți 11, codul devine 0000000100000001 rezultă un caracter care generează erori, deci virusul îl transformă în inatacabil. Astfel, după două secunde toate caracterele sunt inatacabile.

Log in or sign up to be able to send submissions!