Puoi leggere e provare a risolvere questo problema visitando questo indirizzo compleanno
Per prima cosa possiamo assumere che tutte le operazioni incolla avvengano dopo un'operazione copia o dopo un'altra operazione incolla, per cui il problema diventa quindi equivalente a raggiungere emoji utilizzando le operazioni:
La sequenza ottima di operazioni sarà quindi una successione simile a:
Notiamo che . Se conoscessimo quindi i valori potremmo ricavarci anche i valori facilmente.
Con queste osservazioni possiamo costruire una prima semplice soluzione, definiamo come il numero minimo di click per ottenere , possiamo calcolare come:
Possiamo utilizzare la programmazione dinamica per calcolare efficientemente utilizzando una mappa con tutti i valori già calcolare. La risposta al problema è .
Lemma: se allora è un numero primo.
Con questa ottimizzazione anziché iterare su tutti i possibili valori , iteriamo solo su numero ristretto di possibili valori. Facendo ciò il numero di volte che la funzione viene chiamata diminuisce significativamente.
Lemma: .
Con questo lemma possiamo approssimare . Facendo ciò possiamo iterare sui possibili valori di uno alla volta aggiornando il valore ottimale dopo ogni tentativo provato. Tuttavia anziché calcolare direttamente il valore di , proviamo prima ad approssimarlo e se otteniamo un valore più grande del valore ottimale calcolato fino a quel punto, allora ignoriamo e passiamo al successivo.
Queste due ottimizzazioni sono sufficienti per poter totalizzare il punteggio pieno nel problema.
const static vector<int> possible_mul = {2, 3, 4, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
int lower_solve(LL N) { return 5*(log(N)/log(4)) - 0.1; }
unordered_map<LL,int> memo;
int solve(LL N) {
if (N == 0) return 0;
if (memo.count(N)) return memo[N];
int res = min(1000ll, N);
for (int mul : possible_mul) {
int add = N % mul;
if (add + mul + 1 + lower_solve(N / mul) >= res) continue;
int ris = add + mul + 1 + solve(N / mul);
res = min(res, ris);
}
memo[N] = res;
return res;
}
void auguri(LL N) {
vector<pair<int,int>> ops;
while (N != solve(N)) {
int res = solve(N);
pair<int,int> op;
for (int mul : possible_mul) {
int add = N % mul;
if (!memo[N / mul]) continue;
int ris = add + mul + 1 + solve(N / mul);
if (res == ris) op = {mul, add};
}
ops.push_back(op);
N = N / op.first;
}
reverse(ops.begin(), ops.end());
for (int i = 1; i <= N; i++) aggiungi();
for (auto op: ops) {
copia();
for (int i = 2; i <= op.first; i++) incolla();
for (int i = 1; i <= op.second; i++) aggiungi();
}
}