Prime Ring

quoc14
c_cpp
18 days ago
6.8 kB
Indexable
Never
Backtrack
evel 4
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

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


Case 1: 0
Case 2: 2
Case 3: 0
Case 4: 2
Case 5: 0
Case 6: 4
Case 7: 0
Case 8: 96
Case 9: 0
Case 10: 1024
Case 11: 0
Case 12: 2880
Case 13: 0
Case 14: 81024
Case 15: 1320
Case 16: 0
Case 17: 2
Case 18: 0
Case 19: 0
Case 20: 4
Case 21: 1320
Case 22: 32
Case 23: 2020
Case 24: 148
Case 25: 8
Case 26: 0
Case 27: 0
Case 28: 0
Case 29: 0
Case 30: 0
Case 31: 0
Case 32: 6
Case 33: 2
Case 34: 64
Case 35: 2
Case 36: 0
Case 37: 0
Case 38: 32
Case 39: 0
Case 40: 64
Case 41: 0
Case 42: 0
Case 43: 0
Case 44: 2
Case 45: 0
Case 46: 0
Case 47: 0
Case 48: 0
Case 49: 0
Case 50: 0
Case 51: 0
Case 52: 0
Case 53: 0
Case 54: 2
Case 55: 0
Case 56: 0
Case 57: 0
Case 58: 0
Case 59: 0
Case 60: 0
Case 61: 0
Case 62: 2
Case 63: 0
Case 64: 368
Case 65: 0
Case 66: 2
Case 67: 0
Case 68: 0
Case 69: 0
Case 70: 12
Case 71: 0
Case 72: 0
Case 73: 48
Case 74: 0
Case 75: 0
Case 76: 0
Case 77: 64
Case 78: 8
Case 79: 2020
Case 80: 0
Case 81: 0
Case 82: 0
Case 83: 5172
Case 84: 0
Case 85: 0
Case 86: 2
Case 87: 0
Case 88: 12
Case 89: 0
Case 90: 0
Case 91: 0
Case 92: 2
Case 93: 0
Case 94: 0
Case 95: 0
Case 96: 0
Case 97: 0
Case 98: 0
Case 99: 0
Case 100: 0
Time: 0.463000000 s.

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
    #include <iostream>
#include <time.h>
using namespace std;

int oo = 2000000000;

int T, n, arr[16], result, vs[16], path[16];

bool isPrime[100];

bool checkPrime(int t){
	for(int i = 2; i*i <= t; i++){
		if(t%i == 0) return false;
	}
	return true;
}

void updatePrimeArr(){
	isPrime[2] = true;
	for(int i = 3; i < 100; i+= 2){
		if(checkPrime(i)) isPrime[i] = true;
	}
}

void backtrack(int index, int head, int curr, int prev){
	if(prev != -1 && !isPrime[arr[curr] + arr[prev]]) return;

	if(index == n){
		if(isPrime[arr[head] + arr[curr]]) result++;
		return;
	}

	
	
	for(int i = 0; i < n; i++){
		if(!vs[i]){
			// vsTrue
			vs[i]++;

			path[index] = i;
			backtrack(index + 1, head, i, curr);

			// vsFalse
			vs[i]--;
		}
	}
}

int main(){
	freopen("input.txt", "r", stdin);

	// Calc clock
	
	clock_t time_start, time_end; 
	time_start = clock(); 
	
	updatePrimeArr();
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		// Initial && Input
		cin >> n;
		for(int i = 0; i < n; i++){
			cin >> arr[i];
			vs[i] = 0;
		}
		result = 0;

		// Solve Problem
		vs[0]++;
		path[0] = 0;
		backtrack(1, 0, 0, -1);
		
		// Output
		cout << "Case " << tc << ": " << result << endl;
	}

	// Calc Time
	
	time_end = clock();
	cout.setf(ios::fixed);
	cout.precision(9);
	cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl;
	
	return 0;
 }