CSES - Putka Open 2020 – 2/5

Submission details
Task:	Summat
Sender:	TapaniS
Submission time:	2020-09-27 18:39:57 +0300
Language:	Java
Status:	READY
Result:	12

Feedback
group	verdict	score
#1	ACCEPTED	12
#2	TIME LIMIT EXCEEDED	0
#3	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.17 s	1, 2, 3	details
#2	ACCEPTED	0.17 s	1, 2, 3	details
#3	ACCEPTED	0.17 s	1, 2, 3	details
#4	ACCEPTED	0.17 s	1, 2, 3	details
#5	ACCEPTED	0.17 s	1, 2, 3	details
#6	ACCEPTED	0.18 s	2, 3	details
#7	ACCEPTED	0.20 s	2, 3	details
#8	ACCEPTED	0.21 s	2, 3	details
#9	TIME LIMIT EXCEEDED	--	2, 3	details
#10	ACCEPTED	0.21 s	2, 3	details
#11	ACCEPTED	0.27 s	3	details
#12	ACCEPTED	0.91 s	3	details
#13	TIME LIMIT EXCEEDED	--	3	details
#14	TIME LIMIT EXCEEDED	--	3	details
#15	TIME LIMIT EXCEEDED	--	3	details

Code

import java.util.*;

public class summat {

	private static int[] findAnswer(int[] arr, List<Integer> eList, int aqty, int maxsum, int round) {

		int[] storeArr = new int[round-1];

		if (round > aqty) {
			arr[aqty] = 0;
			return arr;
		}

		if (arr[aqty] == 1) return arr;

		List<Integer> dList = new ArrayList<>(eList);
		boolean okAns = false;

		for (int kn = 1; kn < maxsum; kn++) {

			dList = new ArrayList<>(eList);
			boolean ok = true;

			for (int i = 0; i < (round-1); i++) {
				if (!dList.contains(kn+arr[i])) {
					ok = false;
				}
			}

			if (ok) {

			  for (int i = 0; i < (round-1); i++) {
				if (dList.contains(kn+arr[i])) {

					storeArr[i] = kn+arr[i];
					dList.remove(Integer.valueOf(kn+arr[i]));	

				}
				else {
					ok = false;
				}
			  }


			}

			if (ok) {

				arr[round-1] = kn;

				if (round == aqty) {
					arr[round] = 1;
					okAns = true;
					return arr;
				}

				arr = findAnswer(arr, dList, aqty, maxsum, round+1);

				if (arr[aqty] > 0) {break;}

//				dList = new ArrayList<>(eList);
				for (int i = 0; i < (round-1); i++) {
					dList.add(storeArr[i]);
				}
			}

			else {
				dList = new ArrayList<>(eList);
			}
		}

		return arr;

	}



	public static void main(String[] args) {

		Scanner input = new Scanner(System.in);

		int aqty = input.nextInt();
		int bqty = aqty * (aqty - 1) / 2;

		int[] b = new int[bqty];
		int[] c = new int[bqty];
		int[] ans = new int[aqty+1];

		for (int i = 0; i < bqty; i++) {
			b[i] = input.nextInt();
		}

		Arrays.sort(b);

		List<Integer> cList = new ArrayList<Integer>(b.length);
		for (int i : b) {
			cList.add(i);
			}

		int maxsum = b[bqty-1];

		int allOk = 0;
		List<Integer> dList = new ArrayList<>(cList);

		for (int k1 = 1; k1 < maxsum; k1++) {
			
			if (allOk > 0) break;

			ans[0] = k1;

			for (int k2 = 1; k2 < maxsum; k2++) {

				if (dList.contains(k1+k2)) {

					ans[1] = k2;
					dList.remove(Integer.valueOf(k1+k2));

					ans = findAnswer(ans, dList, aqty, maxsum, 3);

					if (ans[aqty] > 0) {
						allOk = 1;
						break;
						}
					else {
						dList.add(k1+k2);
					}
				}
			}
		}


		for (int i = 0; i < (aqty-1); i++) {

			System.out.print(ans[i] + " ");
		}
		System.out.println(ans[aqty-1]);
		input.close(); 
    }
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
`5 2 2 2 2 2 2 2 2 2 2` view save

correct output
`1 1 1 1 1` view save

user output
`1 1 1 1 1` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`5 3 4 5 5 6 6 7 7 8 9` view save

correct output
`1 2 3 4 5` view save

user output
`1 2 3 4 5` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`5 5 6 6 6 9 9 9 10 10 10` view save

correct output
`1 4 5 5 5` view save

user output
`1 4 5 5 5` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`5 2 3 3 6 6 6 6 7 7 10` view save

correct output
`1 1 2 5 5` view save

user output
`1 1 2 5 5` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`5 4 5 5 5 5 6 6 6 7 7` view save

correct output
`2 2 3 3 4` view save

user output
`2 2 3 3 4` view save

Test 6

Group: 2, 3

Verdict: ACCEPTED

input
`20 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...` view save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

Test 7

Group: 2, 3

Verdict: ACCEPTED

input
`20 3 4 5 5 6 6 7 7 7 8 8 8 9 9 9 ...` view save

correct output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

Test 8

Group: 2, 3

Verdict: ACCEPTED

input
`20 52 55 55 57 62 62 63 64 66 71 ...` view save

correct output
`1 51 54 54 56 61 61 62 63 65 7...` view save

user output
`1 51 54 54 56 61 61 62 63 65 7...` view save

Test 9

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`20 25 30 31 32 36 39 40 41 45 45 ...` view save

correct output
`8 17 22 23 24 28 43 50 53 55 6...` view save

user output
(empty)

Test 10

Group: 2, 3

Verdict: ACCEPTED

input
`20 9 10 14 17 17 20 21 22 24 25 2...` view save

correct output
`1 8 9 13 16 19 30 32 38 40 43 ...` view save

user output
`1 8 9 13 16 19 30 32 38 40 43 ...` view save

Test 11

Group: 3

Verdict: ACCEPTED

input
`100 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...` view save

correct output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` view save

user output
`1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...` Truncated

Test 12

Group: 3

Verdict: ACCEPTED

input
`100 3 4 5 5 6 6 7 7 7 8 8 8 9 9 9 ...` view save

correct output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
`1 2 3 4 5 6 7 8 9 10 11 12 13 ...` Truncated

Test 13

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100 502824619 505239810 505668108 ...` view save

correct output
`1 502824618 505239809 50566810...` view save

user output
(empty)

Test 14

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100 17871832 41618648 51611938 538...` view save

correct output
`3939271 13932561 37679377 4989...` view save

user output
(empty)

Test 15

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`100 70588435 115481965 116040218 1...` view save

correct output
`5902586 64685849 109579379 110...` view save

user output
(empty)

Putka Open 2020 – 2/5

Summat

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Tasks

Submissions (TapaniS)