Bài tập Kỹ thuật lập trình hướng đối tượng - TS. Nguyễn Duy Phương cung cấp đến học viên các kiến thức bài tập dạng kỹ thuật lập trình với ngôn ngữ Java, bài tập lập trình Java cơ bản; lý thuyết tổ hợp; bài toán đếm, liệt kê, tối ưu; các mô hình thuật toán cơ bản, thuật toán tham lam, thuật toán chia và trị, thuật toán quy hoạch động; lý thuyết đồ thị; các cấu trúc dữ liệu cơ bản;... Mời các bạn cùng tham khảo!
KỸ THUẬT LẬP TRÌNH VỚI NGÔN NGỮ JAVA
Bài tập lập trình Java cơ bản
BÀI 1 ƯỚC SỐ CHUNG LỚN NHẤT VÀ BỘI SỐ CHUNG NHỎ NHẤT
Viết chương trình tìm ước số chung lớn nhất và bội số chung nhỏ nhất của hai số nguyên dương a,b
Dữ liệu vào: Dòng đầu ghi số bộ test Mỗi bộ test ghi trên một dòng 2 số nguyên a và b không quá 9 chữ số
Kết quả: Mỗi bộ test ghi trên 1 dòng, lần lượt là USCLN, sau đó đến BSCNN
BÀI 2 BẮT ĐẦU VÀ KẾT THÚC
Chương trình kiểm tra số nguyên dương có từ 2 đến 9 chữ số sẽ xác định xem chữ số đầu và chữ số cuối có giống nhau hay không Nếu hai chữ số này trùng khớp, kết quả trả về sẽ là "Có", ngược lại sẽ là "Không" Người dùng cần nhập một số nguyên dương hợp lệ để thực hiện kiểm tra.
Dữ liệu vào: Dòng đầu tiên ghi số bộ test Mỗi bộ test viết trên một dòng số nguyên dương tương ứng cần kiểm tra
Kết quả: Mỗi bộ test viết ra YES hoặc NO, tương ứng với bộ dữ liệu vào
Cho một phép toán có dạng a + b = c với a,b,c chỉ là các số nguyên dương có một chữ số Hãy kiểm tra xem phép toán đó có đúng hay không
Dữ liệu vào: Chỉ có một dòng ghi ra phép toán (gồm đúng 9 ký tự)
Kết quả: Ghi ra YES nếu phép toán đó đúng Ghi ra NO nếu sai
Nhiệm vụ của bạn là hãy xác định xem có bao nhiêu ước số của N chia hết cho 2?
Dữ liệu vào: Dòng đầu tiên là số lượng bộ test T (T ≤ 100) Mỗi bộ test gồm một số nguyên N
Kết quả: Với mỗi test, in ra đáp án tìm được trên một dòng
BÀI 5 ƯỚC SỐ NGUYÊN TỐ LỚN NHẤT
Cho số nguyên dương N Hãy đưa ra ước số nguyên tố lớn nhất của N
Dòng đầu tiên đưa vào số lượng bộ test T
Những dòng kế tiếp đưa vào T bộ test Mỗi bộ test ghi số nguyên dương N
Đưa ra kết quả mỗi test theo từng dòng
BÀI 6 KIỂM TRA SỐ FIBONACCI
Cho số nguyên dương n Hãy kiểm tra xem n có phải là số trong dãy Fibonacci hay không?
Dòng đầu tiên đưa vào số lượng bộ test T
Những dòng kế tiếp đưa vào các bộ test Mỗi bộ test là một số nguyên dương n
Đưa ra “YES” hoặc “NO” tương ứng với n là số Fibonacci hoặc không phải số Fibonacci của mỗi test theo từng dòng
BÀI 7 LIỆT KÊ VÀ ĐẾM
Trong một dãy số nguyên dương không quá 9 chữ số, mỗi số được phân cách bởi khoảng trống và có thể xuống dòng, nhiệm vụ là tìm các số không giảm, tức là các chữ số từ trái qua phải tạo thành một dãy không giảm Sau đó, cần đếm số lần xuất hiện của những số này trong dãy.
Dữ liệu vào: Gồm các số nguyên dương không quá 9 chữ số Không quá 100000 số
Kết quả ghi nhận các số không giảm kèm theo số lần xuất hiện của chúng Các số được sắp xếp theo thứ tự giảm dần của số lần xuất hiện, và trong trường hợp có các số có số lần xuất hiện bằng nhau, số nào xuất hiện trước sẽ được ưu tiên hiển thị trước.
Số tăng giảm là những số có chữ số sắp xếp theo thứ tự tăng dần hoặc giảm dần từ trái sang phải Bài viết này sẽ hướng dẫn cách đếm các số nguyên tố thuộc loại số tăng giảm với một số chữ số nhất định.
Dữ liệu đầu vào bao gồm số lượng bộ test ở dòng đầu tiên, tiếp theo mỗi bộ test sẽ được ghi trên một dòng riêng biệt với số chữ số cần kiểm tra, đảm bảo số lượng chữ số này lớn hơn 1 và nhỏ hơn 10.
Kết quả: Ghi ra số lượng các số thỏa mãn điều kiện
BÀI 9 PHÂN TÍCH THỪA SỐ NGUYÊN TỐ
Hãy phân tích một số nguyên dương thành tích các thừa số nguyên tố
Dữ liệu vào: Dòng đầu tiên ghi số bộ test Mỗi bộ test viết trên một dòng số nguyên dương n không quá 9 chữ số
Kết quả của mỗi bộ test được trình bày theo thứ tự, bao gồm các số nguyên tố khác nhau có trong tích, kèm theo số lượng của mỗi số Để hiểu rõ hơn về cách thức trình bày kết quả, bạn có thể tham khảo ví dụ minh họa.
Một số được xem là đẹp nếu nó có tính chất thuận nghịch và tổng các chữ số của nó chia hết cho 10 Bài toán đặt ra là, với một số lượng chữ số nhất định, hãy xác định số lượng các số đẹp có thể được tạo ra.
Dữ liệu đầu vào bao gồm số lượng bộ test, với mỗi bộ test được ghi trên một dòng, chứa số chữ số cần kiểm tra, với giá trị lớn hơn 1 và nhỏ hơn 10.
Kết quả: Mỗi bộ test viết ra số lượng số đẹp tương ứng
BÀI 11 SỐ THUẦN NGUYÊN TỐ
Số thuần nguyên tố được định nghĩa là số nguyên tố mà tất cả các chữ số của nó cũng là số nguyên tố, và tổng các chữ số đó cũng phải là một số nguyên tố Nhiệm vụ là đếm số lượng số thuần nguyên tố nằm trong khoảng giữa hai số nguyên cho trước.
Dữ liệu đầu vào bao gồm số lượng bộ test ở dòng đầu tiên, tiếp theo là các bộ test được ghi trên các dòng sau, mỗi bộ test gồm hai số nguyên dương cách nhau bởi một khoảng trống, với giá trị không vượt quá 9 chữ số.
Kết quả: Mỗi bộ test viết ra số lượng các số thuần nguyên tố tương ứng
Có ba hình chữ nhật và bạn có thể xoay chúng nhưng không được chồng lấn lên nhau Câu hỏi đặt ra là liệu ba hình chữ nhật này có thể ghép lại thành một hình vuông hay không.
Dữ liệu vào: Có ba dòng, mỗi dòng ghi hai số nguyên dương là chiều rộng và chiều cao của hình chữ nhật (các số đều không quá 100)
Kết quả: Ghi ra YES nếu có thể tạo thành hình vuông, NO nếu không thể
Bài tập về Mảng và Xâu ký tự
Nhập vào một dãy số nguyên gồm n phần tử, với n không vượt quá 100 và các phần tử không lớn hơn 10^9 Viết chương trình để kiểm tra tính đối xứng của dãy số Nếu dãy số đối xứng, in ra "YES", ngược lại in ra "NO".
Dữ liệu đầu vào bao gồm số bộ test, với mỗi bộ test được cấu thành từ hai dòng Dòng đầu tiên chỉ ra số lượng phần tử trong dãy, trong khi dòng thứ hai chứa dãy số, với các số được phân cách bằng một khoảng trống.
Kết quả: Ghi ra YES hoặc NO trên một dòng
BÀI 2 TÍCH MA TRẬN VỚI CHUYỂN VỊ CỦA NÓ
Cho ma trận A chỉ gồm các số nguyên dương cấp N*M Hãy viết chương trình tính tích của
A với ma trận chuyển vị của A
Dữ liệu đầu vào bao gồm số bộ test, trong đó mỗi bộ test bắt đầu bằng hai số n và m, đại diện cho kích thước của ma trận A Tiếp theo, có n dòng, mỗi dòng chứa m số tương ứng với các phần tử trong ma trận A.
Kết quả: Với mỗi bộ test ghi ra thứ tự bộ test, sau đó đến ma trận tích tương ứng, mỗi số cách nhau đúng một khoảng trống
Số được gọi là số tăng giảm nếu các chữ số của nó không giảm hoặc không tăng từ trái sang phải Để xác định xem một số có phải là số tăng giảm hay không, cần kiểm tra sự sắp xếp của các chữ số trong số đó.
Dữ liệu vào: Dòng đầu tiên ghi số bộ test Mỗi bộ test viết trên một dòng một số nguyên dương cần kiểm tra, không quá 500 chữ số
Kết quả: Mỗi bộ test viết ra chữ YES nếu đó đúng là số tăng giảm, chữ NO nếu ngược lại
Nhập 2 mảng (a, N) và (b, M) và số nguyên p (0≤p2, , ‘Z’-
>26 Hãy cho biết có bao nhiêu cách khác nhau để giải mã bản tin M Ví dụ với bản mã M=”123” nó có thể được giải mã thành ABC (1 2 3), LC (12 3), AW(1 23)
Dòng đầu tiên đưa vào số lượng bộ test T
Những dòng kế tiếp đưa vào các bộ test Mỗi bộ test là một xâu ký tự số M
T, M thỏa mãn ràng buộc: 1≤T≤100; 1≤length(M)≤40
Đưa ra kết quả mỗi test theo từng dòng
Mọi số nguyên dương N đều có thể phân tích thành tổng các bình phương của các số nhỏ hơn
N Ví dụ số 100 = 10 2 hoặc 100 = 5 2 + 5 2 + 5 2 + 5 2 Cho số nguyên dương N Nhiệm vụ của bạn là tìm số lượng ít nhất các số nhỏ hơn N mà có tổng bình phương bằng N
Dòng đầu tiên đưa vào số lượng bộ test T
Những dòng kế tiếp đưa vào các bộ test Mỗi test là một số tự nhiên N được viết trên 1 dòng
Đưa ra kết quả mỗi test theo từng dòng
Bài tập về Bài toán liệt kê
BÀI 1 XÂU NHỊ PHÂN KẾ TIẾP
Cho xâu nhị phân X[], nhiệm vụ của bạn là hãy đưa ra xâu nhị phân tiếp theo của X[] Ví dụ X[] =”010101” thì xâu nhị phân tiếp theo của X[] là “010110”
Dòng đầu tiên đưa vào số lượng test T
Những dòng kế tiếp đưa vào các bộ test Mỗi bộ test là một xâu nhi phân X
T, X[] thỏa mãn ràng buộc: 1≤T≤100; 1≤length(X)≤10 3
Đưa ra kết quả mỗi test theo từng dòng
BÀI 2 TẬP CON KẾ TIẾP
Cho hai số N và K cùng với một tập con K phần tử X[] = {X1, X2, , XK} từ tập hợp {1, 2, , N} Nhiệm vụ của bạn là tìm tập con K phần tử tiếp theo của X[] Ví dụ, với N=5, K=3 và X[] = {2, 3, 4}, tập con tiếp theo sẽ là {2, 3, 5}.
Dòng đầu tiên đưa vào số lượng test T
Các bộ test được đưa vào bao gồm hai dòng Dòng đầu tiên chứa hai số N và K, trong khi dòng thứ hai cung cấp K phần tử của mảng X[], tạo thành một tập con.
Đưa ra kết quả mỗi test theo từng dòng
BÀI 3 HOÁN VỊ KẾ TIẾP
Cho một số tự nhiên N và một hoán vị X[] của các số từ 1 đến N, nhiệm vụ của bạn là tìm hoán vị tiếp theo của X[] Ví dụ, với N = 5 và X[] = {1, 2, 3, 4, 5}, hoán vị tiếp theo sẽ là {1, 2, 3, 5, 4}.
Dòng đầu tiên đưa vào số lượng test T
Những dòng kế tiếp đưa vào các bộ test Mỗi bộ test gồm hai dòng: dòng thứ nhất là số N; dòng tiếp theo đưa vào hoán vị X[] của 1, 2, , N
Đưa ra kết quả mỗi test theo từng dòng
Cho hai số nguyên dương N và K, nhiệm vụ của bạn là liệt kê tất cả các tập con K phần tử từ tập hợp {1, 2, , N} Ví dụ, với N=5 và K=3, ta có 10 tập con khác nhau, bao gồm: {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, và {3, 4, 5}.
Dòng đầu tiên đưa vào số lượng test T
Những dòng kế tiếp đưa vào các bộ test Mỗi bộ test là một cặp số tự nhiên N,
K được viết trên một dòng
Đưa ra kết quả mỗi test theo từng dòng
Cho số nguyên dương N Nhiệm vụ của bạn là hãy liệt kê tất cả các hoán vị của 1, 2, , N Ví dụ với N = 3 ta có kết quả: 123, 132, 213, 231, 312, 321
Dòng đầu tiên đưa vào số lượng test T
Những dòng kế tiếp đưa vào các bộ test Mỗi bộ test là một số tự nhiên N được viết trên một dòng
Đưa ra kết quả mỗi test theo từng dòng
Cho số nguyên dương N Nhiệm vụ của bạn là hãy liệt kê tất cả các cách phân tích số tự nhiên
N thành tổng các số tự nhiên nhỏ hơn hoặc bằng N Phép hoán vị vủa một cách được xem là giống nhau Ví dụ với N = 5 ta có kết quả là: (5), (4, 1), (3, 2), (3, 1, 1), (2, 2, 1), (2, 1, 1, 1),
Dòng đầu tiên đưa vào số lượng test T
Những dòng kế tiếp đưa vào các bộ test Mỗi bộ test là một số tự nhiên N được viết trên một dòng
Đưa ra kết quả mỗi test theo từng dòng
Cho số nguyên dương N Nhiệm vụ của bạn là hãy liệt kê tất cả các hoán vị của 1, 2, , N theo thứ tự ngược Ví dụ với N = 3 ta có kết quả: 321, 312, 231, 213, 132, 123
Dòng đầu tiên đưa vào số lượng test T
Những dòng kế tiếp đưa vào các bộ test Mỗi bộ test là một số tự nhiên N được viết trên một dòng
Đưa ra kết quả mỗi test theo từng dòng
Bài tập về Bài toán tối ưu
Cho mảng A[] với N phần tử, nhiệm vụ của bạn là tìm giá trị tối đa 𝑚𝑎𝑥 = ∑ 𝑛−1 𝑖=0 𝐴 𝑖 ∗ 𝑖 bằng cách sắp xếp lại các phần tử trong mảng Lưu ý rằng kết quả có thể rất lớn, vì vậy hãy trả về kết quả sau khi lấy modulo với 10^9 + 7.
Dòng đầu tiên đưa vào số lượng bộ test T
Mỗi bộ test bao gồm hai dòng: dòng đầu tiên chứa số lượng phần tử của mảng N, và dòng thứ hai cung cấp N số A[i] tương ứng với các phần tử trong mảng A[], được phân tách bằng một vài khoảng trống.
Đưa ra kết quả mỗi test theo từng dòng
Cho mảng A[] chứa các số từ 0 đến 9, nhiệm vụ của bạn là tính tổng nhỏ nhất của hai số được tạo ra từ các phần tử trong mảng Lưu ý rằng tất cả các số trong mảng A[] đều phải được sử dụng để tạo ra hai số này.
Dòng đầu tiên đưa vào số lượng bộ test T
Các bộ test sẽ bao gồm hai dòng Dòng đầu tiên nhập vào số phần tử của mảng N, trong khi dòng thứ hai chứa N số A[i] tương ứng với các phần tử của mảng A[], được phân cách bằng một số khoảng trống.
Đưa ra kết quả mỗi test theo từng dòng
Cho mảng A[] gồm N số nguyên không âm và số K, nhiệm vụ là chia mảng A[] thành hai mảng con với kích thước K và N-K để tối đa hóa hiệu giữa tổng hai mảng Ví dụ, với mảng A[] = {8, 4, 5, 2, 10} và K=2, kết quả là 17, khi mảng A[] được chia thành hai mảng {4, 2} và {8, 5, 10}, có hiệu tổng lớn nhất là 23 - 6.
Dòng đầu tiên đưa vào số lượng bộ test T
Mỗi bộ test bao gồm hai dòng: dòng đầu tiên chứa số phần tử của mảng N và số K; dòng thứ hai cung cấp N số A[i] tương ứng với các phần tử của mảng A[], được phân cách bằng một hoặc nhiều khoảng trống.
Đưa ra kết quả mỗi test theo từng dòng
BÀI 4 SẮP XẾP THAM LAM
Cho mảng A[] gồm N số và thực hiện các thao tác theo nguyên tắc dưới đây:
Ta chọn một mảng con sao cho phần tử ở giữa của mảng con cũng là phần tử ở giữa của mảng A[] (trong trường hợp N lẻ)
Đảo ngược mảng con đã chọn trong mảng A[] Ta được phép chọn mảng con và phép đảo ngược mảng con bao nhiêu lần tùy ý
Để xác định xem có thể sắp xếp mảng A[] = {1, 6, 3, 4, 5, 2, 7} hay không, ta có thể thực hiện các thao tác đảo ngược mảng con Ví dụ, bằng cách chọn mảng con {3, 4, 5} và đảo ngược, ta nhận được mảng A[] = {1, 6, 5, 4, 3, 2, 7} Tiếp theo, nếu chọn mảng con {6, 5, 4, 3, 2} và đảo ngược, ta sẽ có mảng A[] = {1, 2, 3, 4, 5, 6, 7} Như vậy, câu trả lời là có, ta có thể sắp xếp mảng A[] bằng cách thực hiện các thao tác đảo ngược mảng con.
Dòng đầu tiên đưa vào số lượng bộ test T
Bài viết này đề cập đến cách nhập dữ liệu cho các bộ test Mỗi bộ test bao gồm hai dòng: dòng đầu tiên chứa số phần tử của mảng N, và dòng thứ hai chứa N số A[i] tương ứng với các phần tử của mảng A[], được phân tách bằng một vài khoảng trống.
Đưa ra kết quả mỗi test theo từng dòng
BÀI 5 GIÁ TRỊ NHỎ NHẤT CỦA BIỂU THỨC
Cho mảng A[], B[] đều có N phần tử Nhiệm vụ của bạn là tìm giá trị nhỏ nhất của biểu thức
P = A[0]*B[0] + A[1]*B[1] + +A[N-1]*B[N-1] bằng cách tráo đổi vị trí các phần tử của cả mảng A[] và B[]
Dòng đầu tiên đưa vào số lượng bộ test T
Các bộ test bao gồm ba dòng: dòng đầu tiên nhập số phần tử của mảng N; dòng thứ hai nhập N số A[i]; và dòng cuối cùng nhập N số B[i], với các số được phân cách bằng khoảng trống.
Đưa ra kết quả mỗi test theo từng dòng
BÀI 6 SỐ KHỐI LẬP PHƯƠNG
Số khối lập phương được định nghĩa là số X là lũy thừa bậc 3 của số Y (X = Y^3) Đối với một số nguyên dương N, nhiệm vụ của bạn là tìm số khối lập phương lớn nhất có thể được tạo ra bằng cách loại bỏ các chữ số từ N Ví dụ, từ số 4125, ta có thể tìm ra số 125, tương đương với 5^3.
Dòng đầu tiên đưa vào số lượng bộ test T
Những dòng kế tiếp đưa vào các bộ test Mỗi bộ test là một số tự nhiên N được viết trên một dòng
Đưa ra kết quả mỗi test theo từng dòng Nếu không tìm được đáp án in ra -1
Cho hai số nguyên dương S và D, với S là tổng các chữ số và D là số lượng chữ số của một số, nhiệm vụ của bạn là tìm số nhỏ nhất thỏa mãn các điều kiện này Ví dụ, với S = 9 và D = 2, số nhỏ nhất thỏa mãn S và D là 18.
Dòng đầu tiên đưa vào số lượng bộ test T
Những dòng kế tiếp đưa vào các bộ test Mỗi bộ test là bộ 2 số S và D được viết trên một dòng
Đưa ra kết quả mỗi test theo từng dòng Nếu không có đáp án, in ra -1
BÀI 8 GIÁ TRỊ NHỎ NHẤT CỦA XÂU
Cho xâu ký tự S Ta gọi giá trị của xâu S là tổng bình phương số lần xuất hiện mỗi ký tự trong
S Hãy tìm giá trị nhỏ nhất của xâu S sau khi thực hiện K lần loại bỏ ký tự
Dòng đầu tiên đưa vào số lượng bộ test T
Mỗi bộ test bao gồm hai phần: phần đầu tiên là số K và phần thứ hai là một xâu ký tự S được trình bày trên một dòng.
T, S, K thỏa mãn ràng buộc: 1≤T≤100; 1≤length(S)≤10000; 1≤K≤1000
Đưa ra kết quả mỗi test theo từng dòng
Hoàng rất thích các số may mắn, được xác định là những số chỉ chứa các chữ số 4 và 7 trong biểu diễn thập phân của chúng Ví dụ về các số may mắn bao gồm 4, 47 và 744, trong khi các số như 5 và 17 không phải là số may mắn.
467 không phải Hoàng muốn tìm số may mắn bé nhất có tổng các chữ số bằng n Hãy giúp anh ấy
Dữ liệu vào: Dòng đầu ghi số bộ test, mỗi bộ test có một dòng chứa số nguyên n (1 ≤ n ≤ 10 6 )
— tổng các chữ số của số may mắn cần tìm
Kết quả: In ra trên 1 dòng số may mắn bé nhất, mà tổng các chữ số bằng n Nếu không tồn tại số thỏa mãn, in ra -1
BÀI 10 PHÂN SỐ ĐƠN VỊ
Một phân số đơn vị được định nghĩa là phân số có tử số bằng 1 Tất cả các phân số nguyên dương đều có thể được biểu diễn dưới dạng tổng của các phân số đơn vị Chẳng hạn, phân số 2/3 có thể được viết thành 1/2 + 1/6 Đối với bất kỳ phân số nguyên dương nào P/Q (với P < Q), ta có thể chuyển đổi nó thành tổng các phân số đơn vị.
Dòng đầu tiên đưa vào số lượng bộ test T
Những dòng kế tiếp đưa vào các bộ test Mỗi bộ test là bộ đôi tử số P và mẫu số
Q của phân số nguyên dương được viết trên một dòng
Đưa ra đáp án tìm được trên 1 dòng, theo dạng “1/a + 1/b + …”
CÁC MÔ HÌNH THUẬT TOÁN CƠ BẢN
Bài tập về Thuật toán Tham lam
BÀI 1 SẮP XẾP CÔNG VIỆC 1
Trong một hệ thống gồm N hành động, mỗi hành động được biểu diễn dưới dạng cặp , với Si là thời gian bắt đầu và Fi là thời gian kết thúc Mục tiêu là tìm ra phương án thực hiện tối đa các hành động mà không xảy ra mâu thuẫn, đảm bảo rằng một máy hoặc một người có thể thực hiện chúng một cách hiệu quả.
Dòng đầu tiên đưa vào số lượng bộ test T
Mỗi bộ test bao gồm ba dòng: dòng đầu tiên nhập vào số lượng hành động N; dòng thứ hai chứa N số Si, tương ứng với thời gian bắt đầu của mỗi hành động; và dòng cuối cùng là N số Fi, tương ứng với thời gian kết thúc của mỗi hành động Các số được phân cách bằng khoảng trống.
T, N, Si, Fi thỏa mãn ràng buộc: 1≤T≤100; 1≤N, Fi, Si≤1000
Đưa số lượng lớn nhất các hành động có thể được thực thi bởi một máy hoặc một người
BÀI 2 SẮP XẾP CÔNG VIỆC 2
Cho N công việc, mỗi công việc được mô tả bằng bộ ba số nguyên dương Trong đó, JobId là mã công việc, Deadline là thời gian hoàn thành, và Profit là lợi nhuận nếu công việc được hoàn thành đúng hạn Thời gian để hoàn thành mỗi công việc là 1 đơn vị thời gian Mục tiêu là xác định lợi nhuận lớn nhất có thể đạt được khi thực hiện các công việc, với giả định rằng mỗi công việc được thực hiện một cách độc lập.
Dòng đầu tiên đưa vào số lượng bộ test T
Các bộ test được trình bày bao gồm hai phần: phần đầu tiên là số lượng công việc N, và phần thứ hai chứa 3×N số liệu tương ứng với N công việc.
T, N, JobId, Deadline, Profit thỏa mãn ràng buộc:1≤T≤100; 1≤N≤1000; 1≤ JobId ≤1000; 1≤ Deadline ≤1000; 1≤ Profit ≤1000
Đưa số lượng công việc tương ứng và lợi nhuận lớn nhất có thể đạt được
Cho N sợi dây có độ dài khác nhau được lưu trong mảng A[] Nhiệm vụ của bạn là nối N sợi dây thành một sợi duy nhất sao cho tổng chi phí nối dây là nhỏ nhất Chi phí nối giữa sợi dây thứ i và sợi dây thứ j được tính bằng tổng độ dài của hai sợi dây A[i] và A[j].
Dòng đầu tiên đưa vào số lượng bộ test T
Các bộ test sẽ bao gồm hai dòng: dòng đầu tiên chứa số lượng sợi dây N, và dòng thứ hai cung cấp N số A[i], thể hiện độ dài của các sợi dây Các số trong dòng thứ hai được ngăn cách bởi một hoặc nhiều khoảng trống.
Đưa ra kết quả mỗi test theo từng dòng
Cho N sợi dây có độ dài khác nhau lưu trữ trong mảng A[] Nhiệm vụ của bạn là nối các sợi dây này thành một sợi duy nhất với tổng chi phí nối dây thấp nhất Chi phí để nối sợi dây thứ i và sợi dây thứ j được tính bằng tổng độ dài của hai sợi dây A[i] và A[j].
Dòng đầu ghi số bộ test T (T