Help with Digit Dp problem (Magic Numbers)

Revision en1, by Ankush08, 2021-04-24 11:09:28

I was attempting this problem : https://mirror.codeforces.com/contest/628/problem/D and came up with a solution which basically look like this :

int d, m;

ll int magicNumberDP(string n, int idx,ll int curNum, bool tight) {
	if (idx >= n.length()) {
		return !curNum ;
	}

	int uprBnd = (tight) ? n[idx] - '0' : 9 ;

	ll int ans = 0 ;

	for (int dig = 0 ; dig <= uprBnd ; dig++) {
		if ((idx + 1) % 2 == 0 and d != dig) {
			continue ;
		}

		if ((idx + 1) % 2 == 1 and d == dig) {
			continue ;
		}

		ans = ans + magicNumberDP(n, idx + 1, (curNum * 10 + dig) % m, tight & (dig == uprBnd)) ;
	}

	return ans;
}

void magicNumber() {
	cin >> m >> d ;
	ll int r, l;
	cin >> l >> r ;

	l--;

	string R = to_string(r);
	string L = to_string(l);

	int ansR = magicNumberDP(R, 0, 0ll, 1);

	int ansL = magicNumberDP(L, 0, 0ll, 1);

	cout << ansL << " " << ansR << endl ;
	cout << ansR - ansL << endl;
}

But this is giving wrong answer can someone tell me why I am wrong and how can I correct it?

Tags #digitdp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Ankush08 2021-04-24 11:09:28 1089 Initial revision (published)