Salve, ho provato a risolvere ois_23, ma ho avuto qualche problema con la complessità di tempo (va oltre i 3 secondi previsti per input arbitrariamente grandi – ho fatto 65/100). Ci ho sbattuto la testa, ma non ho trovato soluzioni alternative alla mia, motivo per cui mi rivolgo direttamente al forum.
Questo è il mio codice:
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
unsigned int T, i;
unsigned long k, c;
using namespace std;
unsigned int sum(unsigned int n, unsigned int base)
{
unsigned int result = 0;
while (n > 0)
{
result += n % base;
n /= base;
}
return result;
}
int32_t main()
{
cin >> T;
vector<unsigned long> input(T);
map<unsigned long, unsigned long> special_numbers;
for (i = 0; i < T; i++)
{
cin >> input[i];
special_numbers[input[i]] = 0;
k = max(k, input[i]);
}
for (i = 1; i <= k; i++)
{
if (sum(i, 2) == sum(i, 3))
{
c++;
}
if (special_numbers.count(i) == 1)
special_numbers[i] = c;
}
for (i = 0; i < T; i++)
{
cout << special_numbers[input[i]] << " ";
}
return 0;
}
L’idea era di prendere gli input, inserirli in un apposito vettore e adottarli come chiave per una mappa (utile per poi inserire i “numeri speciali”). Credo che a prendere molto tempo siano le funzioni che calcolano la somma delle cifre in base 2 e 3. Come potrei migliorare questa soluzione? Vi ringrazio in anticipo.
Per risolvere l’esercizio io ho evitato di utilizzare la mappa, ma semplicemente mi tengo in un array ordinato i vari N_i e poi calcolo, come hai fatto tu, le somme delle cifre in base 2/3 di tutti i numeri fino al massimo tra gli N_i.
Per rendere più veloce la cosa, invece di usare la funziona che somma le cifre in una determinata base tengo 2 array che mantengono la rappresentazione in base 2 ed in base 3 del numero attuale. In questo modo posso implementare a mano l’incremento e, per sapere la somma delle cifre X+1, non devo ricalcolarlo da 0 ma mi baso sulla somma delle cifre di X e l’aggiorno in base alle cifre che ho cambiato incrementando X.
È poi possibile, è veloce ma non è molto costruttivo, precalcolarsi degli specifici valori da scrivere direttamente nel sorgente in modo da evitare calcoli successivi.
Ti ringrazio. In effetti, avevo pensato di precalcolarmi dei valori fino a 10\,000\,000, ma non ho ancora trovato un modo per inserirli in un array con constexpr.
Ottimo approccio quello di mantenere la rappresentazione del numero attuale nelle 2 basi in 2 array distinti, ma non ho capito bene come gestire l’incremento.
Il sorgente che puoi caricare deve avere dimensione entro un limite massimo che è abbastanza ridotto, e non ti permette quindi di scrivere dunque i risultati per ogni possibile N_i, in ogni caso puoi caricare solo alcune informazioni che ti evitano parzialmente dei calcoli.
Per quanto riguarda l’incremento manuale, tu puoi rappresentare X in base b come un array v[] dove v[i] è l’iesima cifra di X in base b, allora quando incrementi X dovrai incrementare di 1v[0] e nel caso in cui v[0] diventi uguale a b allora v[0] diventa 0 ed incrementi v[1] e nel caso in cui v[1] diventi uguale a b…(procedi con lo stesso ragionamento)[In pratica stai semplicemente incrementando un numero in base b]. Mentre cambi i valori relativi all’incremento puoi aggiornare la somma delle precedenti.
Se hai X = 11_{10} = 1011_2 e somma delle cifre S = 1+0+1+1=3 incrementando X ottieni X+1 = 1100_2 (tramite il ragionamento di prima) , e mentre modifichi le ultime 3 cifre puoi aggiornare la somma che risulterà = S -1 -1 +1 =S - 1 = 2.
Questo ha il vantaggio che in molti casi (soprattutto quando il X ha molte cifre) andrai a modificare un numero di cifre molto piccolo.
Ho implementato ciò ed effettivamente vi è stato un netto miglioramento in termini di prestazione, ma non tale da garantirmi di stare sotto i 3 secondi in tutti i testcase. Magari utilizzare una mappa e controllare se un valore vi appartiene è troppo dispendioso in termini di tempo? Quale sarebbe la cosa migliore?
In ogni caso, ecco il codice aggiornato:
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
unsigned int T, i;
unsigned short c_2, c_3;
unsigned short base2[27]; // 27 is the maximum number of digits a number can have in base 2 without being greater than 100_000_000 (base 10)
unsigned short base3[17]; // See base2
unsigned short j;
unsigned long k, c;
using namespace std;
int32_t main()
{
cin >> T;
vector<unsigned long> input(T);
map<unsigned long, unsigned long> special_numbers;
for (i = 0; i < T; i++)
{
cin >> input[i];
special_numbers[input[i]] = 0;
k = max(k, input[i]);
}
for (i = 1; i <= k; i++)
{
for (j = 0;; j++)
{
if (++base2[j] >= 2)
{
c_2 -= base2[j]-1;
base2[j] = 0;
continue;
}
c_2++;
break;
}
for (j = 0;; j++)
{
if (++base3[j] >= 3)
{
c_3 -= base3[j]-1;
base3[j] = 0;
continue;
}
c_3++;
break;
}
if (c_2 == c_3)
c++;
if (special_numbers.count(i) == 1)
special_numbers[i] = c;
}
for (i = 0; i < T; i++)
{
cout << special_numbers[input[i]] << " ";
}
return 0;
}
Io semplicemente metto tutti gli N_i in un array che poi ordino in modo crescente, tenendomi un indice che mi dice quale è il prossimo N_i e quando lo incontro lo salvo (ricordati di mantenere l’ordine originale). E poi non utilizzare i long, non sono necessari e rallentano l’esecuzione.
Un approccio un po’ più semplice per sapere la somma delle cifre è in base 2 è:
precalcolarsi la somma dei primi 2^{14} numeri,
sia b_0 b_1 b_2 \ldots b_{27} la rappresentazione in binario di x, possiamo notare che \underbrace{b_0 b_1 \ldots b_{13}}_{x\mod 2^{14}} \underbrace{b_{14} b_{15} \ldots b_{27}}_{\left\lfloor\frac{x}{2^{14}}\right\rfloor}
per cui S(x)=S\left(x\mod 2^{14}\right)+S\left(\left\lfloor\frac{x}{2^{14}}\right\rfloor\right).
Ringrazio tutti voi; ho avuto la possibilità di ottenere, finalmente direi, 100/100 su quell’esercizio. Ho pubblicato il codice, il quale è visibile a tutti e da cui ho tolto tutti i valori precalcolati (non mi era possibile caricare il file altrimenti).
Ottima funzione built-in! La utilizzerò sicuramente in futuro, ovviamente solo se avrò a che fare con un compilatore GCC (ho letto che è una funzione appartenente solo a questa specie di compilatore).
Alla fine ho adottato questa splendida soluzione, che appare molto semplice e dà un senso effettivo al precalcolo dei numeri. Ti ringrazio in particolare.