# Cabala aiutatemi

**URL:** <https://forum.olinfo.it/t/cabala-aiutatemi/7340>\
**Category:** Aiuto\
**Created:** [12 Maggio 2022, 10:29pm UTC](https://forum.olinfo.it/t/cabala-aiutatemi/7340 "2022-05-12T22:29:52Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Alegag](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alegag/32/777_2.png) [@Alegag](https://forum.olinfo.it/u/Alegag)\
**Post date:** [12 Maggio 2022, 10:29pm UTC](https://forum.olinfo.it/t/cabala-aiutatemi/7340/1 "2022-05-12T22:29:53Z")

</div>

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

```auto
#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) << " ";
	}
}

```

---

<div class="post-metadata">

**Author:** ![Glauco](https://forum.olinfo.it/user_avatar/forum.olinfo.it/glauco/32/2371_2.png) [@Glauco](https://forum.olinfo.it/u/Glauco)\
**Post date:** [14 Maggio 2022, 4:01pm UTC](https://forum.olinfo.it/t/cabala-aiutatemi/7340/2 "2022-05-14T16:01:22Z")

</div>

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.

> **[book.pdf](https://cses.fi/book/book.pdf)**
>
> 1074.18 KB

Qui trovi un capitolo sul backtracking.

---

<div class="post-metadata">

**Author:** ![Alegag](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alegag/32/777_2.png) [@Alegag](https://forum.olinfo.it/u/Alegag)\
**Post date:** [15 Maggio 2022, 2:05am UTC](https://forum.olinfo.it/t/cabala-aiutatemi/7340/3 "2022-05-15T02:05:29Z")

</div>

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