Bài A
Đọc hai chuỗi s và t. Nếu s là "AtCoder" và t là "Land", in ra "Yes", ngược lại in "No".
Xem mã nguồn
#include <bits/stdc++.h>
using namespace std;
int main() {
string x, y;
cin >> x >> y;
if (x == "AtCoder" && y == "Land")
cout << "Yes\n";
else
cout << "No\n";
return 0;
}
Bài B
Có n người, mỗi người cần a đơn vị thời gian để hoàn thành công việc. Người thứ i sẵn sàng bắt đầu từ thời điểm t[i]. Xác định thời điểm kết thúc của từng người khi họ được phục vụ theo thứ tự.
Duy trì biến current_time biểu thị thời điểm hiện tại. Với mỗi người, nếu current_time < t[i], họ bắt đầu ngay tại t[i]; ngược lại, họ bắt đầu ngay sau khi người trước kết thúc. Thời điểm kết thúc là thời điểm bắt đầu cộng với a.
Xem mã nguồn
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, duration;
cin >> n >> duration;
vector<int> ready(n);
for (int i = 0; i < n; ++i)
cin >> ready[i];
vector<int> start(n);
long long current_time = 0;
for (int i = 0; i < n; ++i) {
if (current_time < ready[i]) {
start[i] = ready[i];
current_time = ready[i] + duration;
} else {
start[i] = current_time;
current_time += duration;
}
}
for (int i = 0; i < n; ++i)
cout << start[i] + duration << '\n';
return 0;
}
Bài C
Có n món ăn và m loại hương vị. Mỗi món ăn có thể chứa một số hương vị nhất định (được đánh dấu bằng 'o'). Tìm số lượng món ăn tối thiểu sao cho tất cả m hương vị đều được bao phủ.
Sử dụng đệ quy quay lui (backtracking): với mỗi món ăn, thử chọn hoặc không chọn, đồng thời theo dõi các hương vị đã được bao phủ. Khi xét hết các món, kiểm tra xem mọi hương vị đã xuất hiện chưa và cập nhật đáp án tối ưu.
Xem mã nguồn
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<string> dishes;
vector<int> flavor_count;
int min_dishes = 100;
void backtrack(int idx, int chosen) {
if (idx == n) {
bool all_covered = true;
for (int f = 0; f < m; ++f)
if (flavor_count[f] == 0)
all_covered = false;
if (all_covered)
min_dishes = min(min_dishes, chosen);
return;
}
// Không chọn món hiện tại
backtrack(idx + 1, chosen);
// Chọn món hiện tại
for (int f = 0; f < m; ++f)
if (dishes[idx][f] == 'o')
flavor_count[f]++;
backtrack(idx + 1, chosen + 1);
for (int f = 0; f < m; ++f)
if (dishes[idx][f] == 'o')
flavor_count[f]--;
}
int main() {
cin >> n >> m;
dishes.resize(n);
flavor_count.assign(m, 0);
for (int i = 0; i < n; ++i)
cin >> dishes[i];
backtrack(0, 0);
cout << min_dishes << '\n';
return 0;
}
Bài D
Cho hai dãy số A (độ dài n) và B (độ dài m). Cần gán mỗi phần tử trong B đến một phần tử trong A sao cho: mỗi phần tử A chỉ được dùng một lần, và giá trị A[i] > B[j]. Mục tiêu là tìm tổng nhỏ nhất của các phần tử A được chọn. Nếu không thể gán đủ, in -1.
Giải pháp:
- Sắp xếp cả hai dãy tăng dần.
- Dùng con trỏ duyệt
A, với mỗi phần tửB[j], tìm phần tử nhỏ nhất trongAlớn hơnB[j]mà chưa được dùng. - Kiểm tra tính khả thi: với mỗi
B[j], số phần tử trongAlớn hơn hoặc bằngB[j]phải không ít hơn số phần tử còn lại trongB(từjđến cuối).
Xem mã nguồn
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<long long> a(n), b(m);
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < m; ++i) cin >> b[i];
sort(a.begin(), a.end());
sort(b.begin(), b.end());
// Kiểm tra tính khả thi
for (int i = 0; i < m; ++i) {
int need = m - i;
auto it = upper_bound(a.begin(), a.end(), b[i]);
int available = a.end() - it;
if (available < need) {
cout << -1 << '\n';
return 0;
}
}
long long total = 0;
int j = 0;
for (int i = 0; i < m; ++i) {
while (j < n && a[j] <= b[i]) j++;
if (j < n) {
total += a[j];
j++;
}
}
cout << total << '\n';
return 0;
}