Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
5.1 kB
4
Indexable
Never
Prime Ring
Một vòng gồm N phần tử hình tròn. Trong mỗi hình tròn sẽ chứa một số nguyên P và tổng hai số nguyên trong hai hình tròn cạnh nhau trên vòng tròn tạo thành một số nguyên tố. Nhiệm vụ của bạn là với một chuỗi gồm N phần tử số nguyên, đưa ta tổng số cách xếp N phần tử đó vào vòng tròn thỏa mãn yêu cầu trên.

 

Ví dụ

Ta có đầu vào là một dãy gồm 6 phần tử: 1, 2, 3, 4, 5, 6. Thì đầu ra sẽ có 2 cách xếp là cách 1: 1 - 4 - 3 - 2 - 5 - 6 và cách 2: 1 - 6 - 5 - 2 -  3 - 4





Cách 1: 1 - 4 - 3 - 2 - 5 - 6

 

Input

Dòng đầu liên là T chính là số testcase (T ≤ 100). Mỗi testcase sẽ bao gồm 2 dòng:

Dòng đầu tiên là N chính là số lượng phần tử các số nguyên. (3 ≤ N ≤ 16)\

Dòng thứ hai là một dãy gồm N số nguyên P ( 1 ≤ P ≤ 50)

 

Output

Kết quả được in ra trên một dòng theo định sạng sau: “Case number_testcase: answer”

 

Sample

Input

2

8

1 2 3 4 5 6 7 8

6

1 2 3 4 5 6

 

 

Output

Case 1: 4

Case 2: 2

#include <stdio.h>

int arr[17];
bool selected[17];
int N, E;

bool isPrime[101];

void sieve()
{
	for (int i = 0; i < 101; i++)
		isPrime[i] = true;
	isPrime[0] = isPrime[1] = true;
	for (int i = 2; i < 101; i++) {
		if (isPrime[i])
			for (int j = i * 2; j < 101; j += i)
				isPrime[j] = false;
	}
}

int cnt;
void go(int k, int i) {
	if (k == N) {
		if (isPrime[arr[0] + arr[i]])
			cnt++;
		return;
	}
	for (int j = 1; j < N; j++) {
		if (!selected[j] && isPrime[arr[i] + arr[j]]) {
			selected[j] = true;
			go(k + 1, j);
			selected[j] = false;
		}
	}
}


int main()
{
	int T, tc;
	//freopen("primering_input.txt", "r", stdin);
	scanf("%d", &T);
	sieve();
	for (tc = 1; tc <= T; tc++) {
		scanf("%d", &N);
		for (int i = 0; i < N; i++) {
			scanf("%d", &arr[i]);
		}
		cnt = 0;
		selected[0] = true;
		go(1, 0);
		printf("Case %d: %d\n", tc, cnt);

	}

	return 0;
}

100
3
1 2 3 
4
1 2 3 4 
5
1 2 3 4 5 
6
1 2 3 4 5 6 
7
1 2 3 4 5 6 7 
8
1 2 3 4 5 6 7 8 
9
1 2 3 4 5 6 7 8 9 
10
1 2 3 4 5 6 7 8 9 10 
11
1 2 3 4 5 6 7 8 9 10 11 
12
1 2 3 4 5 6 7 8 9 10 11 12 
13
1 2 3 4 5 6 7 8 9 10 11 12 13 
14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 
15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
16
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 
9
3 4 5 6 7 8 9 10 11 
6
7 8 9 10 11 12 
15
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 
15
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
10
8 9 10 11 12 13 14 15 16 17 
16
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 
10
4 5 6 7 8 9 10 11 12 13 
16
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
14
9 10 11 12 13 14 15 16 17 18 19 20 21 22 
12
7 8 9 10 11 12 13 14 15 16 17 18 
13
6 7 8 9 10 11 12 13 14 15 16 17 18 
15
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
8
9 10 11 12 13 14 15 16 
9
8 9 10 11 12 13 14 15 16 
4
9 10 11 12 
4
11 12 13 14 
10
5 6 7 8 9 10 11 12 13 14 
8
12 13 14 15 16 17 18 19 
14
7 8 9 10 11 12 13 14 15 16 17 18 19 20 
6
4 5 6 7 8 9 
7
6 7 8 9 10 11 12 
8
7 8 9 10 11 12 13 14 
10
4 5 6 7 8 9 10 11 12 13 
4
11 12 13 14 
14
7 8 9 10 11 12 13 14 15 16 17 18 19 20 
3
10 11 12 
6
12 13 14 15 16 17 
4
4 5 6 7 
8
11 12 13 14 15 16 17 18 
13
8 9 10 11 12 13 14 15 16 17 18 19 20 
3
5 6 7 
11
9 10 11 12 13 14 15 16 17 18 19 
13
5 6 7 8 9 10 11 12 13 14 15 16 17 
3
11 12 13 
9
8 9 10 11 12 13 14 15 16 
3
12 13 14 
13
3 4 5 6 7 8 9 10 11 12 13 14 15 
15
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 
8
11 12 13 14 15 16 17 18 
4
6 7 8 9 
7
7 8 9 10 11 12 13 
13
3 4 5 6 7 8 9 10 11 12 13 14 15 
13
9 10 11 12 13 14 15 16 17 18 19 20 21 
4
11 12 13 14 
7
12 13 14 15 16 17 18 
3
6 7 8 
10
11 12 13 14 15 16 17 18 19 20 
7
5 6 7 8 9 10 11 
14
4 5 6 7 8 9 10 11 12 13 14 15 16 17 
6
8 9 10 11 12 13 
8
11 12 13 14 15 16 17 18 
13
3 4 5 6 7 8 9 10 11 12 13 14 15 
8
9 10 11 12 13 14 15 16 
8
9 10 11 12 13 14 15 16 
12
8 9 10 11 12 13 14 15 16 17 18 19 
5
5 6 7 8 9 
15
12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 
12
6 7 8 9 10 11 12 13 14 15 16 17 
4
5 6 7 8 
7
3 4 5 6 7 8 9 
8
9 10 11 12 13 14 15 16 
14
10 11 12 13 14 15 16 17 18 19 20 21 22 23 
12
7 8 9 10 11 12 13 14 15 16 17 18 
16
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
11
3 4 5 6 7 8 9 10 11 12 13 
4
7 8 9 10 
11
3 4 5 6 7 8 9 10 11 12 13 
16
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 
6
10 11 12 13 14 15 
4
10 11 12 13 
8
6 7 8 9 10 11 12 13 
10
12 13 14 15 16 17 18 19 20 21 
12
11 12 13 14 15 16 17 18 19 20 21 22 
4
11 12 13 14 
13
9 10 11 12 13 14 15 16 17 18 19 20 21 
13
3 4 5 6 7 8 9 10 11 12 13 14 15 
8
11 12 13 14 15 16 17 18 
7
4 5 6 7 8 9 10 
5
8 9 10 11 12 
11
12 13 14 15 16 17 18 19 20 21 22 
5
10 11 12 13 14 
5
6 7 8 9 10 
4
4 5 6 7 
7
3 4 5 6 7 8 9 
4
9 10 11 12