Bài tập cuối kỳ Môn Thuật toán ứng dụng | Đại học Bách Khoa Hà Nội

lOMoAR cPSD| 61601590 Hép pi liu diu Bài 2: Description
Trong thế giới huyền bí của vương quốc An Lạc, huyền thoại kể về một lời nguyền cổ xưa mà chỉ
những kẻ dũng cảm nhất mới có thể phá vỡ. Vương quốc này có những kho báu bí ẩn, mỗi kho
chứa một lượng vàng khổng lồ ciđược đặt tại các vị trí kỳ diệu có toạ độ (xi, yi). Những người đi
tìm kho báu chỉ có thể bắt đầu hành trình từ cổng thành cổ tại (0,0) và theo một quy tắc đặc biệt:
họ chỉ được phép di chuyển về phía mặt trời mọc - theo hướng không giảm của cả hai toạ độ x
và y - để tìm đến các kho báu. Điều này nghĩa là từ kho báu tại (xi, yi), người ta chỉ có thể tiếp tục
hành trình đến kho báu (xj, yj) nếu xi ≤ xj và yi ≤ yj.
Kẻ tìm kho báu phải sắp xếp một lộ trình khôn ngoan để thu thập được nhiều vàng nhất, nhưng
cần phải nhớ rằng, lời nguyền sẽ chỉ cho phép họ đi theo hướng mặt trời mọc như đã mô tả. Dữ liệu vào:
Dòng thứ nhất chứa số nguyên dương n là số lượng kho báu (1 ≤ n ≤ 103).
Trong n dòng tiếp theo, mỗi dòng chứa hai số nguyên dương xi, yi, ci (1 ≤ xi, yi, ci ≤ 109) là toạ độ
và lượng vàng của kho báu thứ i, i = 1, 2, …, n. Kết quả:
Ghi ra một số nguyên duy nhất là tổng lượng vàng lớn nhất có thể tìm được. Dữ liệu vào 10 2 4 7 4 2 10 4 6 2 5 5 7 1 3 9 1 5 1 1 1 3 3 1 5 3 3 6 lOMoAR cPSD| 61601590 2 2 2 Kết quả: 26 #include using namespace std; int main(){ struct gold { int x, y, val; }; int n; cin >> n; gold gold_map[105];
for (int i = 0; i < n; i++){
cin >> gold_map[i].x >> gold_map[i].y >> gold_map[i].val; }
sort(gold_map, gold_map + n, [](const gold &a, const gold &b) {
if (a.x == b.x) return a.y < b.y; return a.x < b.x; }); int dp[105]; dp[0] = gold_map[0].val;
for (int i = 1; i < n; i++){ dp[i] = gold_map[i].val;
for (int j = i-1; j >= 0; j--){
if (gold_map[j].x <= gold_map[i].x && gold_map[j].y <= gold_map[i].y){
dp[i] = max(dp[i], dp[j] + gold_map[i].val); } } } cout << dp[n-1]; } lOMoAR cPSD| 61601590 Giải thích:
Đường đi tối ưu đi qua các kho báu có toạ độ lần lượt là (1, 1), (1, 3), (2,4) và (5,5) có tổng lượng vàng là 3 + 9 + 7 + 7 = 26 Description //gk cc
There are n passengers 1, 2, …, n. The passenger i want to travel from point i to point i + n (i =
1,2,…,n). There is a bus located at point 0 and has k places for transporting the passengers (it
means at any time, there are at most k passengers on the bus). You are given the distance matrix
c in which c(i,j) is the traveling distance from point i to point j (i, j = 0,1,…, 2n). Given a positive
integer D, compute the shortest route for the bus, serving n passengers and coming back to point
0 with the condition that the travel distance from the pickup point to the corresponding the drop-
off point of any passenger is at most D. Input •
Line 1 contains n, k, and D (1≤n≤11,1≤k≤10, 1 <= D <= 100000) •
Line i+1 (i=1,2,…,2n+1) contains the (i−1)th line of the matrix c (rows and columns are
indexed from 0,1,2,..,2n, elements are from 1 to 100000). Output •
Unique line contains the length of the shortest route. Example Input 3 2 15 0 8 5 1 10 5 9 9 0 5 6 6 2 8 2 2 0 3 8 7 2 5 3 4 0 3 2 7 lOMoAR cPSD| 61601590 9 6 8 7 0 9 10 3 8 10 6 5 0 2 3 4 4 5 2 2 0 Output 27 Description
Trong thời đại chiến quốc, bạn là một kiến trúc sư danh tiếng của Vương quốc An Lạc, được giao
nhiệm vụ xây dựng một pháo đài vững chãi để chống lại kẻ địch đang tiến gần. Pháo đài này không
chỉ cần mạnh mẽ mà còn phải phản ánh vẻ đẹp của nghệ thuật và kiến trúc An Lạc. Để thực hiện
điều này, bạn cần tập hợp các khối đá với kích thước L1xW1xH1, L2xW2xH2, ..., LNxWNxHN, đây
là nền móng cho các tòa tháp và bức tường của pháo đài. Vừa qua, quân đoàn thợ mỏ của bạn
đã phát hiện một khối đá lớn dạng hình hộp chữ nhật, nguyên liệu lý tưởng cho kế hoạch của
bạn. Khối đá (hoặc bất kỳ khối nhỏ nào được cắt từ nó) chỉ có thể được cắt theo ba chiều không
gian (dài, rộng, cao) thành hai khối nhỏ hơn với các kích thước nguyên. Mỗi lần cắt đá là phải
xuyên suốt qua khối đó (cắt đứt đôi hoàn toàn khối đá theo chiều đã chọn). Đây là cách duy nhất
để cắt khối đá, và các khối sau khi cắt không thể được ghép lại với nhau thành khối to hơn được.
Lưu ý, các khối đá này có thể được xoay theo nhiều hướng khác nhau để phù hợp với từng vị trí
cụ thể trong lúc xây dựng pháo đài: một khối với kích thước AxBxC có thể được sử dụng giống
như khối BxAxC, BxCxA, CxAxB, hoặc CxBxA. Bạn có thể tạo ra không hoặc nhiều khối với mỗi kích
thước mong muốn. Một khối đá bị lãng phí nếu nó không phải là một trong những kích thước
mong muốn sau tất cả các lần cắt. Nhiệm vụ của bạn là làm thế nào để cắt khối đá ban đầu sao
cho tổng thể tích các khối đá bị lãng phí là ít nhất. Đầu vào:
Dòng thứ nhất chứa một số nguyên dương T là số lượng test case (1 ≤ T ≤ 10). Mỗi bộ test case có khuôn dạng như sau:
· Dòng đầu tiên chứa ba số nguyên thể hiệnkích thước L, W, H (1 ≤ L, W, H ≤ 100) của khối đá ban đầu.
· Dòng thứ hai chứa một số nguyên N (0 < N ≤ 50): số lượng các khối có kích thước mong muốn.
· N dòng tiếp theo chứa kích thước các khối mong muốn. Mỗi dòng chứa ba số nguyên: chiều dài
Li, chiều rộng Wi, và chiều cao Hi của kích thước khối mong muốn đó (1 ≤ i ≤ N). Dữ liệu đảm bảo
1 ≤ Li ≤ L, 1 ≤ Wi ≤ W, và 1 ≤ Hi ≤ H. lOMoAR cPSD| 61601590 Kết quả:
Viết mỗi test case ghi ra trên một dòng một số nguyên duy nhất là tổng thể tích tối thiểu của
lượng đá bị lãng phí từ việc cắt khối đá cẩm thạch ban đầu. Ví dụ: Dữ liệu vào 2 5 10 1 33 9 1 2 4 5 2 2 2 5 5 2 2 3 2 3 1 3 2 Kết quả 13 8 Giải thích
Với test case đầu, bạn có thể cắt thành 1 khối 3x9x3, hai khối 2x4x3 và 1 khối 2x2x2. Lãng phí một
khối 1x3x3 và 1 khối 2x2x1 có tổng thể tích là 13 Với test case thứ hai, bạn có thể cắt thành 1 khối
3x2x3 và 4 khối 1x3x2. Lãng phí một khối 2x2x2 có thể tích là 8 Bài 3: Description
Cho một dãy số nguyên A gồm n số a1, a2, …, an. Một dãy con của dãy A là dãy thu được bằng
cách xoá không hoặc một số phần tử của dãy A. Hãy tìm dãy con dài nhất có các phần tử tăng
ngặt và có tính “chẵn lẻ” xen kẽ nhau, nghĩa là tổng hai phần tử liên tiếp nhau bất kỳ luôn không chia hết cho 2. lOMoAR cPSD| 61601590 Dữ liệu vào:
Dòng thứ nhất chứa một số nguyên T là số bộ testcase (1 <= T <= 10).
Mỗi nhóm dòng trong T nhóm dòng tiếp theo có cấu trúc như sau:
- Dòng thứ nhất chứa số nguyên n là số phần tử của dãy A (1 <= n <= 10^5)
- Dòng thứ hai chứa n số nguyên ai cách nhau bởi dấu cách (|ai| <= 10^9) Kết quả:
In ra T dòng, mỗi dòng chứa một số nguyên duy nhất là độ dài của dãy con dài nhất thoả mãn yêu
cầu bài toán ứng với từng testcase. Ví dụ: Dữ liệu vào 2 10
-22 -7 -5 17 41 -9 -44 14 107 -249 15
19 -17 5 39 -19 -15 -32 7 6 -155 69 104 -27 39 155 Kết quả 4 5 Giải thích:
Với testcase 1, dãy con dài nhất có độ dài là 4, chẳng hạn dãy -22 -9 14 107. Với testcase thứ 2,
dãy con dài nhất có độ dài bằng 5 có thể là -15 6 69 104 155. lOMoAR cPSD| 61601590 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { int n; cin >> n; vector a(n + 1); vector dp(n + 1, 1);
for (int i = 1; i <= n; i++) cin >> a[i]; int max_len = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[i] > a[j] && (a[i] + a[j]) % 2 != 0) {
dp[i] = max(dp[i], dp[j] + 1); } }
max_len = max(max_len, dp[i]); }
cout << max_len << "\n"; } return 0; } Description
Để tìm kiếm chồng là một anh chàng khoa học máy tính, công chúa của một đất nước ra một đề
toán như sau: Cho n số nguyên, hãy chọn một tập con của tập n số nguyên này sao cho tổng của
các số nguyên được chọn không vượt qua M cho trước và hiệu giữa M và tổng của những số
nguyên được chọn là nhỏ nhất. Đầu vào lOMoAR cPSD| 61601590
· Dòng 1: Số nguyên n (1 <= n <= 20)
· Dòng 2: n số nguyên cách nhau bởi dấu cách, giá trị của các số nguyên này nằm từ 1 tới 1000
· Dòng 3: Số nguyên M (1 <= M <= 100000) Đầu ra
· Một số tự nhiên là hiệu của M và tổng của các số nguyên được chọn nhỏ nhất. Ví dụ Input (stdin) 5 208 750 114 184 538 897 Output (stdout) 33 lOMoAR cPSD| 61601590 #include using namespace std; int main(){ int n; cin >> n; int a[104]; int sum = 0;
for (int i = 0; i < n; i++){ cin >> a[i]; sum += a[i]; } sort(a, a+n); int m; cin >> m; vector dp(sum, 0); dp[0] = 1;
for (int i = 0; i < n; i++){
for (int j = sum; j >= a[i]; j--){
if (dp[ j - a[i] ] == 1){ dp[j] = 1; } } }
for (int j = m; j >= 0; j--){ if (dp[j]){ cout << m - j; return 0; } } } Description
A bank needs to transfer n bags of money from its headquarters to its branches using two
specialized cash transport vehicles with equal transportation capabilities. Each money bag has a
value. To minimize operational risk, the cash transport coordinator needs to divide these n money lOMoAR cPSD| 61601590
bags between the two vehicles so that the difference in the total value of money transported by
these two vehicles is as small as possible.
(Ngân hàng cần chuyển n túi tiền từ trụ sở chính đến các chi nhánh của mình bằng hai xe chuyên
dụng chở tiền có khả năng vận chuyển bằng nhau. Mỗi túi tiền có một giá trị nhất định. Để giảm
thiểu rủi ro hoạt động, người điều phối vận chuyển tiền cần phải chia những túi tiền này cho hai
xe sao cho sự chênh lệch về tổng giá trị tiền được vận chuyển bởi hai xe này càng nhỏ càng tốt.) Input/Đầu vào •
Row 1: A integer representing the number of cash bags, n (1 <= n <= 20) (Một số nguyên
biểu thị số lượng túi tiền, không xác định) •
Row 2: n integers separated by by spaces, each representing the value of a cash bag. These
integers range from 1 to 1000 (n số nguyên được phân cách bằng dấu cách, mỗi số biểu
thị giá trị của một túi tiền. Những số nguyên này nằm trong khoảng từ 1 đến 1000.) Output/Đầu ra
An integer representing the smallest possible difference in the total values of money transported
by the two vehicles. (Một số nguyên biểu thị cho sự chênh lệch nhỏ nhất có thể trong tổng giá trị
tiền được vận chuyển bởi hai xe.) Example/Ví dụ Input (stdin) 5 208 750 114 184 538 Output (stdout) 66 lOMoAR cPSD| 61601590 #include using namespace std; int main(){ int n; cin >> n; int a[25]; int sum = 0;
for (int i = 0; i < n; i++){ cin >> a[i]; sum += a[i]; } int each = sum/2; vector dp(sum, 0); dp[0] = 1;
for (int i = 0; i < n; i++){
for (int j = sum; j >= a[i]; j--){
if (dp[ j - a[i] ] == 1) dp[j] = 1; } } int each_l, each_r;
for (int i = each; i >= 0; i--){ if (dp[i]){ each_l = i; break; } }
for (int i = each + 1; i <= sum; i++){ if (dp[i]){ each_r = i; break; } }
if ((each_l - each) < (each_r - each)){ each = each_l; } else { each = each_r; }
cout << abs((sum-each) - each); } lOMoAR cPSD| 61601590 Bài 4: Description
Có N điểm 1, 2, …, N cần thu gom bưu kiện và K bưu tá xuất phát từ bưu điện (điểm 0). Biết d(i,j)
là khoảng cách từ điểm i đến điểm j, với i,j = 0,1,..., N. Cần xây dựng phương án thu gom cho K
bưu tá, xác định mỗi bưu tá thu gom nhưng điểm nào và theo thứ tự nào sao cho quãng đường
dài nhất của bưu tá phải ngắn nhất.
Một phương án của bài toán là K lộ trình cho K xe, mỗi lộ trình k được biểu diễn bởi chuỗi lk số
nguyên dương x[1], x[2], . . ., x[lk] trong đó x[1] = 0 (điểm xuất phát, bưu điện), và x[2], x[3], . . ,
x[lk] là các điểm thu gom. Input •
Line 1: chứa 2 số nguyên dương N và K (1 <= N <= 1000, 1 <= K <= 100) •
Line i+1 (i = 0,…,N): chứa dòng thứ i của ma trận khoảng cách d Output •
Line 1: chứa số nguyên dương K •
Line 2*k (k = 1, . . ., K): chứa số nguyên dương lk •
Line 2*k+1 (k = 1, . . ., K): chứa lk số nguyên x[1], x[2], . . . , x[lk] (các phần tử cách nhau bởi 1 ký tự SPACE) Example Input 6 2 0 9 9 9 7 2 9 9 0 3 0 2 8 1 9 3 0 3 4 7 4 9 0 3 0 2 8 1 7 2 4 2 0 6 2 2 8 7 8 6 0 8 9 1 4 1 2 8 0 lOMoAR cPSD| 61601590 Output 2 3 0 5 2 5 0 4 1 3 6 #include using namespace std; int a[1005][1005]; int n, k; vector visited(1005, 0);
vector shipper[105], shipper_kq[105]; int min_record = INT_MAX; void init(){
for (int i = 0; i < k; i++) shipper[i].push_back(0); }
int total_dist(vector shipper){ if (shipper.size() == 1) return 0; int total = 0;
for (int i = 0; i < shipper.size()-1; i++) {
total += a[ shipper[i] ][ shipper[i+1] ]; } return total; }
// co n buu kien, h can phan chia cho k nguoi void Try(int u){ // goi
hang thu u for (int i = 0; i < k; i++){ lOMoAR cPSD| 61601590 shipper[i].push_back(u); visited[u] = 1; if (u == n){ int max_n = INT_MIN;
// di tim quang duong cua shipper dai nhat
for (int j = 0; j < k; j++) {
max_n = max(max_n, total_dist(shipper[j])); } if (min_record > max_n){
for (int j = 0; j < k; j++) { shipper_kq[j] = shipper[j]; } min_record = max_n; } } else Try(u+1); shipper[i].pop_back(); visited[u] = 0; } }
int main(){ cin >> n >> k;
for (int i = 0; i <= n; i++){
for (int j = 0; j <= n; j++){ cin >> a[i][j]; } } init(); Try(1);
cout << k << endl;
for (int i = 0; i < k; i++){
cout << shipper_kq[i].size() << endl;
for (int j: shipper_kq[i]) cout << j << " "; cout << endl; } } lOMoAR cPSD| 61601590 RESOURCE_BOUNDED_K_MST: K có đề -Dòng 1: ghi n, m, R, K
-Dòng i + 1 (i = 1,...,m): ghi u, v, w, r trong đó w là trọng số cạnh (u,v) và r là tài nguyên trên cạnh (u,v) Input 6 14 15 3 3 6 1 10 1 6 9 3 5 1 6 2 2 3 2 6 4 1 7 2 5 2 3 2 6 4 9 10 2 4 10 6 3 4 9 8 1 2 8 8 5 3 9 7 2 6 1 7 6 5 2 4 5 4 4 8