Subiectul I, cerința 3
Cifre distincte și cifra maximă
Subprogramul cu doi parametri de ieșire și programul C++ care caută în interval cel mai mic număr scris cu cifrele 0, 1 și 2, cu lămurirea condiției din enunț pe baza exemplelor oficiale.
Ce condiție trebuie verificată
Formularea „se poate obține cu cifre din mulțimea {0,1,2}” se poate citi în două feluri, iar exemplele din enunț arată care este cel corect.
Dacă ar fi de ajuns ca toate cifrele să fie printre 0, 1 și 2, atunci în intervalul
[2016, 9000] cel mai mic număr potrivit ar fi 2020, nu 2021, iar în intervalul [1992, 2000] ar
exista numărul 2000, deci răspunsul nu ar fi nu exista. Amândouă exemplele s-ar contrazice.
Numerele date de enunț se obțin dacă se cere ca numărul să fie scris cu toate cele trei cifre: 2021 este primul număr din [2016, 9000] în care apar și 0, și 1, și 2, iar în [1992, 2000] nu există niciun astfel de număr. Condiția devine astfel:
- numărul are exact 3 cifre distincte, adică
nrd = 3; - cifra lui maximă este 2, adică
cma = 2.
Cele două condiții luate împreună înseamnă că mulțimea cifrelor numărului este exact {0, 1, 2}: sunt trei cifre distincte, iar cea mai mare dintre ele este 2, deci celelalte două nu pot fi decât 0 și 1.
Descrierea algoritmului în limbaj natural
Se citesc de la tastatură cele două capete ale intervalului, x și y, despre care enunțul spune că x este mai mic decât y.
Se parcurg numerele din interval, în ordine crescătoare, începând de la x. Pentru fiecare număr se
apelează subprogramul cifDistMax, care furnizează numărul de cifre distincte și cifra maximă.
Numărul căutat este primul pentru care numărul de cifre distincte este 3 și cifra maximă este 2.
Fiindcă parcurgerea pornește de la capătul din stânga și se oprește la prima potrivire, valoarea
găsită este cea mai mică din interval care îndeplinește condiția.
Dacă parcurgerea se încheie fără ca vreun număr să îndeplinească ambele condiții, în fișier se
scrie mesajul nu exista. În caz contrar se scrie valoarea găsită.
În interiorul subprogramului, cifrele numărului se obțin una câte una, ca rest al împărțirii la 10, iar numărul se reduce prin împărțire întreagă la 10 până devine 0. Pentru numărarea cifrelor distincte se folosește un vector cu zece poziții, în care se marchează cifrele deja întâlnite: o cifră se numără numai la prima ei apariție. În aceeași parcurgere se reține și cea mai mare cifră întâlnită.
Rezolvarea se poate citi pe educamp.ro, la adresa de mai sus.
S-a încheiat minutul de citit liber.
Ce cuprinde rezolvarea
- Ce condiție trebuie verificată
- Descrierea algoritmului în limbaj natural
- Programul
- Verificarea pe exemplele din enunț
Vezi rezolvarea ca și cursant
Cel puțin o cerință din fiecare an este disponibilă gratuit și integral. Pentru a citi toate celelalte rezolvări ale disciplinei, te înscrii la cursul de pregătire.
Cursul cuprinde suportul de curs publicat până acum, care se completează capitol cu capitol, și două întâlniri de câte două ore în fiecare lună. Prima săptămână este gratuită, fără plată și fără card. Dacă vrei să vezi mai întâi cum este scrisă o rezolvare, poți reveni la prima cerință a anului.