Rezolvare completă PbInfo #1122 Babilon

Babilonienii au dezvoltat  un sistem pozițional de scriere a numerelor, în care orice număr natural se poate reprezenta utilizând semnele (unu), (zece) şi spaţii.

Valorile k din {2, 3, … , 9} se obțin scriind semnul de k ori (scrierea babiloniană a lui 3 este ). 

Numerele 11, 12, … , 59 se obțin ca succesiuni de semne urmate de semne (43 se reprezintă ca
).

Sistemul folosește gruparea unităților câte șaizeci. Astfel, pentru a scrie umărul șaizeci se folosește același semn ca pentru unu, dar valoarea sa este dată de poziția în care se găsește semnul .

Babilonienii nu foloseau cifra 0. Pentru poziţionarea corectă a semnelor se utiliza spațiu (60 se reprezintă ca , 3600 se reprezintă ca etc.).

Se codifică scrierea babiloniană a unui număr utilizând cifra 1 în locul semnului , cifra 2 în locul semnului și cifra 3 în loc de spațiu, ca în exemplele de mai jos:

Scrierea babiloniană
Codificarea scrierii babiloniene 1311 12 1221111 123111
Valoarea zecimală a numărului 1*60+2=62 1*60+10=70 1*60+20+4=84 1*60*60+10*60+3=4203

Cerință

Dându-se un număr natural n și un șir de n cifre din mulțimea {1, 2, 3}, reprezentând codificarea scrierii babiloniene a unui număr natural, să se determine:
a) numărul maxim de cifre 1 aflate pe poziții consecutive în codificarea scrierii babiloniene date;
b) numărul natural din sistemul zecimal corespunzător scrierii babiloniene date.

Date de intrare

Fișierul de intrare babilon.in conține:

  • pe prima linie un număr natural p ( 1 ≤ p ≤ 2 );
  • pe a doua linie un număr natural n;
  • pe a treia linie n cifre separate prin câte un spațiu, reprezentând codificarea scrierii babiloniene a unui număr natural.

Date de ieșire

Dacă valoarea lui p este 1, atunci se va rezolva numai punctul a) din cerință. În acest caz, fişierul de ieşire babilon.out va conţine pe prima linie un număr natural reprezentând numărul maxim de cifre 1 aflate pe poziții consecutive în codificarea scrierii babiloniene date.

Dacă valoarea lui p este 2, atunci se va rezolva numai punctul b) din cerință. În acest caz, fişierul de ieşire babilon.out va conţine pe prima linie numărul natural corespunzător scrierii babiloniene date.

Restricții și precizări

  • 2 ≤ n ≤ 109;
  • se garantează faptul că numărul de cifre al rezultatului de la punctul b) (numărul zecimal) este mai mic decât 20;
  • 30% din teste vor avea pe prima linie valoarea 1, iar restul de 70% din teste vor avea pe prima linie valoarea 2.

Exemplul 1

babilon.in

1
8
1 1 3 2 1 1 1 2

babilon.out

3

Explicație

1 1 3 2 1 1 1 2. Cea mai lungă secvență de cifre 1 are lungimea 3.

Exemplul 2

babilon.in

2
7
1 1 3 2 1 1 1

babilon.out

7213

Explicație


2 se înmulțește de două ori cu 60 (o dată pentru că este urmat de spațiu și încă o dată pentru că precede o grupă care începe cu semnul ), apoi se adună valoarea 13.

2*60*60+10+3=7213

Exemplul 3

babilon.in

2
9
1 1 1 2 1 1 2 2 1

babilon.out

11541

Explicație


3 se înmulțește cu 60 de două ori pentru că este precedat de două grupe care încep cu semnul , apoi se adună 12 înmulţit cu 60 şi la final se adună 21.

3*60*60+12*60+21=11541

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Babilon:

//Florentina Ungureanu - Colegiul National de Informatica Piatra-Neamt
#include <fstream>
#include <iostream>
#include <string.h>
using namespace std;
unsigned n, v, a, b, c;

ifstream f("babilon.in");
ofstream g("babilon.out");
int main()
{
    long long z=0;
    unsigned i, fr, fmax;
    f>>v>>n;
    if(v==1)
    {
        f>>a;
        fmax=fr=a==1;
        for(i=2;i<=n;i++)
        {
            f>>b;
            if(a*b==1) fr++;
              else  {
                        if (fr>fmax) fmax=fr;
                        fr=b==1;
                    }
            a=b;
        }
      if (fr>fmax) fmax=fr;
      g<<fmax<<'\n';
    }
    else
    { f>>a;
      if(a==1)z=1;
          else if(a==2)z=10;
                else z=0;
      for(i=2;i<=n;i++)
        {
            f>>b;
            if (b>a) z=z*60;
            if(b==1)z++;
                else if(b==2)z+=10;
            if (b!=3)   a=b;
        }
      g<<z<<'\n';
    }
    f.close();
    g.close();
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1122 Babilon

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1122 Babilon de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!