tralala

Time limit: 0.2s Memory limit: 32MB Input: tralala.in Output: tralala.out

Cerință

Gheorghe a început cursuri de pian și a învățat că poate crea o gamă alegând 77 note din setul de 1212 note pe care le are pianul. Acesta a primit ca temă pentru acasă de la profesorul lui Tiberiu, să compună o progresie. Pentru ca melodia să sune armonios, profesorul Tiberiu l-a invățat faptul că trebuie să folosească doar note dintr-o singură gamă. De asemenea, acesta i-a cerut ca melodia să fie cât mai lungă.

Notele sunt numerotate de la 11 la 1212 și pentru ca tema să fie cât mai simplă, Tiberiu i-a spus să pună notele din gama aleasă sub forma unei melodii care să aibă prima notă mai mică decât a doua și să nu fie 2 note egale alăturate. De exemplu, dacă se alege gama 11, 22, 33, 44, 77, 99, 1010, notele din acea gamă trebuie folosite pentru a crea acea secvență.(Un exemplu de melodie formată corect ar fi: 11, 22, 33, 44, 33, 22, 77, 99, 1010, și incorect ar fi: 22, 11, 33, 44, 33, 22, 77, 99, 1010 sau 11, 22, 22, 44, 33, 22, 77, 99, 1010).
Principalul scop al lui Gheorghe e să selecteze gama de 77 note astfel încât să creeze cea mai lungă melodie care să respecte aceste condiții și să prezinte această melodie.

Gheorghe se gândea profund la o shaorma în timpul cursului și nu a înțeles mare lucru. El a încercat să își facă tema, însă melodia suna mediocru. Ajutați-l pe Gheorghe să repare melodia selectând doar o gamă din ea și rearanjând notele gamei astfel încât Tiberiu să îl mai primească în continuare la cursuri. El trebuie să formeze cea mai lungă melodie care să respecte condițiile puse de Tiberiu.

Date de intrare

Pe prima linie a fișierului de intrare tralala.in se află numărul natural NN de note pe care le-a folosit inițial Gheorghe.
Pe a doua linie a fișierului de intrare tralala.in se află un șir de NN numere naturale de la 11 la 1212 ce reprezintă înșiruirea de note a melodiei inițiale.

Date de ieșire

Pe prima linie a fișierului de ieșire tralala.out se va afla un număr natural LL reprezentând numărul de note folosite după ce melodia a fost reparată.
Pe a doua linie a fișierului de ieșire tralala.outse va afla un șir de numere naturale separate prin spații, de la 11 la 1212 ce reprezintă melodia pe care Gheorghe i-o prezintă lui Tiberiu la următoarea oră de curs. (merge pe mâna voastră)

Restricții și precizări

  • 1N1 000 0001 \leq N \leq 1 \ 000 \ 000;
  • Toate notele din șirul inițial și final vor fi de la 11 la 1212
  • Se garantează că în melodia inițială se vor afla cel puțin 77 note diferite
  • Punctajul pentru fiecare din cele 5050 de teste se va calcula după urmatoarea formulă: Fie LL lungimea obținută de soluția trimisă de voi și LoL_o lungimea obținută de soluția comisiei. Dacă soluția este corectă și respectă regulile de mai sus, punctajul obținut pentru fiecare test este: 2min(1,LLo2)2 \cdot min(1, \frac{L}{L_o}^2)

Exemplul 1

tralala.in

20
1 5 12 3 10 5 2 6 11 2 2 3 1 6 12 3 9 5 8 8

tralala.out

17
1 2 3 5 6 8 12 8 6 5 3 2 1 2 3 5 12 

Explicație

Această melodie are în componență 1717 note, obținând punctajul maxim.

Exemplul 2

tralala.in

10
1 1 1 2 2 3 4 5 6 7

tralala.out

9
1 7 3 5 4 2 7 2 1

Explicație

Această soluție este compusă din 99 note, iar melodia optimă din 1010, deci punctajul obținut pe acest test ar fi 29102=1.622 \cdot \frac{9}{10}^ 2 = 1.62

Log in or sign up to be able to send submissions!