Fişierul intrare/ieşire:maxim3.in, maxim3.outSursăOJI 2019, clasa a 6-a
AutorAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test1.5 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Maxim3

Dintr-un șir format din N cifre, numerotate de la 1 la N, Ionel ia exact M cifre aflate pe poziții consecutive. El lipește cifrele luate sau le amestecă și apoi le lipește pentru a obține cu ele un număr cât mai mare.
Cunoscând N, M și cele N cifre din șir, să se determine:

  1. Cel mai mare număr care se poate obține din primele M dintre cele N cifre date;
  2. De unde va lua Ionel M cifre aflate pe poziții consecutive pentru a obține un număr maxim; dacă sunt mai multe poziții corespunzătoare unui număr maxim,
    alegerea se va face astfel încât numărul format din cifrele rămase, în ordinea în care erau, să fie cât mai mare posibil; dacă și în acest caz există mai multe soluții, se alege poziția maximă.

Date de intrare

Din fișierul maxim3.in se citesc: P de pe prima linie, reprezentând cerința problemei (1 sau 2), N și M de pe a doua linie, despărțite printr-un spațiu, cu semnificația din enunț, iar de pe linia a treia, se citesc cele N cifre, despărțite prin câte un spațiu.

Date de ieşire

În fișierul maxim3.out se scrie:

  1. Pentru P=1: numărul maxim care se poate obține cu ajutorul primelor M cifre dintre cele N date, fără spații între cifrele numărului;
  2. Pentru P=2: un număr reprezentând poziția cerută.

Restricţii

  • M, N numere naturale, 1 ≤ N ≤ 500000, 1 ≤ M ≤ 1000, M < N
  • Cele N valori de pe linia a treia sunt numere naturale între 0 și 9
  • Secvența de N cifre poate să înceapă cu cel mult M-1 cifre nule.
  • 30 de puncte se vor obține cu rezolvarea cerinței 1, iar 60 de puncte se vor obține cu
    rezolvarea cerinței 2. 10 puncte sunt din oficiu (corespund unor teste egale cu primul exemplu).
  • Pentru 50% dintre teste, N < 1000 și M < 10.

Exemple

maxim3.inmaxim3.outExplicatie
1
10 3
7 2 8 1 0 0 4 7 8 1
872
Se rezolvă cerința 1.
Cu primele 3 cifre dintre cele 10 cifre date se pot forma numerele: 728, 782, 287, 278, 827, 872, cel mai mare fiind 872
2
10 3
7 2 8 1 0 0 4 7 8 1
7
Se rezolvă cerința 2.
Alegând cifrele începând de la poziția a 7-a (cifrele 4, 7 și 8), se va forma numărul 874, care este cel mai mare posibil.
2
10 2
0 7 2 8 4 8 7 1 7 8
9
Se rezolvă cerința 2.
Alegând cifrele începând de la poziția a 6-a (cifrele 8 și 7) sau cifrele începând cu poziția a 9-a (7 și 8) va forma numărul
87 care este cel mai mare număr de două cifre consecutive. Dar, eliminînd cifrele de pe pozițiile 6 și 7, secvența rămasă este
07284178 (cu valoarea 7284178), pe când eliminând cifrele de pe pozițiile 9 și 10 numărul rămas este 7284871 care este mai mare.
2
10 2
5 9 6 9 6 8 2 6 6 8
4
Se rezolvă cerința 2.
Alegând cifrele de pe pozițiile 2,3 sau 3,4 sau 4,5 se va forma numărul 96 care este cel mai mare număr de două cifre
consecutive posibil. Dar, eliminând cifrele de pe pozițiile 2 și 3, numărul rămas este 59682668, eliminând cifrele de pe
pozițiile 3 și 4 numărul rămas este 59682668, eliminând cifrele de pe pozițiile 4 și 5 numărul rămas este 59682668. Se poate
afișa poziția 2 sau 3 sau 4, dar se va alege poziția maximă, 4.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?