Untitled
unknown
plain_text
a year ago
6.2 kB
6
Indexable
Tổng hợp lại
Cho Một tổng t đã xác định và một danh sách n số nguyên, tìm tất cả các tổng riêng biệt bằng cách sử dụng Các số từ danh sách cộng lại với T. Ví dụ: nếu t = 4, n = 6 và danh sách là [4, 3, 2, 2, 1, 1], sau đó 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 như nó xuất hiện trong danh sách và một num ber duy nhất đượ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 nói chung.
Nhập
Các Tệp đầu vào sẽ chứa một hoặc nhiều trường hợp kiểm thử, một trường hợp trên mỗi dòng. Mỗi trường hợp kiểm thử chứa tổng, tiếp theo là n, số nguyên trong danh sách, tiếp theo là n Số nguyên x1, . . . ,xn. t sẽ là một số nguyên dương nhỏ hơn 1000, n sẽ là Một số nguyên từ 1 đến 12 (bao gồm) và x1, . . . , xn sẽ dương số nguyên nhỏ hơn 100. Tất cả các số sẽ được phân tách bằng chính xác một khoảng trắng. Các Các số trong mỗi danh sách có thể là sự lặp lại.
Ra
Cho Mỗi trường hợp kiểm thử, xuất ra tổng cách, nếu không phải là đầu ra -1.
Mẫu
Nhập
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
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
package Tong_Hop_Lai;
import java.io.FileInputStream;
import java.util.Scanner;
public class Solution {
static int sum, n;
static int[] a;
static int dem;
static int[] res;
static int[] ts;
static int[] b;
static int[] visit;
static int m;
public static void main(String args[]) throws Exception{
System.setIn(new FileInputStream("src/Tong_Hop_Lai/input.txt"));
Scanner sc = new Scanner(System.in);
int T;
int Answer;
T=sc.nextInt();
for(int test_case = 1; test_case <= T; test_case++){
sum = sc.nextInt();
n = sc.nextInt();
a = new int[n];
res = new int[n];
ts = new int[105];
b = new int[n];
visit = new int[105];
for(int i = 0; i < n; i++){
a[i] = sc.nextInt();
}
m = 0;
for(int i = 0; i < n; i++){
if(visit[a[i]] == 0){
visit[a[i]] = 1;
b[m] = a[i];
m++;
}
ts[a[i]]++;
}
for(int i = 0; i < m; i++){
System.out.println(b[i] + " " + ts[b[i]]);
}
dem = 0;
Try(0,0,0,0);
System.out.println(dem);
}
}
public static void Try(int k, int cnt, int u, int start){
if(cnt > sum){
return;
}
if(u == n){
if(cnt == sum){
dem++;
}
return;
}
if(cnt < sum){
for(int i = start; i < ts[b[k]]; i++){
Try(k,cnt+b[k],u+1,start+1);
}
}else{
Try(k+1,cnt+b[k],u+1,start+1);
}
Try(k+1, cnt, u+1, 0);
}
}
The Settlers of Catan
Settlers of Catan, một trò chơi của người Đức ở năm 1995, người chơi tham gia vào cuộc cai trị một hòn đảo bằng việc xây dựng các con đường, các khu định cư, và các thành phố qua các vùng hoang dã chưa được thám hiểm.
Bạn được một công ty phần mềm thuê để phát triển một phiên bản máy tính cho trò chơi này, và bạn được chọn để xây dựng một trong các luật đặc biệt của trò chơi.
Khi trò chơi kết thúc, người chơi mà xây dựng được con đường dài nhất sẽ được thêm 2 điểm thắng cuộc.
Vấn đề gặp phải ở đây là người chơi thường xây dựng các mạng lưới con đường rất phức tạp và không chỉ theo một đường tuyến tính. Vì lý do đó, việc xác định con đường dài nhất không phải đơn giản (mặc dù những người chơi thường có thể thấy ngay lập tức).
Đối chiếu tới trò chơi gốc, chúng ta sẽ giải quyết một vấn đề đơn giản ở đây: Bạn được cho trước một tập các nodes (thành phố) và một tập các cạnh (các đoạn đường) có chiều dài là 1 kết nối các nodes.
Con đường dài nhất được định nghĩa như là đường đi dài nhất trong mạng lưới đường mà không có cạnh nào được dử dụng hai lần. Dù vậy, các nodes có thể được thăm hơn một lần.
Ví dụ: Mạng lưới sau đây chứa một con đường dài nhất là 12.
Input
Input sẽ chứa một hoặc nhiều test cases.
Dòng đầu là số lượng test case T.
Dòng đầu tiên của mỗi test cases chứa 2 số nguyên: số nodes N (2<=N<=25) và số cạnh M (1<=M<=25). M dòng tiếp theo miêu tả M cạnh. Mỗi cạnh được cho bởi các số node kết nối với nhau. Các node được đánh số từ 0 -> N-1. Các cạnh không có hướng. Các node có bậc là 3 hoặc nhỏ hơn. Mạng lưới không cần thiết phải được kết nối thông suốt với nhau.
Output
Với mỗi test case, in ra chiều dài của con đường dài nhất trên một dòng.
Sample
Input
3
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
3 2
0 1
1 2
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
Output
12
2
12