Se dă un număr natural nenul n. Să se determine numărul de numere de n cifre din mulțimea {1, 2, 3, 4} care nu au două cifre alăturate egale și care au proprietatea că sunt divizibile cu 2. Pentru că acest număr poate fi foarte mare, se va calcula modulo 123457.
Date de intrare
Programul citește de la tastatură numărul n,.
Date de ieșire
Programul va afișa pe ecran numărul cerut, modulo 123457.
Restricții și precizări
Pentru 80 de puncte, 1 ≤ n ≤ 10. 000
Pentru alte 20 de puncte, 100. 0. 000 ≤ n ≤ 1. 0. 0. 000
Exemplu
Intrare
2
Ieșire
6
Explicație
Numerele sunt 12, 14, 24, 32, 34, 42.
Răspunsuri la întrebare
Răspuns:
Pentru a rezolva această problemă, putem utiliza un algoritm de programare dinamică. În fiecare pas, vom calcula numărul de numere valide de lungime i care nu au două cifre alăturate egale și care sunt divizibile cu 2.
f[i] = f[i - 1] * 4 - f[i - 2] * 2, i >= 2
Această recurență se bazează pe ideea că, pentru a calcula numărul de numere valide de lungime i, putem lua fiecare număr valid de lungime i - 1 și adăuga o cifră la sfârșitul său, astfel încât să avem f[i - 1] * 4 numere noi. Dar, dintre aceste numere, unele pot avea două cifre alăturate egale, deci trebuie să le scădem din numărul total de numere noi. Aceste numere sunt cele care au forma abaa, unde a și b sunt oricare dintre cele patru cifre permise (1, 2, 3, 4). Acestea sunt de fapt toate numerele de lungime i - 2 care nu au două cifre alăturate egale și care sunt divizibile cu 2, deci putem calcula numărul lor folosind valoarea f[i - 2].
Pentru a implementa acest algoritm, putem utiliza un vector pentru a stoca valorile intermediare ale lui f, astfel încât să putem calcula valoarea lui f[i] în timpul O(1). De asemenea, trebuie să inițializăm vectorul cu valorile pentru i = 0 și i = 1, astfel încât recurența să poată fi folosită pentru a calcula valorile pentru i >= 2.
Aici este o posibilă implementare a algoritmului în C++:
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 123457;
int main() {
int n;
cin >> n;
// Initialize f[0] and f[1].
vector<int> f(n + 1, 0);
f[0] = 1;
f[1] = 2;
// Calculate f[i] for i >= 2.
for (int i = 2; i <= n; i++) {
f[i] = (f[i - 1] * 4 - f[i - 2] * 2) % MOD;
}
// Print the result.
cout << f[n] << endl;
return 0;
}
Explicație:
Sper să te ajute!