Solution of 2AM Rule

De departe aceasta problema a creat cele mai multe probleme probleme participantilor desi este o problema simpla de procesare de siruri de caractere, aceasta putand fi rezolvata folosind expresii regulate(regex). Desi mai greu de implementat, o sursa fara regex putea fi scrisa in circa 20 de minute. Pentru elevii de gimnaziu, scrierea aceastei solutii este o foarte buna pregatire pentru ONI.

O greseala pe care au facut-o multi participanti a fost citirea incorecta. Regulamentul olimpiadei spune ca fisierele se termine cu un caracter newline, lucru pe care multi participanti nu l-au luat in considerare, tratand si ultima "linie" (goala) ca o expresie.

Intrucat operatorii + si - sunt echivalenti, incepem prin a inlocui + cu - (1). Apoi verificam daca sirul incepe cu -, se termina cu -, sau contine subsirurile [- sau -], caz in care returnam ERROR (2). Continuam prin inlocuirea subsirurilor de forma [ceva] cu +ceva (3).

Acum avem o expresie delimitata de caracterul -. Consideram separat fiecare token (4):

  • Daca e egal cu bx sau bp (case-insensitive), incrementam numarul de base registers (5)
  • Daca e egal cu si sau di (case-insensitive), incrementam numarul de index registers (6)
  • Daca e egal cu o litera lowercase, incrementam numarul de variabile (7)
  • Daca e numar, trecem mai departe (8)
  • Daca nu e niciuna din cele de mai sus, returnam ERROR (9)
In final, returnam OK daca si numai daca numerele de base registers, de index registers si de variabile sunt toate mai mici decat 2. (10)

Sursa oficiala:

    1 #!/usr/bin/perl -w
    2 use v5.14;
    3 no if $] >= 5.017011, warnings => 'experimental::smartmatch';
    4 
    5 sub ok{
    6     chomp;                                  # Remove the final newline
    7     y/+/-/;                                 # (1) Replace + with -
    8     return if /^-|-$|\[-|-\]/;              # (2) ERROR if the string starts/ends with a - or if it contains [- or -]
    9     1 while s/\[([^[\]]+)]/-$1/;            # (3) Replace [...] with -...
   10     my ($base, $index, $vars) = (0, 0, 0);
   11     for (split '-'){                        # (4) Tokenize the expression, using '-' as the delimiter
   12         $base++ when m/^bx$|^bp$/i;         # (5) If the current token is bx or bp, increment $base
   13         $index++ when m/^si$|^di$/i;        # (6) If the current token is si or di, increment $index
   14         $vars++ when m/^[a-z]$/;            # (7) If the current token is a lowercase letter, increment $vars
   15         1 when m/^\d*$/i;                   # (8) If the current token is a number, do nothing
   16         default { return }                  # (9) Otherwise ERROR
   17     }
   18 
   19     $base < 2 && $index < 2 && $vars < 2    # (10)
   20 }
   21 
   22 say ok() ? 'OK' : 'ERROR' while <>;
Questions?

Sponsors Gold