Prime Ring
quoc14
c_cpp
18 days ago
6.8 kB
5
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; }
Leave a Comment