Hướng dẫn giải của [200 đề thầy Đức] Bài 194: Hoán đổi vị trí
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
John được đổi chỗ tối đa x lần hai con bò liền kề. Hãy tìm khoảng cách lớn nhất có thể có giữa Bessie (vị trí a) và Elsie (vị trí b).
Cách làm
Khoảng cách ban đầu là d = |a - b|. Mỗi lần đổi chỗ, một trong hai con bò đi thêm đúng một bước, nên khoảng cách tăng thêm tối đa x, tức là kq = d + x. Khoảng cách trong hàng n con bò không thể vượt quá n - 1, nên nếu kq > n - 1 thì lấy kq = n - 1.
Ví dụ: n = 5, x = 1, a = 3, b = 2 thì d = 1, kq = 2.
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, x, a, b;
cin >> n >> x >> a >> b;
// Khoảng cách ban đầu giữa Bessie và Elsie
int d = abs(a - b);
// Mỗi lần tráo đổi có thể làm khoảng cách tăng thêm tối đa 1,
// nên sau x lần khoảng cách tối đa là d + x
int kq = d + x;
// Khoảng cách lớn nhất có thể trong hàng n con bò là n - 1
if (kq > n - 1) {
kq = n - 1;
}
cout << kq << "\n";
}
return 0;
}
Bình luận