Untitled

 avatar
unknown
plain_text
a year ago
14 kB
5
Indexable
<dd><p style="margin: 0in 0in 0pt; text-align: justify; line-height: 115%; -ms-text-justify: inter-ideograph;"><span style="line-height: 115%; mso-fareast-font-family: &quot;Times New Roman&quot;; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">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.</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; text-align: justify; line-height: 115%; -ms-text-justify: inter-ideograph;"><span style="line-height: 115%; mso-fareast-font-family: &quot;Times New Roman&quot;; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">&nbsp;</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><b style="mso-bidi-font-weight: normal;"><span style="line-height: 115%; mso-fareast-font-family: &quot;Times New Roman&quot;; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">Ví dụ</font></span></b></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><font face="Times New Roman"><span style="line-height: 115%; mso-fareast-font-family: &quot;Times New Roman&quot;; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" size="3">Ta có đầu vào là một dãy gồm 6 phần tử: </font><b style="mso-bidi-font-weight: normal;"><font color="#000000" size="3">1, 2, 3, 4, 5, 6</font></b><font color="#000000" size="3">. Thì đầu ra sẽ có 2 cách xếp là cách 1: </font></span><b style="mso-bidi-font-weight: normal;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" size="3">1 - 4 - 3 - 2 - 5 - 6</font></span></b><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" size="3"> và cách 2: </font><b style="mso-bidi-font-weight: normal;"><font color="#000000" size="3">1 - 6 - 5 - 2 - </font><span style="mso-spacerun: yes;"><font color="#000000" size="3">&nbsp;</font></span><font color="#000000" size="3">3 - 4</font></b></span></font></p><font color="#000000" face="Times New Roman" size="3"></font><p align="center" style="margin: 0in 0in 0pt; text-align: center; line-height: 115%;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-no-proof: yes; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3"><br></font></span></p><p align="center" style="margin: 0in 0in 0pt; text-align: center; line-height: 115%;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-no-proof: yes; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3"><img src="/uploadimage/2016121911478202_e1c2oK9S9Ly_R7FIze3XF1uew...png" border="0"></font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p align="center" style="margin: 0in 0in 0pt; text-align: center; line-height: 115%;"><font face="Times New Roman"><i style="mso-bidi-font-style: normal;"><span style="line-height: 115%; mso-fareast-font-family: &quot;Times New Roman&quot;; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" size="3">Cách 1: </font></span></i><b style="mso-bidi-font-weight: normal;"><i style="mso-bidi-font-style: normal;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" size="3">1 - 4 - 3 - 2 - 5 - 6</font></span></i></b></font></p><font color="#000000" face="Times New Roman" size="3"></font><p align="center" style="margin: 0in 0in 0pt; text-align: center; line-height: 115%;"><b style="mso-bidi-font-weight: normal;"><i style="mso-bidi-font-style: normal;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">&nbsp;</font></span></i></b></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><b style="mso-bidi-font-weight: normal;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">Input</font></span></b></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">Dòng đầu liên là T chính là số testcase (T ≤ 100). Mỗi testcase sẽ bao gồm 2 dòng:</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">Dòng đầu tiên là N chính là số lượng phần tử các số nguyên. (3 ≤ N ≤ 16)\</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">Dòng thứ hai là một dãy gồm N số nguyên P ( 1 ≤ P ≤ 50</font><a name="_GoBack"></a><font color="#000000" face="Times New Roman" size="3">)</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><b style="mso-bidi-font-weight: normal;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">&nbsp;</font></span></b></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><b style="mso-bidi-font-weight: normal;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">Output</font></span></b></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font face="Times New Roman"><font color="#000000" size="3">Kết quả được in ra trên một dòng theo định sạng sau: “</font><b style="mso-bidi-font-weight: normal;"><font color="#000000" size="3">Case </font></b><i style="mso-bidi-font-style: normal;"><font color="#000000" size="3">number_testcase</font></i><b style="mso-bidi-font-weight: normal;"><font color="#000000" size="3">: </font></b><i style="mso-bidi-font-style: normal;"><font color="#000000" size="3">answer</font></i><font color="#000000" size="3">”</font></font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><span style="line-height: 115%; mso-fareast-font-family: &quot;Times New Roman&quot;; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">&nbsp;</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><b><span lang="VI" style="line-height: 115%; mso-fareast-font-family: DotumChe; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt; mso-ansi-language: VI;"><font color="#000000" face="Times New Roman" size="3">Sample</font></span></b></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><b><span style="line-height: 115%; mso-fareast-font-family: DotumChe; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">Input</font></span></b></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><span style="line-height: 115%; mso-fareast-font-family: DotumChe; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">2</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><span style="line-height: 115%; mso-fareast-font-family: DotumChe; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">8</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><span style="line-height: 115%; mso-fareast-font-family: DotumChe; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">1 2 3 4 5 6 7 8</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><span style="line-height: 115%; mso-fareast-font-family: DotumChe; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">6</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><span style="line-height: 115%; mso-fareast-font-family: DotumChe; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">1 2 3 4 5 6</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%; mso-layout-grid-align: none;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">&nbsp;</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><b><span style="line-height: 115%; mso-fareast-font-family: DotumChe; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">&nbsp;</font></span></b></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%;"><b><span style="line-height: 115%; mso-fareast-font-family: DotumChe; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">Output</font></span></b></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%; mso-layout-grid-align: none;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">Case 1: 4</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><p style="margin: 0in 0in 0pt; line-height: 115%; mso-layout-grid-align: none;"><span style="line-height: 115%; mso-bidi-font-family: &quot;Times New Roman&quot;; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3">Case 2: 2</font></span></p><font color="#000000" face="Times New Roman" size="3"></font><br></dd>
package Buoi28.prime_ring;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {

	static int N;
	static int[] arr;
	static int[] visited;
	static int[] choose;

	static int count;

	public static void input(Scanner sc) {
		N = sc.nextInt();
		arr = new int[N];
		visited = new int[N];
		choose = new int[N];
		count = 0;
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
		}
	}

	public static boolean isCheckNguyenTo(int x) {
		for (int i = 2; i <= Math.sqrt(x); i++) {
			if (x % i == 0) {
				return false;
			}
		}
		return true;
	}

	public static void backtrack(int k) {
		if (k == N) {
			if (isCheckNguyenTo(choose[N - 1] + choose[0])) {
				count++;
			}
			return;
		}
		for (int i = 0; i < N; i++) {
			if (visited[i] == 0
					&& isCheckNguyenTo(choose[k - 1] + arr[i])) {
				visited[i] = 1;
				choose[k] = arr[i];
				backtrack(k + 1);
				visited[i] = 0;
				choose[k] = 0;
			}
		}
	}

	public static void solve() {
		choose[0] = arr[0];
		visited[0] = 1;
		backtrack(1);
	}

	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		long start = System.currentTimeMillis();
		System.setIn(new FileInputStream("input.txt"));
		Scanner sc = new Scanner(System.in);
		int T;
		T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			input(sc);
			System.out.print("Case " + test_case+": ");
			solve();
			System.out.println(count);
		}
		long end = System.currentTimeMillis();
		System.out.println((double) (end - start) / 1000);
	}
}
Editor is loading...