Submission #1746313


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;

int solve(int K) {
    deque<ii> dq;
    vector<int> vis(K, 0);

    dq.push_front(ii(1, 1)); // num(%K), cost
    while (!dq.empty()) {
        ii p = dq.front(); dq.pop_front();
        int curr = p.first, cnt = p.second;
        if (curr == 0) return cnt;

        vis[curr] = 1;
        int next = (curr + 1)% K;
        if (vis[next] == 0)
            dq.push_back(ii(next, cnt+1));

        next = (curr * 10) % K;
        if (vis[next] == 0)
            dq.push_front(ii(next, cnt));
    }
}

int main() {
    int K; cin >> K;
    cout << solve(K) << endl;
    return 0;
}

Submission Info

Submission Time
Task D - Small Multiple
User naoya_t
Language C++14 (GCC 5.4.1)
Score 700
Code Size 683 Byte
Status
Exec Time 9 ms
Memory 1152 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 700 / 700 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 1 ms 256 KB
02.txt 1 ms 256 KB
03.txt 1 ms 256 KB
04.txt 1 ms 256 KB
05.txt 1 ms 256 KB
06.txt 1 ms 256 KB
07.txt 1 ms 256 KB
08.txt 1 ms 256 KB
09.txt 1 ms 256 KB
10.txt 1 ms 256 KB
11.txt 1 ms 256 KB
12.txt 1 ms 256 KB
13.txt 1 ms 256 KB
14.txt 1 ms 256 KB
15.txt 1 ms 256 KB
16.txt 1 ms 256 KB
17.txt 1 ms 256 KB
18.txt 1 ms 256 KB
19.txt 1 ms 256 KB
20.txt 1 ms 256 KB
21.txt 1 ms 640 KB
22.txt 9 ms 768 KB
23.txt 3 ms 1024 KB
24.txt 5 ms 1024 KB
25.txt 4 ms 1024 KB
26.txt 2 ms 768 KB
27.txt 4 ms 1024 KB
28.txt 5 ms 1152 KB
29.txt 3 ms 896 KB
30.txt 6 ms 1024 KB
31.txt 1 ms 256 KB
32.txt 1 ms 256 KB
33.txt 7 ms 768 KB
34.txt 2 ms 512 KB
35.txt 4 ms 768 KB
36.txt 3 ms 768 KB
37.txt 2 ms 384 KB
38.txt 2 ms 512 KB
39.txt 3 ms 640 KB
40.txt 1 ms 256 KB
41.txt 3 ms 896 KB
42.txt 6 ms 1024 KB
43.txt 2 ms 384 KB
44.txt 1 ms 256 KB
45.txt 2 ms 512 KB
46.txt 4 ms 640 KB
47.txt 1 ms 256 KB
48.txt 4 ms 896 KB
49.txt 3 ms 768 KB
50.txt 3 ms 640 KB
51.txt 2 ms 384 KB
52.txt 2 ms 512 KB
53.txt 3 ms 640 KB
54.txt 2 ms 512 KB
55.txt 4 ms 640 KB
56.txt 2 ms 640 KB
57.txt 7 ms 1024 KB
58.txt 5 ms 768 KB
59.txt 7 ms 896 KB
60.txt 7 ms 768 KB
61.txt 1 ms 384 KB
62.txt 2 ms 512 KB
63.txt 3 ms 640 KB
64.txt 9 ms 768 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 4 ms 640 KB