== include(page="template/taskheader" task_id="babilon") ==
Poveste și cerință...
Babilonienii au dezvoltat un sistem pozițional de scriere a numerelor, în care orice număr natural se poate reprezenta utilizând semnele !problema/babilon?babilon-1.gif! (unu), !problema/babilon?babilon-10.gif! (zece) și spații. Valorile k ∈ {2, 3, …, 9} se obțin scriind semnul !problema/babilon?babilon-1.gif! de k ori (scrierea babiloniană a lui 3 este {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!}). Numerele 11, 12, …, 59 se obțin ca succesiuni de semne !problema/babilon?babilon-10.gif! urmate de semne !problema/babilon?babilon-1.gif! (43 se reprezintă ca {!problema/babilon?babilon-10.gif!} {!problema/babilon?babilon-10.gif!} {!problema/babilon?babilon-10.gif!} {!problema/babilon?babilon-10.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!} ).
Acestea sînt caracterele babiloniene: !problema/babilon?babilon-1.gif! !problema/babilon?babilon-1.gif! !problema/babilon?babilon-10.gif!
Sistemul folosește gruparea unităților câte șaizeci. Astfel, pentru a scrie numă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 !problema/babilon?babilon-1.gif!. Babilonienii nu foloseau cifra 0. Pentru poziționarea corectă a semnelor se utiliza spațiu !problema/babilon?babilon-s.gif! (60 se reprezintă ca {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-s.gif!}, 3600 se reprezintă ca {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-s.gif!} {!problema/babilon?babilon-s.gif!}, etc).
Se codifică scrierea babiloniană a unui număr utilizând cifra 1 în locul semnului !problema/babilon?babilon-1.gif!, cifra 2 în locul semnului !problema/babilon?babilon-10.gif! și cifra 3 în loc de spațiu, ca în exemplele de mai jos:
table().
|_. Scrierea babiloniană |_. Codificarea scrierii babiloniene |_. Valoarea zecimală a numărului |
| {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-s.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!}
| 1311
| 1*60+2=62
|
| {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-10.gif!}
| 12
| 1*60+10=70
|
| {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-10.gif!} {!problema/babilon?babilon-10.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!}
| 1221111
| 1*60+20+4=84
|
| {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-10.gif!} {!problema/babilon?babilon-s.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!}
| 123111
| 1*60*60+10*60+3=4203
|
h2. Cerință
Dându-se un număr natural n și un șir de n cifre ∈ {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.
h2. Date de intrare
Fișierul de intrare $babilon.in$ ...
Fișierul de intrare $babilon.in$ va 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.
h2. Date de ieșire
În fișierul de ieșire $babilon.out$ ...
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.
h2. Restricții
* $... ≤ ... ≤ ...$
* $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.
h2. Exemplu
table(example).
|_. babilon.in |_. babilon.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. babilon.in |_. babilon.out |_. Explicații |
| 1
8
1 1 3 2 1 1 1 2
| 3
| 1 1 3 2 1 1 1 2
Cea mai lungă secvență de cifre 1 are lungimea 3.
|
| 2
7
1 1 3 2 1 1 1
| 7213
| {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-s.gif!} {!problema/babilon?babilon-10.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!}
2 10 + 3
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 !problema/babilon?babilon-10.gif!), apoi se adună valoarea 13
2*60*60+10+3=7213
|
| 2
9
1 1 1 2 1 1 2 2 1
| 11541
| {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-10.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-1.gif!} {!problema/babilon?babilon-10.gif!} {!problema/babilon?babilon-10.gif!} {!problema/babilon?babilon-1.gif!}
3 12 21
3 se înmulțește cu 60 de două ori pentru că este precedat de
două grupe care încep cu semnul !problema/babilon?babilon-10.gif!, apoi se adună 12 înmulțit cu 60
și la final se adună 21.
3*60*60+12*60+21=11541
|
== include(page="template/taskfooter" task_id="babilon") ==
