Submission #68406044

---

Source Code Expand

#include <deque>
#include <iostream>
#include <utility>

using std::cin;
using std::cout;

constexpr int kMaxN = 1e5 + 5;
bool visited[kMaxN];
int k;

int Bfs() {
    std::deque<std::pair<int, int>> deq;
    deq.push_front(std::make_pair(1, 1));
    
    while (!deq.empty()) {
        int u = deq.front().first, w = deq.front().second;
        deq.pop_front();
        
        if (u == 0) {
            return w;
        }
        
        if (visited[(u * 10) % k] == false) {
            deq.push_front(std::make_pair((u * 10) % k, w));
            visited[(u * 10) % k] = true;
        }
        
        if (visited[(u + 1) % k] == false) {
            deq.push_back(std::make_pair((u + 1) % k, w + 1));
        }
    }
    
    return -1;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> k;
    
    cout << Bfs() << '\n';
    
    return 0;
}

Submission Info

Judge Result