Cabala (30/100)

#include <iostream>
#include <vector>

using namespace std;

bool controlla (long long int n)
{
	int i=0;
	vector <int> N;
	do
	{
		N.push_back(n%10);
		n=n/10;
		i++;
	}
	while (n>0);
	
	for (int j=0; j<i-1; j++)
	{
		if (N[j]==N[j+1])
			return false;
	}
	
	for (int j=0; j<i-1; j++)
	{
		if (N[j]!=3 && N[j]!=6 && N[j]!=9)
			return false;
	}
	
	return true;
}

long long int occulta (int N, int M)
{
	long long int i=M-1, max=1, risposta; 
	for (int j=0; j<N; j++)
		max=max*10;
			
	bool ok=false;
	do 
	{
		long long int num=i;
		do
		{
			if (num%3==0)
			{
				if (controlla (num)==true)
				{
				    ok=true;
				    risposta=i;
				}
			}
			num=num+M;
		}
		while (num<max);
		i--;
	}
	while (ok==false);
	return risposta;
}

int main() 
{
    int T, N, M, i;

    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    cin>>T;
    for (i=0; i<T; i++) 
	{
        cin>>N>>M;
        cout<<occulta(N, M);
		cout<<" ";
    }
    return 0;
}

Non capisco dov’è il problema in questo algoritmo, qualcuno sa dirmi perchè?

Il report dice che negli ultimi test case va fuori tempo massimo, bisogna velocizzare l’algoritmo.
Il tuo programma ad esempio con N=18 lavora con una quantitĂ  enorme di numeri da controllare.

va bene grazie mille, devo evitare i cicli annidati ad esempio? sono alle prime armi e molte cose non le so

Anche se è un problema da una stella scarsa non è poi così facile, se guardi le statistiche sono in molti coloro che non l’hanno risolto, quindi forse non è un problema per chi è alle prime armi come tu dici; comunque invece di generare tanti numeri per poi scartarne la maggior parte prova a pensare di generare solo quelli che soddisfano già le prime 3 condizioni.

ok forse non sono proprio alle prime armi visto che forse sarò alle nazionali, ma penso di dover ancora imparare molto; grazie mille del consiglio, provo a lavorarci

ho trovato la soluzione grazie mille, ho totalizzato 100/100

2 Mi Piace