import java.util.Scanner;
public class Solution {
static int n,a[]=new int[16],b[]=new int[16];
static int count;
static boolean matric[][]=new boolean[16][16],visit[]=new boolean[16];
private static Scanner sc;
static boolean ktnt(int x)
{
if(x<2) return false;
for(int i=2;i<=x/2;i++)
if(x%i==0)return false;
return true;
}
static void Try(int step)
{
if(step>=n-1){
if(matric[b[step]][0]==true){
count++;
return;
}
}
else for(int i=1;i<n;i++)
if(matric[i][b[step]]==true && visit[i]==false)
{
b[step+1]=i;
visit[i]=true;
Try(step+1);
visit[i]=false;
}
}
public static void main(String[] args) {
sc = new Scanner(System.in);
int T=sc.nextInt();
for(int tc=1;tc<=T;tc++)
{
n=sc.nextInt();
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
visit[i]=false;
}
visit[0]=true;
b[0]=0;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
matric[i][j]=ktnt(a[i]+a[j]);
count=0;
Try(0);
System.out.println("Case "+tc+": "+count);
}
}
}
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
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
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.