Question

URGENT URGENT!!!

În această problemă veţi primi două numere natural N, şi K. Definim magnitudinea unui număr ca fiind diferenţa dintre cifra maximă şi cifra minimă ale lui. De exemplu, magnitudinea lui 9748 este 9 - 4 = 5. Eliminaţi maxim K cifre din numărul N, astfel încât magnitudinea numărului obţinut să fie cât mai mică. Date de intrare În fișierul magnitudine.in se află pe prima linie numerele N si K separate prin spaţii. Date de ieșire Afișați în fișierul magnitudine.out magnitudinea minimă care se poate obţine după eliminarea a K cifre ale lui N. Restricții și precizări  1 ≤ N ≤ 10 18  pentru teste în valoare de 30 puncte, K = 0  pentru teste în valoare de 30 puncte, K = 1  pentru teste în valoare de 40 puncte, K = 2 Exemplu magnitudine.in magnitudine.out Explicații 9748 1 2 Daca eliminam cifra 4 obtinem 978 cu magnitudine = 2. DAU CORONITA!

Answer 1

Pai o luam incetisor:

1. Citesti numerele n si k.

2. Pai daca definim magnitudinea ca cifra_maxima - cifra_minima, ai doua optiuni ca sa scazi magnitudinea: ori sa elimini mereu cea mai mare cifra, astfel cifra maxima scade, ori sa elimini mereu cifra minima, asftel cifra minima scade. Solutia e sa elimini ori cifra maxima de k ori ori cifra minima de k ori.

Trucul e sa iti dai seama daca elimini maximul sau minimul:

Sa spunem ca avem nr 944, magnitudinea se vede ca este 9 - 4 = 5. Acum, daca eliminam cifra minima, 4, ramanem cu 94, care are tot magnitudinea 5, nu am facut mare lucru.

Dar sa spunem ca eliminam cifra maxima, aia e 9, si obxinem 44, care are magnitudinea 0, mult mai bine. 

Cea mai simpla solutie este sa faci urmatoarea treaba:

1. un vector de numere si un condor ca sa retii cate elemente ai in vector. 

2. Folosind un whhile nr > 0, ii vei lua pe rand cifrele si le vei pune in vectorul de la 1. Acum ai cifrele separate in vector, super!

3. Acum cam trebuie sa incerci si cu eliminatul maximului si cu al minimului de k ori asa ca intai o sa eliminam maximul:

Un for de la 1 la k pt ca eliminam maximul de k ori.

In acest for determini maximul dintre cifrele din vector, si il stergi. Ca sa il sfergi poti muta toate cifrele din dreapta acelei cifre cu o pozitie mai la stanga, si scazi contorul de lungime. 

Dupa ce ai facut asta de k ori verifici iar magnitudinea si o retii intr-o variabila. 

Apoi trebuie iar cu un for de la 1 la k ca sa verificam si daca e mai ok sa eliminam minimul(atentie ca trebuie ori sa iti descompui numarul original ori sa faci de la inceput doua matrici cu cifre, pentru ca pe prima matrice ai tot scmibat-o cand calculai ce e mai sus)

Aici e similar doar ca in lok sa calculezi si sa scoti maximul de k ori, vei scoate minimul. Apoi calculezi magnitudinea si pentru cifrele din aceste vector si vezi la care metoda ti-a dat magnitudine mai mica, la scos maximul sau minimul, si ala e raspunsul tau!