Submission #3266978


Source Code Expand

Copy
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.stream.Stream;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskX solver = new TaskX();
		solver.solve(1, in, out);
		out.close();
	}

	static int INF = 1 << 30;
	static long LINF = 1L << 55;
	static int MOD = 1000000007;
	static int[] mh4 = { 0, -1, 1, 0 };
	static int[] mw4 = { -1, 0, 0, 1 };
	static int[] mh8 = { -1, -1, -1, 0, 0, 1, 1, 1 };
	static int[] mw8 = { -1, 0, 1, -1, 1, -1, 0, 1 };

	@SuppressWarnings("unchecked")
	static class TaskX {

		public void solve(int testNumber, InputReader in, PrintWriter out) {

			int k = in.nextInt();
			List<P>[] g = new ArrayList[k];
			g = Stream.generate(ArrayList::new).limit(k).toArray(List[]::new);

			for (int i = 0; i < k; i++) {
				g[i].add(new P((i + 1) % k, 1));
				g[i].add(new P((i * 10) % k, 0));
			}

			PriorityQueue<Integer> pq = new PriorityQueue<>();
			pq.add(1);
			long[] cost = new long[k];
			Arrays.fill(cost, INF);
			cost[1] = 1;

			while (!pq.isEmpty()) {
				int cur = pq.remove();
				for (P p : g[cur]) {
					if (cost[cur] + p.c < cost[p.t]) {
						cost[p.t] = cost[cur] + p.c;
						pq.add(p.t);
					}
				}
			}
			out.println(cost[0]);

		}

		class P implements Comparable<P> {
			int t;
			long c;

			public P(int t, long c) {
				super();
				this.t = t;
				this.c = c;
			}

			@Override
			public String toString() {
				return "P [t=" + t + ", c=" + c + "]";
			}

			@Override
			public int compareTo(P o) {
				return Long.compare(this.c, o.c);
			}

		}
	}

	static class InputReader {
		BufferedReader in;
		StringTokenizer tok;

		public String nextString() {
			while (!tok.hasMoreTokens()) {
				try {
					tok = new StringTokenizer(in.readLine(), " ");
				} catch (IOException e) {
					throw new InputMismatchException();
				}
			}
			return tok.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(nextString());
		}

		public long nextLong() {
			return Long.parseLong(nextString());
		}

		public double nextDouble() {
			return Double.parseDouble(nextString());
		}

		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt();
			}
			return res;
		}

		public int[] nextIntArrayDec(int n) {
			int[] res = new int[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextInt() - 1;
			}
			return res;
		}

		public int[] nextIntArray1Index(int n) {
			int[] res = new int[n + 1];
			for (int i = 0; i < n; i++) {
				res[i + 1] = nextInt();
			}
			return res;
		}

		public long[] nextLongArray(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public long[] nextLongArrayDec(int n) {
			long[] res = new long[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextLong() - 1;
			}
			return res;
		}

		public long[] nextLongArray1Index(int n) {
			long[] res = new long[n + 1];
			for (int i = 0; i < n; i++) {
				res[i + 1] = nextLong();
			}
			return res;
		}

		public double[] nextDoubleArray(int n) {
			double[] res = new double[n];
			for (int i = 0; i < n; i++) {
				res[i] = nextDouble();
			}
			return res;
		}

		public InputReader(InputStream inputStream) {
			in = new BufferedReader(new InputStreamReader(inputStream));
			tok = new StringTokenizer("");
		}
	}

}

Submission Info

Submission Time
Task D - Small Multiple
User tutuz
Language Java8 (OpenJDK 1.8.0)
Score 700
Code Size 4029 Byte
Status
Exec Time 540 ms
Memory 77232 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 176 ms 26324 KB
02.txt 165 ms 25940 KB
03.txt 158 ms 27476 KB
04.txt 152 ms 24404 KB
05.txt 171 ms 25940 KB
06.txt 165 ms 25940 KB
07.txt 157 ms 25804 KB
08.txt 166 ms 27732 KB
09.txt 167 ms 23888 KB
10.txt 157 ms 26196 KB
11.txt 171 ms 25940 KB
12.txt 153 ms 23372 KB
13.txt 160 ms 25172 KB
14.txt 165 ms 25296 KB
15.txt 173 ms 24276 KB
16.txt 154 ms 26452 KB
17.txt 165 ms 26452 KB
18.txt 163 ms 23380 KB
19.txt 165 ms 24020 KB
20.txt 162 ms 26580 KB
21.txt 285 ms 54868 KB
22.txt 289 ms 53204 KB
23.txt 540 ms 76500 KB
24.txt 512 ms 72444 KB
25.txt 412 ms 60872 KB
26.txt 371 ms 59476 KB
27.txt 423 ms 66644 KB
28.txt 419 ms 59340 KB
29.txt 475 ms 60260 KB
30.txt 516 ms 77232 KB
31.txt 150 ms 25684 KB
32.txt 166 ms 26580 KB
33.txt 436 ms 54396 KB
34.txt 344 ms 47028 KB
35.txt 433 ms 53820 KB
36.txt 428 ms 57600 KB
37.txt 295 ms 37988 KB
38.txt 310 ms 49328 KB
39.txt 368 ms 47652 KB
40.txt 213 ms 26580 KB
41.txt 346 ms 57172 KB
42.txt 389 ms 59304 KB
43.txt 254 ms 26832 KB
44.txt 198 ms 24276 KB
45.txt 337 ms 48876 KB
46.txt 360 ms 51352 KB
47.txt 189 ms 24528 KB
48.txt 335 ms 51796 KB
49.txt 358 ms 57632 KB
50.txt 329 ms 50756 KB
51.txt 252 ms 34600 KB
52.txt 303 ms 47088 KB
53.txt 336 ms 54484 KB
54.txt 258 ms 34916 KB
55.txt 339 ms 49960 KB
56.txt 306 ms 51148 KB
57.txt 384 ms 56788 KB
58.txt 292 ms 47340 KB
59.txt 310 ms 51284 KB
60.txt 298 ms 53332 KB
61.txt 215 ms 28116 KB
62.txt 228 ms 40532 KB
63.txt 279 ms 54608 KB
64.txt 289 ms 54996 KB
s1.txt 165 ms 25940 KB
s2.txt 154 ms 25556 KB
s3.txt 295 ms 52692 KB