Untitled
unknown
plain_text
2 years 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: "Times New Roman"; mso-bidi-font-family: "Times New Roman"; 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: "Times New Roman"; mso-bidi-font-family: "Times New Roman"; mso-bidi-font-size: 12.0pt;"><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-fareast-font-family: "Times New Roman"; mso-bidi-font-family: "Times New Roman"; 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: "Times New Roman"; mso-bidi-font-family: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; 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"> </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: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; mso-bidi-font-family: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3"> </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: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3"> </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: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; mso-bidi-font-family: "Times New Roman"; mso-bidi-font-size: 12.0pt;"><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><span lang="VI" style="line-height: 115%; mso-fareast-font-family: DotumChe; mso-bidi-font-family: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; mso-bidi-font-size: 12.0pt;"><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><span style="line-height: 115%; mso-fareast-font-family: DotumChe; mso-bidi-font-family: "Times New Roman"; mso-bidi-font-size: 12.0pt;"><font color="#000000" face="Times New Roman" size="3"> </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: "Times New Roman"; 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: "Times New Roman"; 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: "Times New Roman"; 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...