Fişierul intrare/ieşire:maxim2.in, maxim2.outSursăOJI 2019 clasa a 6-a
AutorRodica PinteaAdăugată defrancuCristian Francu francu
Timp execuţie pe test1 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Maxim2 (clasa a 6-a)

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.

Cerinţe

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 maxim2.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 maxim2.out se scrie:

  • 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;
  • 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.
  • Se acordă 10p din oficiu, cu condiţia ca programul să compileze şi execuţia lui să se termine normal, în timpul alocat.
  • Pentru 50% dintre teste, N < 1000 şi M < 10.

Exemplu

maxim2.inmaxim2.outExplicaţie
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