bratara

Bratara

== include(page="template/taskheader" task_id="bratara") ==
Deorece se apropie 1 martie, Iulia pregăteşte nişte brăţări mai deosebite pentru prietenele ei pasionate de matematică. Acestea trebuie să îndeplinească următoarele reguli:

- Sunt secvenţe formate din minim două  numere naturale.
- Oricare două numere, a şi b, aflate pe poziţii alăturate vor respecta condiţia: cifra zecilor lui a coincide cu cea mai semnificativă (prima din dreapta) cifră a lui b şi  cifra unitaţilor lui a este identică cu a doua cifră semnificativă (a 2-a din dreapta) a lui b. În plus, dacă aceleaşi condiţii sunt respectate şi de ultimul şi primul termen din secvenţă, atunci brăţara este norocoasă.

- Sunt secvenţe formate din minim două numere naturale.
- Oricare două numere, $a$ şi $b$, aflate pe poziţii alăturate vor respecta condiţia: cifra zecilor lui $a$ coincide cu cea mai semnificativă (prima din dreapta) cifră a lui $b$ şi cifra unitaţilor lui $a$ este identică cu a doua cifră semnificativă (a 2-a din dreapta) a lui $b$. În plus, dacă aceleaşi condiţii sunt respectate şi de ultimul şi primul termen din secvenţă, atunci brăţara este norocoasă.

- Toate numerele incep cu o cifră diferită de 0.

- Un exemplu de astfel de brăţară este: 1234     34551    517890   9001.
Secvenţa 17235    3524    24758   58117  este o brăţară norocoasă.
Următorul şir nu este o brăţară:  1234   3112   12567   5642 deorece 1234 si 3112 nu corespund cerinţei de alăturare.

- Un exemplu de astfel de brăţară este: $1234$ $34551$ $517890$ $9001$.
Secvenţa $17235$ $3524$ $24758$ $58117$ este o brăţară norocoasă.
Următorul şir nu este o brăţară: $1234$ $3112$ $12567$ $5642$ deorece $1234$ si $3112$ nu corespund cerinţei de alăturare.

h2. Cerinţă

Avănd un şir cu n numere naturale,  Iulia vrea să ştie:

Avănd un şir cu $n$ numere naturale, Iulia vrea să ştie:

1.  câte brăţări poate forma doar cu numere aflate pe poziţii consecutive în şir care respectă regulile formulate anterior şi care nu mai pot fi extinse ca lungime

2.  care este cea mai lungă brăţară norocoasă;  dacă există mai multe brăţări norocoase de lungime maximă se va reţine cea mai din stânga şirului.

2.  care este cea mai lungă brăţară norocoasă; dacă există mai multe brăţări norocoase de lungime maximă se va reţine cea mai din stânga şirului.

h2. Date de intrare

În fişierul $bratara.in$ :
- pe prima linie se află o valoare C care poate fi 1 sau  2. Dacă C = 1, se rezolvă cerinţa 1, pentru C = 2, cerinţa 2.
- pe a doua linie este n – numărul de termeni din şirul Iuliei
- pe a treia linie se găsesc cele n numere naturale ale şirului, separate prin câte un spaţiu.

În fişierul $bratara.in$:
- pe prima linie se află o valoare $C$ care poate fi 1 sau 2. Dacă $C$ = 1, se rezolvă cerinţa 1, pentru $C$ = 2, cerinţa 2.
- pe a doua linie este $n$ – numărul de termeni din şirul Iuliei
- pe a treia linie se găsesc cele $n$ numere naturale ale şirului, separate prin câte un spaţiu.

h2. Date de ieşire
În fişierul $bratara.out$ se vor afişa:

- un număr natural, reprezentând numărul de brăţări descoperite în şir, dacă C este 1
- trei numere naturale k, s, d, separate printr-un spaţiu, cu semnificaţia: k= numărul maxim de valori cuprinse  într-o brăţară norocoasă, s şi d capătul (indicele) din stânga şi cel din dreapta al brăţării solicitate, dacă C este 2; dacă în şir nu există brăţări norocoase, se va afişa -1.

- un număr natural, reprezentând numărul de brăţări descoperite în şir, dacă $C$ este 1
- trei numere naturale $k$, $s$, $d$, separate printr-un spaţiu, cu semnificaţia: $k$ = numărul maxim de valori cuprinse  într-o brăţară norocoasă, $s$ şi $d$ capătul (indicele) din stânga şi cel din dreapta al brăţării solicitate, dacă $C$ este 2;
- dacă în şir nu există brăţări norocoase, se va afişa -1

h2. Restricţii

* 2 <= n <= 100.000
* Numerele din şir au minim 4  şi maxim 9 cifre fiecare

* 2 <= $n$ <= 100.000
* Numerele din şir au minim 4 şi maxim 9 cifre fiecare

h2. Exemplu

table(example). |_. bratara.in |_. bratara.out |

table(example). |_. bratara.in |_. bratara.out |_. Explicatii |

| 1

7
1232 32112 17235 3524  24758 51117  12234
 | 2
|
 
h3. Explicaţie
 
Cele două brăţări găsite sunt:
1232    32112
17235 3524  24758

  7
  1232 32112 17235 3524  24758 51117  12234
| 2
| Cele două brăţări găsite sunt:
  1232    32112
  17235 3524  24758
|
| 2
  7
  1232 32117 17235 3524  24721   21117  1721
| 4 3 6
| Se observă că avem o singură brăţară simplă formată din toate elementele şirului.
  Dar brăţari norocoase sunt:
  {*17*}235   3524    247{+21+}    {+21+}1{*17*}  şi
  {*21*}117  17{*21*}
Cea mai lungă brăţară este prima, este formată din 4 numere, are 3 ca pozitie de început şi 6 ca poziţie finală în şirul dat
|
 

== include(page="template/taskfooter" task_id="bratara") ==