Autor: Ștefan-Cosmin Dăscălescu
Soluția problemei cifre (OJI 2016, clasa a IX-a)#
Cunoștințe necesare
Link problemă
Această problemă poate fi accesată aici.
De-a lungul acestei abordări, va fi foarte important să ne gândim la folosirea cifrelor pentru a codifica numărul de poziții pe care s-a plasat un anumit segment. Deoarece ni se dau segmentele, putem deja să codificăm cifrele care sunt incluse una în alta, sau pur și simplu să numărăm într-o listă câte cifre mai mari sunt incluse în alta.
Pentru prima cerință, nu trebuie decât să numărăm segmentele care apar în numere.
Pentru cea de-a doua cerință, ne putem gândi să fixăm cifra care va determina gradul de comparare între numere, iar pentru acea cifră să aflăm la câte cifre mai mari putem ajunge. Ulterior, pentru toate celelalte cifre vom afla câte numere pot fi obținute, indiferent că sunt mai mari sau mai mici decât ea.
Pentru a afla formula specifică fiecărei poziții, ne putem gândi la regula produsului, deoarece știm câte variante avem pentru fiecare poziție și le putem înmulți pentru a afla contribuția la răspuns a poziției curente.
Mai jos puteți găsi o soluție neoficială care ia punctajul maxim.
#include <fstream>
int c[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // nr de segmente
int t[] = {2, 7, 2, 3, 3, 4, 2, 5, 1, 2}; // nr de numere pe care le putem obtine
int mm[] = {1, 5, 1, 2, 2, 3, 1, 2, 0, 0}; // nr de numere mai mari
int cif[25];
char s[25];
unsigned long long p, sol;
int main() {
std::ifstream cin("cifre.in");
std::ofstream cout("cifre.out");
int t1, k = 0, sum = 0, g;
cin >> t1;
cin >> s;
for (k = 0; s[k]; k++) {
cif[k] = s[k] - '0';
}
if (t1 == 1) {
for (int i = 0; i < k; i++) {
sum += c[cif[i]];
}
cout << sum;
}
else {
for (int i = 0; i < k; i++) {
p = 1;
for (int j = i + 1; j < k; j++) {
g = cif[j];
p *= t[g];
}
sol += mm[cif[i]] * p;
}
cout << sol;
}
return 0;
}