Untitled
unknown
plain_text
2 years ago
5.1 kB
8
Indexable
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 12Editor is loading...