CSES - Datatähti Open 2017 - Results
Submission details
Task:Program
Sender:fjuengermann
Submission time:2017-01-22 15:15:27 +0200
Language:Java
Status:READY
Result:21
Feedback
groupverdictscore
#1ACCEPTED21
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.16 s1details
#2ACCEPTED0.14 s1details
#3ACCEPTED0.16 s1details
#4ACCEPTED0.16 s1details
#5ACCEPTED0.16 s1details
#6ACCEPTED0.16 s1details
#7ACCEPTED0.15 s1details
#8ACCEPTED0.15 s1details
#9ACCEPTED0.15 s1details
#10ACCEPTED0.15 s1details
#11ACCEPTED0.14 s2details
#12--2details
#13--2details
#14--2details
#15--2details
#16--2details
#17ACCEPTED0.14 s2details
#18--2details
#19--2details
#20ACCEPTED0.19 s2details
#210.12 s3details
#220.14 s3details
#230.16 s3details
#240.12 s3details
#250.17 s3details
#260.17 s3details
#270.14 s3details
#280.14 s3details
#290.15 s3details
#300.14 s3details

Code

import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * Created by Florian on 22-Jan-17.
 */
public class Program2 {
	static final int N = 1000000;
	static boolean[] visited = new boolean[N];

	public static void main(String args[]) throws IOException {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.nextLine());
		int m = n % 3;
		if (m == 0) {
			System.out.println(0);
			return;
		}
		Queue<Integer> queue = new LinkedList<>();
		Queue<ArrayList<Boolean>> paths = new LinkedList<>();
		queue.add(1);
		paths.add(new ArrayList<>());
		ArrayList<Boolean> path;
		int i;
		while (true) {
			i = queue.poll();
			path = paths.poll();
			if (i == n)
				break;
			int a = i + 3;
			int b = 2 * i;
			if (a <= n && !visited[a]) {
				queue.add(a);
				ArrayList<Boolean> pathA = new ArrayList<>(path);
				pathA.add(false);
				paths.add(pathA);
			}
			if (b <= n && !visited[b]) {
				queue.add(b);
				ArrayList<Boolean> pathB = new ArrayList<>(path);
				pathB.add(true);
				paths.add(pathB);
			}
		}
		StringBuilder sb = new StringBuilder();
		sb.append((path.size()+1)).append("\n");
		for (Boolean b : path) {
			if (b)
				sb.append("MUL\n");
			else
				sb.append("ADD\n");
		}
		sb.append("END\n");
		OutputStream out = new BufferedOutputStream(System.out);
		byte[] b = sb.toString().getBytes();
		out.write(b);
		out.flush();
	}
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
58

correct output
8
MUL
ADD
MUL
ADD
...

user output
8
ADD
ADD
ADD
ADD
...

Test 2

Group: 1

Verdict: ACCEPTED

input
72

correct output
0

user output
0

Test 3

Group: 1

Verdict: ACCEPTED

input
83

correct output
8
MUL
ADD
MUL
MUL
...

user output
8
ADD
ADD
ADD
MUL
...

Test 4

Group: 1

Verdict: ACCEPTED

input
53

correct output
8
ADD
MUL
ADD
MUL
...

user output
8
ADD
MUL
ADD
MUL
...

Test 5

Group: 1

Verdict: ACCEPTED

input
100

correct output
8
ADD
MUL
ADD
MUL
...

user output
8
ADD
MUL
ADD
MUL
...

Test 6

Group: 1

Verdict: ACCEPTED

input
64

correct output
6
ADD
MUL
MUL
MUL
...

user output
6
ADD
MUL
MUL
MUL
...

Test 7

Group: 1

Verdict: ACCEPTED

input
84

correct output
0

user output
0

Test 8

Group: 1

Verdict: ACCEPTED

input
60

correct output
0

user output
0

Test 9

Group: 1

Verdict: ACCEPTED

input
51

correct output
0

user output
0

Test 10

Group: 1

Verdict: ACCEPTED

input
77

correct output
9
ADD
ADD
MUL
ADD
...

user output
9
ADD
ADD
MUL
ADD
...

Test 11

Group: 2

Verdict: ACCEPTED

input
941694

correct output
0

user output
0

Test 12

Group: 2

Verdict:

input
905674

correct output
30
MUL
ADD
MUL
ADD
...

user output
(empty)

Test 13

Group: 2

Verdict:

input
908426

correct output
29
ADD
MUL
ADD
MUL
...

user output
(empty)

Test 14

Group: 2

Verdict:

input
960500

correct output
31
ADD
ADD
MUL
MUL
...

user output
(empty)

Test 15

Group: 2

Verdict:

input
902101

correct output
27
MUL
ADD
MUL
ADD
...

user output
(empty)

Test 16

Group: 2

Verdict:

input
994208

correct output
27
ADD
ADD
MUL
MUL
...

user output
(empty)

Test 17

Group: 2

Verdict: ACCEPTED

input
923538

correct output
0

user output
0

Test 18

Group: 2

Verdict:

input
950287

correct output
24
MUL
ADD
MUL
ADD
...

user output
(empty)

Test 19

Group: 2

Verdict:

input
950516

correct output
29
ADD
ADD
MUL
MUL
...

user output
(empty)

Test 20

Group: 2

Verdict: ACCEPTED

input
921882

correct output
0

user output
0

Test 21

Group: 3

Verdict:

input
933942296856681219

correct output
0

user output
(empty)

Error:
Exception in thread "main" java.lang.NumberFormatException: For input string: "933942296856681219"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
	at java.lang.Integer.parseInt(Integer.java:583)
	at java.lang.Integer.parseInt(Integer.java:615)
	at Program2.main(Program2.java:18)

Test 22

Group: 3

Verdict:

input
955775764385016720

correct output
0

user output
(empty)

Error:
Exception in thread "main" java.lang.NumberFormatException: For input string: "955775764385016720"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
	at java.lang.Integer.parseInt(Integer.java:583)
	at java.lang.Integer.parseInt(Integer.java:615)
	at Program2.main(Program2.java:18)

Test 23

Group: 3

Verdict:

input
981578916796073406

correct output
0

user output
(empty)

Error:
Exception in thread "main" java.lang.NumberFormatException: For input string: "981578916796073406"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
	at java.lang.Integer.parseInt(Integer.java:583)
	at java.lang.Integer.parseInt(Integer.java:615)
	at Program2.main(Program2.java:18)

Test 24

Group: 3

Verdict:

input
927875200723222396

correct output
94
MUL
ADD
MUL
MUL
...

user output
(empty)

Error:
Exception in thread "main" java.lang.NumberFormatException: For input string: "927875200723222396"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
	at java.lang.Integer.parseInt(Integer.java:583)
	at java.lang.Integer.parseInt(Integer.java:615)
	at Program2.main(Program2.java:18)

Test 25

Group: 3

Verdict:

input
990125206148420558

correct output
84
ADD
MUL
ADD
MUL
...

user output
(empty)

Error:
Exception in thread "main" java.lang.NumberFormatException: For input string: "990125206148420558"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
	at java.lang.Integer.parseInt(Integer.java:583)
	at java.lang.Integer.parseInt(Integer.java:615)
	at Program2.main(Program2.java:18)

Test 26

Group: 3

Verdict:

input
964804802247123102

correct output
0

user output
(empty)

Error:
Exception in thread "main" java.lang.NumberFormatException: For input string: "964804802247123102"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
	at java.lang.Integer.parseInt(Integer.java:583)
	at java.lang.Integer.parseInt(Integer.java:615)
	at Program2.main(Program2.java:18)

Test 27

Group: 3

Verdict:

input
996610423667404231

correct output
96
MUL
ADD
MUL
ADD
...

user output
(empty)

Error:
Exception in thread "main" java.lang.NumberFormatException: For input string: "996610423667404231"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
	at java.lang.Integer.parseInt(Integer.java:583)
	at java.lang.Integer.parseInt(Integer.java:615)
	at Program2.main(Program2.java:18)

Test 28

Group: 3

Verdict:

input
948665008088793691

correct output
86
MUL
ADD
MUL
ADD
...

user output
(empty)

Error:
Exception in thread "main" java.lang.NumberFormatException: For input string: "948665008088793691"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
	at java.lang.Integer.parseInt(Integer.java:583)
	at java.lang.Integer.parseInt(Integer.java:615)
	at Program2.main(Program2.java:18)

Test 29

Group: 3

Verdict:

input
969397787818953279

correct output
0

user output
(empty)

Error:
Exception in thread "main" java.lang.NumberFormatException: For input string: "969397787818953279"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
	at java.lang.Integer.parseInt(Integer.java:583)
	at java.lang.Integer.parseInt(Integer.java:615)
	at Program2.main(Program2.java:18)

Test 30

Group: 3

Verdict:

input
918471787211371085

correct output
90
ADD
MUL
ADD
MUL
...

user output
(empty)

Error:
Exception in thread "main" java.lang.NumberFormatException: For input string: "918471787211371085"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
	at java.lang.Integer.parseInt(Integer.java:583)
	at java.lang.Integer.parseInt(Integer.java:615)
	at Program2.main(Program2.java:18)