提出 #72913829

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10;
int dx[]{-1, -1, -1};
int dy[]{-1, 0, 1};

void solve()
{
    int n;
    cin >> n;
    if (n % 10 == 0)
    {
        cout << -1 << "\n";
        return;
    }
    vector<vector<int>> vis(10, vector<int>(n + 1, -1));
    vector<vector<int>> res(10, vector<int>(n + 1, 0));
    vector<vector<int>> len(10, vector<int>(n + 1, 1e9));

    vector<int> ans;
    queue<array<int, 2>> q;
    q.push({0, 0});
    len[0][0] = 0;
    int now = 0;
    while (q.size())
    {
        auto [pre, mod] = q.front();
        q.pop();
        if (mod == 0 and pre != 0)
        {
            now = pre;
            break;
        }
        for (int i = max(1ll, pre); i <= 9; i++)
        {
            if (vis[i][(mod * 10 + i) % n] == -1)
            {
                q.push({i, (mod * 10 + i) % n});
                vis[i][(mod * 10 + i) % n] = pre;
                res[i][(mod * 10 + i) % n] = mod;
                len[i][(mod * 10 + i) % n] = len[pre][mod] + 1;
            }
        }
    }

    // int minn = 1e9;
    // for (int i = 1; i <= 9; i++)
    // {
    //     if (minn > len[i][0])
    //     {
    //         minn = len[i][0];
    //         now = i;
    //     }
    // }
    if (now == 0)
    {
        cout << -1 << '\n';
        return;
    }
    ans.push_back(now);
    int mod = res[now][0];
    now = vis[now][0];
    while (now != 0)
    {
        ans.push_back(now);
        int temp = vis[now][mod];
        mod = res[now][mod];
        now = temp;
    }

    for (int i = ans.size() - 1; i >= 0; i--)
        cout << ans[i];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--)
        solve();

    return 0;
}

提出情報

ジャッジ結果