Cabala aiutatemi

Aiuto
1

Sto cercando di risolvere ois_cabala ma non riesco ad ottimizzare il codice, qualcuno mi può dare una mano?

#include <bits/stdc++.h>
using namespace std;
bool controlla(int a){
	string b = to_string(a);
	for(int i=0; i<b.size(); i++){
		if(b[i] != '3' && b[i] != '6' && b[i] != '9'){
			return false;
		}
		if(i != b.size()-1){
			if(b[i] == b[i+1]){
				return false;
			}
		}
	}
	return true;
}
int occulta(int N, int M, int ris, int att){
	if(to_string(ris).size() <= N){
		if(controlla(ris)){
			return att;
		}else{
			return occulta(N, M, ris+M, att);
		}
	}else{
		return occulta(N, M, att-1, att-1);
	}
}
int main(){ 
	int T;
	cin >> T;
	int N, M;
	for(int k=0; k<T; k++){	
		cin >> N >> M;
		cout << occulta(N, M, M-1, M-1) << " ";
	}
}
2

Ciao, mi sembra di capire che stai applicato un approccio brute force, quindi molto inefficiente. In poche parole stai controllando ogni possibile numero di lunghezza N, cioè un totale di 10^N numeri.

Ti consiglio invece di scrivere una soluzione che sfrutti ricorsione con backtracking. Se non sai bene cosa sia, ti linko l’handbook.

Qui trovi un capitolo sul backtracking.

3

il problema non è il tempo ma l’output che ridà sbagliato