Sto cercando di risolvere ois_23 e la mia attuale soluzione però non risolve 2 testcase e 3 vanno in timeout. Mi dareste una mano?
Ecco la mia soluzione:
la mia idea era di sortare il vettore e appena trovavo un numero presente nell’array far assumere al vettore sol in posizione dll’originale posizione del numero il valore dell’attuale “soluzione”;
sumDigits ritorna la somma delle cifre del numero convertito;
mentre solve controlla se la somma delle cifre in base 3 e in base 2 sono uguali e nel caso aumenta un contatore( var buffer) e se il numero è presente nel vettore salvare la sua soluzione
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
vector<pair<int,int>> V;
vector<int> sol;
int sumDigits(int n, int base)
{
int result = 0 ;
while (n > 0) {
result+= n % base ;
n /= base;
}
return result ;
}
void solve()
{
int buffer=0,count=0;
for(int i=1;i<=V[V.size()-1].first;i++){
if(sumDigits(i, 2) == sumDigits(i, 3))
buffer++;
if(V[count].first==i){
sol[V[count].second]=buffer;
count++;
}
}
}
int main()
{
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
int x,T;
cin>>T;
V.resize(T);
sol.resize(T);
for(int i=0;i<T;i++){
cin>>x;
V[i].first=x;
V[i].second=i;
}
sort(V.begin(),V.end());
solve();
for(int i=0;i<T;i++){
cout<<sol[i]<<" ";
}
return 0;
}
si, ho provato anche in altri modi con il bitwise ma comunque va in timeout, semplicemente riuso sum perche nello stesso momento riempio l’array dove tengo conto dei risultati in base 2 e 3