Untitled
unknown
plain_text
2 years ago
4.1 kB
4
Indexable
Cho một tổng cụ thể t và một danh sách n số nguyên, tìm tất cả các tổng khác nhau bằng cách sử dụng các số từ danh sách có tổng bằng t. Ví dụ: nếu t = 4, n = 6 và danh sách là [4, 3, 2, 2, 1, 1], thì có bốn tổng khác nhau bằng 4: 4, 3+1, 2+2, và 2+1+1. (Một số có thể được sử dụng trong một tổng nhiều lần khi nó xuất hiện trong danh sách và một số duy nhấtber được tính là một tổng.) Công việc của bạn là giải quyết vấn đề này một cách tổng quát. Đầu vào Tệp đầu vào sẽ chứa một hoặc nhiều trường hợp thử nghiệm, mỗi trường hợp trên một dòng. Mỗi trường hợp thử nghiệm chứa t, tổng số, theo sau là n, số lượng các số nguyên trong danh sách, theo sau là n số nguyên x1, . . . ,xn. t sẽ là số nguyên dương nhỏ hơn 1000, n sẽ là số nguyên từ 1 đến 12 (đã bao gồm) và x1, . . . , xn sẽ là các số nguyên dương nhỏ hơn 100. Tất cả các số sẽ cách nhau đúng một dấu cách. Các số trong mỗi danh sách có thể được lặp lại. đầu ra Đối với mỗi trường hợp kiểm tra, xuất ra tổng số cách, nếu không xuất ra -1. Vật mẫu Đầu vào 4 4 6 4 3 2 2 1 1 5 3 2 1 1 400 12 50 50 50 50 50 50 25 25 25 25 25 25 20 10 1 2 3 4 5 6 7 8 9 10 đầu ra #1 4 #2 -1 #3 2 #4 31 Giải thích #1 4 3+1 2+2 2+1+1 #3 50+50+50+50+50+50+25+25+25+25 50+50+50+50+50+25+25+25+25+25+25 #4 1+2+3+4+10 1+2+3+5+9 1+2+3+6+8 1+2+4+5+8 1+2+4+6+7 1+2+7+10 1+2+8+9 1+3+4+5+7 1+3+6+10 1+3+7+9 1+4+5+10 1+4+6+9 1+4+7+8 1+5+6+8 1+9+10 2+3+4+5+6 2+3+5+10 2+3+6+9 2+3+7+8 2+4+5+9 2+4+6+8 2+5+6+7 2+8+10 3+4+5+8 3+4+6+7 3+7+10 3+8+9 4+6+10 4+7+9 5+6+9 5+7+8 in 20 644 12 54 80 97 20 47 98 68 28 25 55 2 70 498 12 60 70 15 4 32 44 93 37 21 25 38 59 150 12 9 93 72 64 9 27 47 24 3 26 75 3 499 11 57 33 43 12 42 35 8 61 49 73 86 734 11 55 89 23 28 81 58 90 77 72 64 97 302 12 61 100 72 28 7 26 18 60 70 61 62 39 295 11 82 31 72 46 97 98 61 13 17 47 26 201 10 62 63 2 46 39 95 71 58 69 99 133 10 66 55 48 89 28 83 18 20 100 28 272 11 55 24 43 94 38 78 68 3 25 94 22 171 12 35 54 64 67 29 13 81 26 3 43 58 40 207 12 49 73 4 62 18 40 95 69 35 33 96 49 429 10 53 25 60 30 36 35 15 100 69 6 226 10 68 51 75 64 13 75 85 96 60 92 626 12 45 65 11 81 40 80 83 21 60 65 28 47 407 12 79 96 81 82 42 45 89 90 88 72 38 13 152 12 80 51 59 94 35 63 15 14 89 18 68 25 350 12 1 73 75 58 86 64 49 52 88 60 45 49 261 10 38 90 71 16 33 82 36 91 42 23 692 10 100 87 93 69 29 53 62 76 50 73 #include <iostream> using namespace std; int array[1001]; int so[1001]; int visit[1001]; int compare[100][100]; int k,n,result; int count1; int check (int a){ for(int i = 0; i < count1; i++){ int dem = 0; for(int j = 0; j < a; j++){ if(compare[i][j] == so[j]) dem++; else break; } if(dem == a) return 0; } return 1; } void backtrack(int a,int sum,int len){ if(sum == k){ if(check(len)){ for(int i = 0; i < len ; i++){ compare[count1][i] = so[i]; } count1 ++; result ++; } return; } if(sum > k || a >= n) return; for(int i = 0; i < 2; i++){ if(i == 0) backtrack( a + 1,sum,len); else{ so[len] = array[a]; backtrack(a + 1,sum + array[a],len+1); so[len] = 0; } } } int main(){ ///freopen("Text.txt","r",stdin); int T;cin >> T; for(int tc = 1; tc <= T; tc ++){ cin >> k >> n; for(int i = 0; i < n; i++){ cin >> array[i]; so[i] = 0; for(int j = 0; j < n; j++){ compare[i][j] = 0; } } result = 0; count1 = 0; backtrack(0,0,0); if(result != 0){ cout << "#" << tc << " " << result << endl; } else cout << "#" << tc << " " << -1 << endl; } return 0; }
Editor is loading...