Vòng sơ khảo 2021 – RoboCom Robot Developer Competition
7-1: Ai cũng hiểu
Dữ liệu vào mẫu:
5 3 4 8 12 20 40 3 11 16 19 3 12 16 19 10 11 11 11 11 11 11 11 11 11 11
Dữ liệu ra mẫu:
Yes No Yes
Phân tích:
Vì giới hạn dữ liệu nhỏ, ta dùng vòng lặp bốn tầng O(n⁴) để sinh ra tất cả các tổng có thể của bốn số, sau đó kiểm tra từng truy vấn.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k, b, m;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
set<int> ok;
for (int i = 0; i < n - 3; ++i)
for (int j = i + 1; j < n - 2; ++j)
for (int l = j + 1; l < n - 1; ++l)
for (int r = l + 1; r < n; ++r) {
int sum = a[i] + a[j] + a[l] + a[r];
if (sum % 4 == 0) ok.insert(sum / 4);
}
while (k--) {
cin >> m;
bool flag = true;
for (int i = 0; i < m; ++i) {
cin >> b;
if (!ok.count(b)) flag = false;
}
cout << (flag ? "Yes\n" : "No\n");
}
return 0;
}
7-2: Cờ gỗ Phần Lan
Dữ liệu vào mẫu:
11 1 2 2 2 4 3 ... 2 -1 999
Dữ liệu ra mẫu:
1022 9
Phân tích:
Tổng điểm không đổi vì quân 1 điểm dù đổ riêng hay cùng lúc vẫn cho cùng điểm. Nhiệm vụ là tối thiểu số lần đánh. Các quân >1 điểm buộc phải đánh riêng. Với các quân 1 điểm, ta gom thành cụm liên tiếp trên cùng một đường thẳng (theo vector chỉ phương). Dùng map với key là vector tối giản (dx, dy), value là list các cặp (khoảng cách, điểm). Sắp xếp theo khoảng cách rồi đếm số cụm liên tiếp của quân 1 điểm.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, x, y, p, total = 0, cnt = 0;
cin >> n;
map<pair<int,int>, vector<pair<int,int>>> dirs;
while (n--) {
cin >> x >> y >> p;
total += p;
if (x != 0 && y != 0) {
int g = __gcd(abs(x), abs(y));
dirs[{x/g, y/g}].push_back({g, p});
} else {
if (x) dirs[{(x>0?1:-1), 0}].push_back({x, p});
else dirs[{0, (y>0?1:-1)}].push_back({y, p});
}
}
for (auto &[vec, lst] : dirs) {
sort(lst.begin(), lst.end());
int run = 0;
for (auto [dist, val] : lst) {
if (val == 1) {
run++;
} else {
if (run) { cnt++; run = 0; }
cnt++;
}
}
if (run) cnt++;
}
cout << total << " " << cnt << "\n";
return 0;
}
7-3: Đánh quái thăng cấp
Phân tích:
Yêu cầu: (1) Tìm điểm xuất phát sao cho năng lượng tối đa cần để đánh bại pháo đài xa nhất là nhỏ nhất. (2) Tìm đường đi từ điểm đó đến từng đích yêu cầu với năng lượng tối thiểu, nếu có nhiều đường thì chọn đường có tổng giá trị vũ khí lớn nhất.
Bước 1: Dùng Floyd-Warshall để tìm khoảng cách ngắn nhất giữa mọi cặp đỉnh, từ đó chọn đỉnh khởi đầu. Bước 2: Chạy Dijkstra cải tiến (lưu thêm giá trị vũ khí) để tìm đường đi thỏa mãn.
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
int n, m;
cin >> n >> m;
vector dis(n+1, vector<int>(n+1, INF));
vector e(n+1, vector<tuple<int,int,int>>());
for (int i=0; i<m; ++i) {
int u,v,w,val;
cin >> u >> v >> w >> val;
dis[u][v] = dis[v][u] = w;
e[u].push_back({v,w,val});
e[v].push_back({u,w,val});
}
// Floyd
for (int k=1; k<=n; ++k)
for (int i=1; i<=n; ++i)
for (int j=1; j<=n; ++j)
if (i!=j) dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
int src = 1, best = INF;
for (int i=1; i<=n; ++i) {
int mx = 0;
for (int j=1; j<=n; ++j) if (i!=j) mx = max(mx, dis[i][j]);
if (mx < best) { best = mx; src = i; }
}
cout << src << "\n";
// Dijkstra
vector<int> d(n+1, INF), val(n+1, 0), pre(n+1), vis(n+1);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
d[src]=0; pq.push({0, src});
while (!pq.empty()) {
auto [du, u] = pq.top(); pq.pop();
if (vis[u]) continue;
vis[u]=1;
for (auto [v, w, vv] : e[u]) {
if (vis[v]) continue;
if (d[v] > d[u] + w || (d[v] == d[u] + w && val[v] < val[u] + vv)) {
d[v] = d[u] + w;
val[v] = val[u] + vv;
pre[v] = u;
pq.push({d[v], v});
}
}
}
int k; cin >> k;
while (k--) {
int t; cin >> t;
vector<int> path;
for (int v = t; v != src; v = pre[v]) path.push_back(v);
path.push_back(src);
reverse(path.begin(), path.end());
for (int i=0; i<path.size(); ++i) {
if (i) cout << "->";
cout << path[i];
}
cout << "\n" << d[t] << " " << val[t] << "\n";
}
return 0;
}
7-4: Phòng chống dịch
Phân tích:
Do các thành phố bị phong tỏa dần theo thời gian, xử lý xuôi rất khó. Ta xử lý ngược: đầu tiên coi tất cả các thành phố sẽ bị phong tỏa là không tồn tại, nối các cạnh của các thành phố còn lại bằng DSU. Sau đó xử lý từ ngày cuối lên: với mỗi ngày, trả lời truy vấn (kiểm tra tính liên thông bằng DSU), rồi thêm thành phố bị phong tỏa vào đồ thị (gỡ bỏ phong tỏa).
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> fa, sz;
DSU(int n) : fa(n+1), sz(n+1,1) { iota(fa.begin(),fa.end(),0); }
int find(int x) { while(x!=fa[x]) x=fa[x]=fa[fa[x]]; return x; }
bool same(int x,int y) { return find(x)==find(y); }
bool merge(int x,int y) {
x=find(x); y=find(y);
if(x==y) return false;
if(sz[x]<sz[y]) swap(x,y);
fa[y]=x; sz[x]+=sz[y];
return true;
}
};
int main() {
int n,m,d;
cin >> n >> m >> d;
vector e(n+1, vector<int>());
for (int i=0; i<m; ++i) {
int a,b; cin >> a >> b;
e[a].push_back(b); e[b].push_back(a);
}
vector<vector<pair<int,int>>> queries(d);
vector<int> block(d), locked(n+1,0);
for (int i=0; i<d; ++i) {
int c,q; cin >> c >> q;
block[i]=c;
locked[c]=1;
while (q--) {
int x,y; cin >> x >> y;
queries[i].push_back({x,y});
}
}
DSU dsu(n);
for (int i=1; i<=n; ++i) if (!locked[i])
for (int v : e[i]) if (!locked[v]) dsu.merge(i,v);
vector<int> ans(d);
for (int i=d-1; i>=0; --i) {
int bad = 0;
for (auto [x,y] : queries[i]) if (!dsu.same(x,y)) bad++;
ans[i] = bad;
locked[block[i]] = 0;
for (int v : e[block[i]]) if (!locked[v]) dsu.merge(block[i], v);
}
for (int x : ans) cout << x << "\n";
return 0;
}
Vòng bán kết 2021 – RoboCom Robot Developer Competition
7-1: Đội mạo hiểm
Phân tích:
Xử lý chênh lệch giữa chỉ số mục tiêu và ban đầu (đã chia 20). Điều kiện khả thi: tổng chênh lệch = 0, mọi chênh lệch chia hết cho 20, cùng số dư khi chia 3. Sau đó tìm số thao tác tối thiểu dựa trên dạng chênh lệch (một dương, một âm, một không; hoặc hai dương một âm…).
#include <bits/stdc++.h>
using namespace std;
int main() {
int T; cin >> T;
while (T--) {
vector<int> a(3), b(3), c(3);
for (int i=0; i<3; ++i) cin >> a[i];
for (int i=0; i<3; ++i) cin >> b[i];
int sum=0; bool bad=false;
for (int i=0; i<3; ++i) {
c[i]=b[i]-a[i];
if (abs(c[i])%20) bad=true;
sum+=c[i];
c[i]/=20;
}
int mod = (c[0]%3+3)%3;
for (int i=1; i<3; ++i) if ((c[i]%3+3)%3 != mod) bad=true;
if (bad || sum) { cout << -1 << "\n"; continue; }
sort(c.begin(), c.end());
int ans = 0;
if (c[0]*c[1] < 0) { // one positive, one negative, one zero
ans = min(abs(c[1]), abs(c[2]));
int idx = (c[0]<0 ? 0 : (c[1]<0 ? 1 : 2));
c[idx] = -abs(c[idx]);
} else {
ans = min(abs(c[0]), abs(c[1]));
int idx = (c[0]>=0 ? 2 : 0);
c[idx] = -abs(c[idx]);
}
c[0] -= (c[0]>0?1:-1)*2*ans; // simplify approach from editorial
// the rest is handled by combinations of (1,1,-2) and (3,0,-3)
if (c[0] != 0) ans += (abs(c[0])/3)*2;
cout << ans << "\n";
}
return 0;
}
7-2: Phần thưởng chấm bài A
Phân tích:
Bài toán ba lô 0/1 với thời gian lớn (m lớn) nhưng tổng giá trị nhỏ (n*30). Ta đảo ngược: dp[j] = thời gian tối thiểu để đạt được j giá trị.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> t(n), c(n), sum(n);
for (int i=0; i<n; ++i) cin >> t[i];
for (int i=0; i<n; ++i) cin >> c[i];
int maxVal = n*30;
const int INF = 1e9;
vector<int> dp(maxVal+1, INF);
dp[0]=0;
int best=0;
for (int i=0; i<n; ++i) {
for (int j=maxVal; j>=c[i]; --j) {
if (dp[j-c[i]] != INF && dp[j-c[i]] + t[i] <= m) {
dp[j] = min(dp[j], dp[j-c[i]] + t[i]);
best = max(best, j);
}
}
}
cout << best << "\n";
return 0;
}
Vòng chung kết 2021 – RoboCom Robot Developer Competition
7-1: Hàng rào xanh
Phân tích:
Mô phỏng bước đi theo các điểm uốn. Với mỗi bước, nếu độ dài tích lũy chia hết cho L thì đánh dấu cọc. Cần xử lý cả đoạn cuối từ điểm uốn cuối về (0,0).
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, L;
cin >> n >> L;
vector<pair<int,int>> fence;
fence.push_back({0,0});
int x=0,y=0, len=0;
for (int i=0; i<n; ++i) {
int c; cin >> c;
int &var = (i%2==0 ? x : y);
int step = (c > var ? 1 : -1);
while (var != c) {
var += step;
++len;
if (len % L == 0) {
fence.push_back({x,y});
}
}
}
// come back to origin
int &var = (n%2==0 ? x : y);
int step = (0 > var ? 1 : -1);
while (var != 0) {
var += step;
++len;
if (len % L == 0) {
fence.push_back({x,y});
}
}
if (!fence.empty() && fence.back().first==0 && fence.back().second==0)
fence.pop_back();
for (auto &p : fence) cout << p.first << " " << p.second << "\n";
return 0;
}
7-3: Cảnh báo an toàn tài khoản
Phân tích:
Bài toán xử lý dữ liệu lớn: đếm số IP khác nhau cho mỗi email, nếu vượt ngưỡng thì cảnh báo. Sắp xếp kết quả theo số IP giảm dần (và email tăng dần). Đầu ra cần liệt kê các IP kèm số lần xuất hiện cho mỗi email cảnh báo.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, tip, tin;
cin >> n >> tip >> tin;
map<string, set<string>> cntIP;
map<string, map<string,int>> freq;
map<string, int> total;
while (n--) {
string email, ip;
cin >> email >> ip;
cntIP[email].insert(ip);
freq[email][ip]++;
total[email]++;
}
vector<pair<string,int>> warns;
for (auto &[em, st] : cntIP) {
if ((int)st.size() > tip && total[em] > tin)
warns.push_back({em, (int)st.size()});
}
sort(warns.begin(), warns.end(), [](auto &a, auto &b){
if (a.second != b.second) return a.second > b.second;
return a.first < b.first;
});
if (warns.empty()) {
// fallback: email with max distinct IPs
int mx = 0;
for (auto &[em, st] : cntIP) mx = max(mx, (int)st.size());
for (auto &[em, st] : cntIP) if ((int)st.size() == mx) warns.push_back({em, mx});
sort(warns.begin(), warns.end());
}
for (auto &[em, _] : warns) {
cout << em << "\n";
vector<pair<string,int>> ips;
for (auto &[ip, f] : freq[em]) ips.push_back({ip, f});
sort(ips.begin(), ips.end(), [](auto &a, auto &b){
if (a.second != b.second) return a.second > b.second;
return a.first < b.first;
});
for (auto &[ip, f] : ips) cout << ip << " " << f << "\n";
}
return 0;
}
Vòng tỉnh 2024 – CAIP (Nhóm Đại học)
RC-u1: Nóng nóng nóng
void solve() {
int n, w; cin >> n >> w;
int a=0, b=0;
for (int i=0, t; i<n; ++i) {
cin >> t;
if (t >= 35) {
if (w == 4) ++b; else ++a;
}
w = w % 7 + 1;
}
cout << a << " " << b << "\n";
}
RC-u2: Ai vào offline?
void solve() {
int n; cin >> n;
vector<int> score(21,0);
auto point = [](int p) {
if (p==1) return 12; if (p==2) return 9; if (p==3) return 7;
if (p==4) return 5; if (p==5) return 4; if (p<=7) return 3;
if (p<=10) return 2; if (p<=15) return 1; return 0;
};
for (int i=0; i<n; ++i)
for (int j=0; j<20; ++j) {
int p, k; cin >> p >> k;
score[j] += k + point(p);
}
for (int i=0; i<20; ++i) cout << i+1 << " " << score[i] << "\n";
}
RC-u3: Lò sưởi và chuột lang nước
void solve() {
int n,m; cin >> n >> m;
vector<string> g(n);
for (int i=0; i<n; ++i) cin >> g[i];
int dx[8]={-1,-1,-1,0,1,1,1,0}, dy[8]={-1,0,1,1,1,0,-1,-1};
vector status(n, vector<int>(m,0));
for (int i=0; i<n; ++i) for (int j=0; j<m; ++j) {
if (g[i][j]=='c') {
status[i][j]=1;
for (int d=0; d<8; ++d) {
int x=i+dx[d], y=j+dy[d];
if (x>=0&&x<n&&y>=0&&y<m) status[x][y]=-1;
}
} else if (g[i][j]=='w') status[i][j]=2;
else if (g[i][j]=='m') status[i][j]=3;
}
set<pair<int,int>> ans;
for (int i=0; i<n; ++i) for (int j=0; j<m; ++j) {
if (status[i][j]==2) {
bool ok = false;
for (int d=0; d<8; ++d) {
int x=i+dx[d], y=j+dy[d];
if (x>=0&&x<n&&y>=0&&y<m && status[x][y]==3) { ok=true; break; }
}
if (!ok) {
for (int d=0; d<8; ++d) {
int x=i+dx[d], y=j+dy[d];
if (x>=0&&x<n&&y>=0&&y<m && status[x][y]==0) ans.insert({x+1,y+1});
}
}
}
}
if (ans.empty()) cout << "Too cold!\n";
else for (auto [x,y] : ans) cout << x << " " << y << "\n";
}
RC-u5: Sắp xếp công việc
void solve() {
int n; cin >> n;
struct Task { int t, d, p; };
vector<Task> a(n);
for (int i=0; i<n; ++i) cin >> a[i].t >> a[i].d >> a[i].p;
sort(a.begin(), a.end(), [](Task &x, Task &y){ return x.d < y.d; });
int maxDeadline = 5000;
vector<int> dp(maxDeadline+1, 0);
for (auto &task : a) {
int t=task.t, d=task.d, p=task.p;
if (t == 0) { dp[0] += p; continue; }
for (int j = min(maxDeadline, d); j >= t; --j)
dp[j] = max(dp[j], dp[j-t] + p);
}
int ans = *max_element(dp.begin(), dp.end());
cout << ans << "\n";
}
Vòng quốc gia 2024 – CAIP (Nhóm Đại học)
RC-u1: Cùng nhau kiểm tra gian lận
void solve() {
auto isAlnum = [](char c) { return isalnum(c); };
int cnt[3]={0,0,0};
auto upd = [&](char c) {
if (islower(c)) cnt[0]++;
else if (isupper(c)) cnt[1]++;
else cnt[2]++;
};
string s; int points=0, len=0, words=0;
while (cin >> s) {
for (int l=0,r=0; l<(int)s.size(); ) {
while (l<(int)s.size() && !isAlnum(s[l])) ++l;
if (l>=(int)s.size()) break;
cnt[0]=cnt[1]=cnt[2]=0;
upd(s[l]); r=l+1;
while (r<(int)s.size() && isAlnum(s[r])) { upd(s[r]); ++r; }
--r;
if (l<=r) {
words++;
len += r-l+1;
if (cnt[0]&&cnt[1]&&cnt[2]) points+=5;
else if (cnt[2]&&(cnt[0]||cnt[1])) points+=3;
else if (cnt[0]&&cnt[1]) points+=1;
}
l=r+1; ++r;
}
}
cout << points << "\n" << len << " " << words << "\n";
}
RC-u2: Ai vào offline? II
void solve() {
int point[] = {0,25,21,18,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0};
int n; cin >> n;
map<int,int> tot;
for (int i=0; i<n; ++i)
for (int j=0; j<20; ++j) {
int c, p; cin >> c >> p;
tot[c] += point[p];
}
vector<pair<int,int>> v(tot.begin(), tot.end());
sort(v.begin(), v.end(), [](auto &a, auto &b){
if (a.second != b.second) return a.second > b.second;
return a.first < b.first;
});
for (auto [id, sc] : v) cout << id << " " << sc << "\n";
}
RC-u3: Cân sức ngang tài
void solve() {
int n; cin >> n;
vector<int> a(n);
for (int i=0; i<n; ++i) cin >> a[i];
if (n==3) {
for (int i=0; i<3; ++i) {
long long val = a[i]*100 + a[(i+1)%3]*10 + a[(i+2)%3];
cout << val << "\n";
}
} else if (n==4) {
auto process = [&](vector<int> b) {
long long sum=0;
for (int i=0; i<4; ++i) {
long long val = b[i]*1000 + b[(i+1)%4]*100 + b[(i+2)%4]*10 + b[(i+3)%4];
cout << val << "\n";
sum += val*val;
}
};
process(a);
process({a[0], a[2], a[3], a[1]});
process({a[0], a[3], a[1], a[2]});
}
}
RC-u4: City hay không City?
void solve() {
int n,m,s,t;
cin >> n >> m >> s >> t;
vector<int> rating(n+1);
for (int i=1; i<=n; ++i) cin >> rating[i];
vector e(n+1, vector<pair<int,int>>());
for (int i=0; i<m; ++i) {
int u,v,w; cin >> u >> v >> w;
e[u].push_back({v,w});
e[v].push_back({u,w});
}
const int INF = 1e9;
vector<int> dist(n+1,INF), bestRating(n+1,0), vis(n+1,0);
dist[s]=0; bestRating[s]=rating[s];
struct Node {
int d, r, id;
bool operator<(const Node &o) const {
if (d != o.d) return d > o.d;
return r < o.r;
}
};
priority_queue<Node> pq;
pq.push({0, rating[s], s});
while (!pq.empty()) {
auto [d, r, u] = pq.top(); pq.pop();
if (vis[u]) continue;
vis[u]=1;
if (u != s) bestRating[u] = max(bestRating[u], rating[u]);
for (auto [v, w] : e[u]) {
if (vis[v]) continue;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
bestRating[v] = bestRating[u];
pq.push({dist[v], bestRating[v], v});
} else if (dist[v] == dist[u] + w && bestRating[v] < bestRating[u]) {
bestRating[v] = bestRating[u];
pq.push({dist[v], bestRating[v], v});
}
}
}
if (dist[t] == INF) cout << "Impossible\n";
else cout << dist[t] << " " << bestRating[t] << "\n";
}