Bộ 15 Đề thi Phân tích & thiết kế giải thuật (Có đáp án)

 Bộ 15 Đề thi Phân tích & thiết kế giải thuật (Có đáp án) - DeThiTinHoc.net
 DeThiTinHoc.net Bộ 15 Đề thi Phân tích & thiết kế giải thuật (Có đáp án) - DeThiTinHoc.net
 ĐỀ SỐ 1
 ĐẠI HỌC ĐÀ NẴNG ĐỀ THI KẾT THÚC HỌC PHẦN HỌC KỲ 1
 TRƯỜNG ĐẠI HỌC SƯ PHẠM Môn: PHÂN TÍCH & THIẾT KẾ GIẢI THUẬT 
 Thời gian: 60 phút (không kể thời gian phát đề)
Bài 1: Thay chữ số (ReplaceDigit) (20 điểm) 
Hãy lập trình vào số nguyên n,thực hiện thay thế các chữ số 0 trong biểu diễn thập phân của 
n thành các chữ số 5 và in ra kết quả. 
Ví dụ: với n = 1005 thì sau khi thực hiện thay thế ta thu được số 1555. Còn với n = 1234, thì 
không có chữ số nào bị thay thế và kết quả vẫn là số 1234. 
Đầu vào 
Dòng đầu tiên của đầu vào chứa số nguyên T cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ 
liệu cần một dòng chứa một số nguyên n 
Đầu ra 
Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra số n sau khi thay thế các chữ 
số của n theo yêu cầu đề bài. 
Ràng buộc 
 • 1 ≤ T ≤ 105 ; 0 ≤ n ≤ 1012
Ví dụ:
 Đầu vào Đầu ra
2 1555
1005 1234
1234
Bài 2: (MAXPRIME) (30 điểm) 
Cho dãy số nguyên gồm n phần tử: a1, a2,...,an. Tìm số nguyên tố lớn nhất trong dãy đã cho. 
Nếu trong dãy không có số nguyên tố nào thì in ra No prime 
* Input: 
- Dòng đầu: n (n < 106). 
 18
- Dòng sau ghi n số nguyên a1, a2,...,an (ai < 10 ). 
* Output: Số nguyên tố lớn nhất cần tìm. 
Ví dụ:
 Input Output
5 59
43 59 88 96 22
5 No prime
4 6 9 12 15
 DeThiTinHoc.net Bộ 15 Đề thi Phân tích & thiết kế giải thuật (Có đáp án) - DeThiTinHoc.net
Bài 3: Bộ tam hợp (TAMHOP) (30 điểm) 
Cho dãy số nguyên a1, a2, ..., an, các số khác nhau từng đôi một (3 ≤ n ≤ 5000; với mọi i ta 
có |ai| ≤ 106). Bộ ba số ai, aj, ak (i ≠ j ≠ k) được gọi là Bộ tam hợp nếu có một số bất kỳ trong 
ba số đó bằng trung bình cộng của hai số còn lại. 
Yêu cầu: Hãy đếm số lượng bộ tam hợp và tìm bộ tam hợp có tổng giá trị của ba số là lớn 
nhất. 
Dữ liệu vào: 
- Dòng 1 chứa số n; 
- Dòng 2 chứa n số a1, a2, ..., an cách nhau ít nhất một dấu cách 
Dữ liệu ra:
- Dòng 1 ghi một số nguyên dương là số lượng bộ tam hợp tìm được;
- Dòng 2 ghi tổng giá trị ba số của bộ tam hợp là lớn nhất. 
Ví dụ:
 Đầu vào Đầu ra
7 5 
6 1 9 2 3 4 8 18
Giải thích: Có 5 bộ tam hợp tìm được là: (1, 2, 3); (2, 3, 4); (2, 4, 6); (4, 6, 8); (3, 6, 9).
Bài 4: CON ĐƯỜNG HOA (PAFOWER) (20 điểm) 
Ở thành phố Đà Nẵng, để trang trí con đường tham quan nhân dịp các ngày lễ, lãnh đạo 
thành phố đã chỉ đạo trồng những cây hoa ở hai bên lề đường (có thể xem là lề đường A và 
lề đường B). Sau một thời gian, các cây hoa này đã trưởng thành và có thể phục vụ cho du 
khách tham quan. Trước dịp Tết vừa qua, người ta thấy trong các cây hoa được trồng thì 
cũng có khá nhiều cây hoa không được đẹp nên lãnh đạo thành phố quyết định đưa ra 
phương án bỏ đi một số cây hoa và sắp xếp lại sao cho cảnh quan được hài hòa hơn. Người 
chịu trách nhiệm công việc đó đã đánh dấu các cây hoa được đánh giá là đẹp có số 1, còn các 
cây hoa được coi là xấu được đánh dấu là số -1. Việc bỏ đi các cây hoa xấu có thể làm cho 
con đường tham quan không còn nhiều cây hoa nữa nên công việc ở đây cần phải đảm bảo 
tất cả các điều kiện sau: 
- Không được di chuyển cây hoa ở lề đường A sang lề đường B và ngược lại. 
- Các cây hoa trên cùng một lề đường không được thay đổi vị trí với nhau. 
- Một cây hoa ở lề đường A và một cây hoa ở lề đường B sẽ tạo thành 1 cặp. 
- Với mỗi cặp được giữ lại phải luôn luôn không được cả 2 cây hoa cùng xấu. 
- Số lượng cây hoa được giữ lại là nhiều nhất. 
Mỗi lề đường đều có n cây hoa, với lề đường A: cây hoa thứ i được đánh giá bởi giá trị ai; 
với lề đường B: cây hoa thứ i được đánh giá bởi giá trị bi (với ai và bi nhận giá trị là 1 hoặc -
1; i = 1,..,n). 
 DeThiTinHoc.net Bộ 15 Đề thi Phân tích & thiết kế giải thuật (Có đáp án) - DeThiTinHoc.net
Yêu cầu: Cho biết số lượng cặp cây hoa được giữ lại nhiều nhất thỏa mãn tất cả các điều 
kiện nêu trên. 
Dữ liệu: 
- Dòng đầu: Chứa số nguyên dương n (n ≤ 1000). 
- Trong n dòng tiếp theo, mỗi dòng chứa cặp số nguyên ai và bi. 
Kết quả: một số nguyên duy nhất là số lượng cặp cây hoa nhiều nhất được giữ lại thỏa mãn 
tất cả các điều kiện của đề bài. 
Ví dụ:
 Input Output
5 4
-1 -1 
 1 1 
 1 -1 
-1 -1 
-1 1
Giải thích: Chọn được nhiều nhất là 4 cặp cây hoa: 
- Lề đường A: gồm các cây ở vị trí 1, 2, 3, 4 
- Lề đường B: gồm các cây ở vị trí 2, 3, 4, 5
 ----------HẾT----------
 DeThiTinHoc.net Bộ 15 Đề thi Phân tích & thiết kế giải thuật (Có đáp án) - DeThiTinHoc.net
 ĐÁP ÁN
Bài 1: Thay chữ số (ReplaceDigit) (20 điểm) 
#include 
#include 
#include 
using namespace std;
void solve() {
 string n;
 cin >> n;
 // Duyệt qua từng ký tự của chuỗi số
 for (int i = 0; i < n.length(); i++) {
 if (n[i] == '0') {
 n[i] = '5';
 }
 }
 cout << n << endl;
}
int main() {
 // Tối ưu tốc độ nhập xuất
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 int T;
 if (!(cin >> T)) return 0;
 while (T--) {
 solve();
 }
 return 0;
}
 DeThiTinHoc.net Bộ 15 Đề thi Phân tích & thiết kế giải thuật (Có đáp án) - DeThiTinHoc.net
Bài 2: (MAXPRIME) (30 điểm) 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef __int128_t int128;
// Hàm tính (base^exp) % mod
ll power(ll base, ll exp, ll mod) {
 ll res = 1;
 base %= mod;
 while (exp > 0) {
 if (exp % 2 == 1) res = (ll)((int128)res * base % mod);
 base = (ll)((int128)base * base % mod);
 exp /= 2;
 }
 return res;
}
// Kiểm tra số nguyên tố bằng Miller-Rabin
bool isPrime(ll n) {
 if (n < 2) return false;
 if (n == 2 || n == 3) return true;
 if (n % 2 == 0 || n % 3 == 0) return false;
 ll d = n - 1;
 int s = 0;
 while (d % 2 == 0) {
 d /= 2;
 s++;
 }
 // Các cơ số đủ để kiểm tra chính xác cho n < 3*10^18
 static const vector bases = {2, 3, 5, 7, 11, 13, 17, 19, 23};
 for (ll a : bases) {
 DeThiTinHoc.net Bộ 15 Đề thi Phân tích & thiết kế giải thuật (Có đáp án) - DeThiTinHoc.net
 if (n <= a) break;
 ll x = power(a, d, n);
 if (x == 1 || x == n - 1) continue;
 bool composite = true;
 for (int r = 1; r < s; r++) {
 x = (ll)((int128)x * x % n);
 if (x == n - 1) {
 composite = false;
 break;
 }
 }
 if (composite) return false;
 }
 return true;
}
int main() {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 int n;
 if (!(cin >> n)) return 0;
 ll max_prime = -1;
 for (int i = 0; i < n; i++) {
 ll a;
 cin >> a;
 if (a > max_prime && isPrime(a)) {
 max_prime = a;
 }
 }
 if (max_prime == -1) {
 cout << "No prime" << endl;
 } else {
 cout << max_prime << endl;
 }
 DeThiTinHoc.net Bộ 15 Đề thi Phân tích & thiết kế giải thuật (Có đáp án) - DeThiTinHoc.net
 return 0;
}
Bài 3: Bộ tam hợp (TAMHOP) (30 điểm) 
#include 
#include 
#include 
using namespace std;
// Mảng đánh dấu sự tồn tại của phần tử (cộng offset 10^6 để xử lý số âm)
int exists[2000005]; 
const int OFFSET = 1000000;
int main() {
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 int n;
 cin >> n;
 vector a(n);
 for (int i = 0; i < n; i++) {
 cin >> a[i];
 exists[a[i] + OFFSET] = 1;
 }
 sort(a.begin(), a.end());
 long long count = 0;
 long long max_sum = -4e18; // Khởi tạo giá trị rất nhỏ
 bool found = false;
 // Duyệt cặp (i, j) để tìm trung bình cộng ở giữa
 for (int i = 0; i < n; i++) {
 for (int j = i + 2; j < n; j++) {
 long long sum_xz = a[i] + a[j];
 // Điều kiện để có số nguyên y ở giữa: tổng x+z phải chẵn
 DeThiTinHoc.net Bộ 15 Đề thi Phân tích & thiết kế giải thuật (Có đáp án) - DeThiTinHoc.net
 if (sum_xz % 2 == 0) {
 long long mid = sum_xz / 2;
 if (exists[mid + OFFSET]) {
 count++;
 max_sum = max(max_sum, (long long)(a[i] + a[j] + mid));
 found = true;
 }
 }
 }
 }
 cout << count << endl;
 if (found) cout << max_sum << endl;
 return 0;
}
Bài 4: CON ĐƯỜNG HOA (PAFOWER) (20 điểm) 
#include 
#include 
#include 
using namespace std;
int main() {
 int n;
 if (!(cin >> n)) return 0;
 vector a(n + 1), b(n + 1);
 for (int i = 1; i <= n; i++) {
 cin >> a[i] >> b[i];
 }
 // dp[i][j] là số lượng cặp hoa tối đa chọn từ i cây đầu lề A và j cây đầu lề B
 vector> dp(n + 1, vector(n + 1, 0));
 for (int i = 1; i <= n; i++) {
 DeThiTinHoc.net Bộ 15 Đề thi Phân tích & thiết kế giải thuật (Có đáp án) - DeThiTinHoc.net
 for (int j = 1; j <= n; j++) {
 // Kiểm tra điều kiện: không được cả hai cùng là -1
 if (!(a[i] == -1 && b[j] == -1)) {
 dp[i][j] = dp[i - 1][j - 1] + 1;
 } else {
 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
 }
 }
 }
 cout << dp[n][n] << endl;
 return 0;
}
 DeThiTinHoc.net