Bài A – Hộp Bảo Bối
Xuất phát từ một chuỗi ký tự gồm ba ký hiệu đặc biệt: '|' (hai dấu gạch đứng biểu thị hai cạnh của hộp) và '*' (một ngôi sao đại diện cho vật phẩm). Nhiệm vụ là xác định xem ngôi sao nằm bên trong hay bên ngoài hộp — tức là có nằm giữa hai dấu gạch hay không.
Cách tiếp cận đơn giản: duyệt chuỗi để ghi nhận vị trí đầu tiên và cuối cùng của dấu '|', đồng thời lưu vị trí của dấu '*'. Sau đó kiểm tra điều kiện: vị_trí_gạch_đầu < vị_trí_sao < vị_trí_gạch_cuối.
#include <iostream>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
string seq;
cin >> seq;
int left = -1, right = -1, star = -1;
for (int i = 0; i < n; ++i) {
if (seq[i] == '|') {
if (left == -1) left = i;
else right = i;
} else if (seq[i] == '*') {
star = i;
}
}
if (star != -1 && left != -1 && right != -1 && left < star && star < right) {
cout << "in\n";
} else {
cout << "out\n";
}
}
Bài B – Chiến Thuật Đánh Bài
Cho n người chơi, mỗi người có một màu bài (số nguyên dương) và một điểm số. Một "màu chủ đạo" t được chọn trước. Nếu không ai sở hữu màu t, thì người đầu tiên (chỉ số 0) sẽ thay thế làm tiêu chuẩn. Người chiến thắng là người có điểm cao nhất trong số những người dùng màu chủ đạo.
Cài đặt: đọc danh sách màu và điểm; xác định màu thực tế sẽ áp dụng; duyệt tuyến tính để tìm chỉ số người có điểm lớn nhất với màu khớp.
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, t;
cin >> n >> t;
vector<int> colors(n), scores(n);
set<int> available_colors;
for (int i = 0; i < n; ++i) {
cin >> colors[i];
available_colors.insert(colors[i]);
}
for (int i = 0; i < n; ++i) {
cin >> scores[i];
}
int target = available_colors.count(t) ? t : colors[0];
int best_idx = 0;
int best_score = -1;
for (int i = 0; i < n; ++i) {
if (colors[i] == target && scores[i] > best_score) {
best_score = scores[i];
best_idx = i + 1; // chỉ số bắt đầu từ 1
}
}
cout << best_idx << '\n';
}
Bài C – Món Bánh Dango
Một dãy ký tự gồm hai loại: 'o' (bánh tròn) và '-' (que tre). Mỗi cụm liên tiếp các chữ 'o' được coi là một xiên dango. Yêu cầu tìm độ dài lớn nhất của một xiên như vậy. Nếu không tồn tại cả 'o' lẫn '-', hoặc thiếu một trong hai, in ra -1.
Giải pháp: quét chuỗi, khi gặp 'o', đếm độ dài đoạn con liên tiếp toàn 'o'; cập nhật giá trị cực đại. Trước đó kiểm tra sự hiện diện của cả hai ký tự.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int len;
cin >> len;
string s;
cin >> s;
if (s.find('o') == string::npos || s.find('-') == string::npos) {
cout << "-1\n";
return 0;
}
int max_len = 0;
int i = 0;
while (i < len) {
if (s[i] == 'o') {
int j = i;
while (j < len && s[j] == 'o') ++j;
max_len = max(max_len, j - i);
i = j;
} else {
++i;
}
}
cout << max_len << '\n';
}
Bài D – Tìm Giá Trị Qua Truy Vấn Tương Tác
Biết rằng một mảng nhị phân độ dài n có dạng [0, ..., 0, 1, ..., 1] — toàn 0 ở đầu, toàn 1 ở cuối, và tồn tại đúng một vị trí chuyển tiếp từ 0 sang 1. Bạn được phép đặt tối đa 20 câu hỏi dạng "? x", và hệ thống trả về giá trị tại vị trí x. Mục tiêu là xác định chỉ số nhỏ nhất có giá trị 1.
Do cấu trúc đơn điệu, ta áp dụng tìm kiếm nhị phân trên khoảng [1, n]. Với mỗi truy vấn tại mid, nếu kết quả là 1, thì ranh giới nằm ở nửa trái (bao gồm mid); ngược lại nằm ở nửa phải. Khi khoảng còn lại hai phần tử liền kề, phần tử bên trái chính là đáp án.
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int low = 1, high = n;
for (int step = 0; step < 20; ++step) {
if (high - low == 1) {
cout << "! " << low << '\n';
return 0;
}
int mid = (low + high) / 2;
cout << "? " << mid << '\n';
cout.flush();
int val;
cin >> val;
if (val == 1) {
high = mid;
} else {
low = mid;
}
}
}
Bài E – Đỉnh Đen Gần Nhất
Cho đồ thị vô hướng gồm n đỉnh và m cạnh. Cần tô màu mỗi đỉnh bằng 0 (trắng) hoặc 1 (đen) sao cho thỏa mãn k ràng buộc dạng: "khoảng cách ngắn nhất từ đỉnh pᵢ đến một đỉnh đen nào đó phải đúng bằng dᵢ". Điều này ngụ ý: (1) mọi đỉnh trong bán kính < dᵢ quanh pᵢ đều phải trắng; (2) ít nhất một đỉnh ở đúng khoảng cách dᵢ phải đen.
Cách giải: với mỗi pᵢ, chạy BFS để tính khoảng cách tới tất cả đỉnh khác. Khởi tạo toàn bộ đỉnh là đen (1). Áp dụng từng ràng buộc: đánh dấu trắng tất cả đỉnh trong bán kính < dᵢ. Sau đó kiểm tra xem có tồn tại ít nhất một đỉnh ở khoảng cách = dᵢ vẫn còn đen hay không. Nếu không, bài toán vô nghiệm.
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u; --v;
graph[u].push_back(v);
graph[v].push_back(u);
}
// dist[i][j]: khoảng cách từ i đến j
vector<vector<int>> dist(n, vector<int>(n, INT_MAX));
for (int start = 0; start < n; ++start) {
queue<int> q;
dist[start][start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (dist[start][v] > dist[start][u] + 1) {
dist[start][v] = dist[start][u] + 1;
q.push(v);
}
}
}
}
int k;
cin >> k;
vector<int> color(n, 1); // mặc định đen
vector<int> centers(k), thresholds(k);
for (int i = 0; i < k; ++i) {
cin >> centers[i] >> thresholds[i];
--centers[i];
// Đánh trắng các đỉnh gần hơn ngưỡng
for (int v = 0; v < n; ++v) {
if (dist[centers[i]][v] < thresholds[i]) {
color[v] = 0;
}
}
}
// Kiểm tra mỗi ràng buộc: có ít nhất một đỉnh đen ở đúng khoảng cách
for (int i = 0; i < k; ++i) {
bool found = false;
for (int v = 0; v < n; ++v) {
if (dist[centers[i]][v] == thresholds[i] && color[v] == 1) {
found = true;
break;
}
}
if (!found) {
cout << "No\n";
return 0;
}
}
cout << "Yes\n";
for (int c : color) cout << c;
cout << '\n';
}