Fişierul intrare/ieşire:colier1.in, colier1.outSursăOJI 2016 clasa a 5-a
AutorMarius NicoliAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.5 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Colier 1 (clasa a 5-a)

Maria are în camera sa N mărgele aşezate una lângă alta. Pe fiecare dintre ele este scris un număr natural format din cifre nenule distincte. Pentru fiecare mărgea, Maria şterge numărul şi în locul său scrie altul, având doar două cifre, respectiv cifra minimă şi cifra maximă din numărul scris iniţial, în ordinea în care aceste cifre apăreau înainte de ştergere. Acum Maria consideră că mărgelele sunt de două tipuri, în funcţie de numărul de două cifre scris pe ele: tipul 1 (cele care au cifra zecilor mai mică decât cifra unităţilor) şi tipul 2 (celelalte). Folosind mărgelele, fetiţa doreşte ca prin eliminarea unora dintre ele (dar fără să le schimbe ordinea celorlalte) să obţină un colier circular cât mai lung care să respecte proprietatea că oricare două mărgele vecine ale sale sunt de tipuri diferite. În colierul format cu mărgelele rămase după eliminare se consideră că prima mărgea este vecină cu ultima.

Cerinţe

  1. Determinaţi numărul de mărgele de tipul 1.
  2. Determinaţi numărul maxim de mărgele pe care le poate avea colierul.

Date de intrare

Fişierul de intrare colier1.in conţine pe prima linie un număr natural T. Pe linia a doua se găseşte un număr natural N. Pe linia a treia sunt N numere naturale ce reprezintă, în ordine, valorile scrise iniţial pe mărgele. Aceste numere sunt separate prin câte un spaţiu.

Date de ieşire

Dacă valoarea lui T este 1, se va rezolva numai punctul (1) din cerinţe. În acest caz, fişierul de ieşire colier1.out va conţine pe prima linie un număr natural reprezentând răspunsul la cerinţa (1).

Dacă valoarea lui T este 2, se va rezolva numai punctul (2) din cerinţe. În acest caz, fişierul de ieşire colier1.out va conţine pe prima linie un număr natural reprezentând răspunsul la cerinţa (2).

Restricţii

  • 1 ≤ N ≤ 50 000;
  • Numerele scrise iniţial pe mărgele au cifrele distincte, nu conţin cifra 0 şi sunt cuprinse între 12 şi 987654321;
  • T va fi 1 sau 2;
  • Pentru obţinerea colierului, Maria poate decide să nu elimine nicio mărgea;
  • Colierul obţinut poate fi format şi dintr-o singură mărgea;
  • Pentru teste în valoare de 20 de puncte avem T = 1 şi toate numerele scrise iniţial pe mărgele au două cifre;
  • Pentru teste în valoare de 30 de puncte avem T = 1 şi dintre numerele scrise iniţial pe mărgele sunt şi unele cu mai mult de două cifre;
  • Pentru teste în valoare de 50 de puncte avem T = 2.

Exemple

colier1.incolier1.outExplicaţie
1
5
12 678 312 24 938
3
Numerele scrise de Maria pe mărgele vor fi,
în ordine: 12 68 31 24 93.
Trei dintre ele (12, 68 şi 24) sunt de tipul 1.
(T fiind 1 se rezolvă doar cerinţa 1)
2
5
12 678 312 24 938
4
Numerele scrise de Maria pe mărgele vor fi,
în ordine: 12 68 31 24 93.
Eliminând mărgeaua de pe poziţia 1 sau pe cea de pe poziţia 2
şi aşezându-le pe celelalte circular obţinem un colier
cu 4 mărgele în care oricare două vecine sunt de tipuri diferite.
(T fiind 2 se rezolvă doar cerinţa 2).
Maria este obligată să elimine una din cele două mărgele,
altfel ar exista mărgele vecine de acelaşi tip.
Trebuie sa te autentifici pentru a trimite solutii. Click aici