Bài A - Tháng Chín
Bài toán: Cho 12 chuỗi, hãy đếm số lượng chuỗi có độ dài bằng chỉ mục của nó.
Hướng tiếp cận: Duyệt qua từng chuỗi và kiểm tra điều kiện về độ dài.
Xem mã nguồn
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
vector<string> strings(12);
int count = 0;
for (int i = 0; i < 12; ++i) {
cin >> strings[i];
if (strings[i].size() == (i + 1)) {
count++;
}
}
cout << count << "\n";
return 0;
}
Bài B - Bàn Phím Một Chiều
Bài toán: Có 26 chữ cái từ A đến Z. Bắt đầu từ A, mỗi bước di chuyển một ký tự. Tính tổng số bước để đi từ A đến Z.
Hướng tiếp cận: Sử dụng mảng để lưu vị trí các ký tự và tính tổng khoảng cách giữa chúng.
Xem mã nguồn
#include <iostream>
#include <vector>
using namespace std;
void process() {
string input;
cin >> input;
vector<int> positions(26, 0);
for (size_t i = 0; i < input.size(); ++i) {
positions[input[i] - 'A'] = static_cast<int>(i);
}
int totalSteps = 0;
for (int i = 1; i < 26; ++i) {
totalSteps += abs(positions[i] - positions[i - 1]);
}
cout << totalSteps << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
process();
return 0;
}
Bài C - Tổng Hai Mảng
Bài toán: Cho hai dãy số có độ dài n, tìm giá trị lớn nhất của tổng hai phần tử lấy từ mỗi dãy.
Hướng tiếp cận: Tìm phần tử lớn nhất trong mỗi dãy rồi cộng chúng lại.
Xem mã nguồn
#include <iostream>
#include <vector>
using namespace std;
void solve() {
int size;
cin >> size;
vector<int> array1(size), array2(size);
int max1 = INT32_MIN, max2 = INT32_MIN;
for (int& num : array1) {
cin >> num;
max1 = max(max1, num);
}
for (int& num : array2) {
cin >> num;
max2 = max(max2, num);
}
cout << (max1 + max2) << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
solve();
return 0;
}
Bài D - Trọng Số Ẩn
Bài toán: Cho n đỉnh và m cạnh cùng trọng số w. Gán mỗi đỉnh một giá trị sao cho thỏa mãn điều kiện x_v - x_u = w.
Hướng tiếp cận: Sử dụng thuật toán DFS để duyệt qua các đỉnh và gán giá trị theo công thức.
Xem mã nguồn
#include <iostream>
#include <vector>
using namespace std;
struct Edge {
int to, weight;
};
vector adjList;
vector<int> values;
vector<bool> visited;
void dfs(int node, int val) {
visited[node] = true;
values[node] = val;
for (auto& edge : adjList[node]) {
if (!visited[edge.to]) {
dfs(edge.to, val + edge.weight);
}
}
}
void resolve() {
int nodes, edges;
cin >> nodes >> edges;
adjList.assign(nodes, vector<Edge>());
values.assign(nodes, 0);
visited.assign(nodes, false);
for (int i = 0; i < edges; ++i) {
int u, v, w;
cin >> u >> v >> w;
--u; --v;
adjList[u].push_back({v, w});
adjList[v].push_back({u, -w});
}
for (int i = 0; i < nodes; ++i) {
if (!visited[i]) {
dfs(i, 0);
}
}
for (int i = 0; i < nodes; ++i) {
cout << values[i] << " ";
}
cout << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
resolve();
return 0;
}
Bài E - Chiến Thắng Trong Cuộc Bầu Cử
Bài toán: Có n người tham gia bầu cử với k lá phiếu còn lại. Mỗi người đã có một số phiếu ban đầu. Xác định số phiếu tối thiểu cần thêm để đảm bảo chiến thắng.
Hướng tiếp cận: Sử dụng thuật toán nhị phân để tìm số phiếu cần thiết cho mỗi người.
Xem mã nguồn
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool canWin(int idx, int extraVotes, const vector<int>& sortedVotes, int remainingVotes, int m) {
int newVotes = sortedVotes[idx] + extraVotes;
int neededVotes = 0;
auto it = upper_bound(sortedVotes.begin(), sortedVotes.end(), newVotes) - sortedVotes.begin();
if (it < m) return false;
for (int i = 0; i < it && i < m; ++i) {
neededVotes += (newVotes + 1 - sortedVotes[i]);
}
return neededVotes <= remainingVotes;
}
void election() {
int n, m, k;
cin >> n >> m >> k;
vector<int> votes(n);
for (auto& vote : votes) cin >> vote;
vector<int> sortedVotes = votes;
sort(sortedVotes.begin(), sortedVotes.end(), greater<int>());
vector<int> results(n);
for (int i = 0; i < n; ++i) {
int low = 0, high = k, result = -1;
while (low <= high) {
int mid = (low + high) / 2;
if (canWin(i, mid, sortedVotes, k - mid, m)) {
result = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
results[i] = result;
}
for (auto res : results) cout << res << " ";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
election();
return 0;
}