Submission #3446782

---

Source Code Expand

/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int K = 1e5 + 10, S = 50, inf = 1e9;

bool seen[K][S];

void dfs(int m, int s, int k, int mx);

int main() {
	fast_cin();
	int k; cin >> k;
	int best = 0, temp = k;
	while (temp) {
		best += temp % 10;
		temp /= 10;
	}
	dfs(0, 0, k, best);
	for (int s = 1; s <= best; ++s) {
		if (seen[0][s]) {
			cout << s << endl;
			break;
		}
	}
}

void dfs(int m, int s, int k, int mx) {
	if (s > mx or seen[m][s]) {
		return;
	}
	seen[m][s] = true;
	for (int d = 0; d < 10; ++d) {
		dfs(((10 * m) + d) % k, s + d, k, mx);
	}
}

Submission Info

Judge Result