Tìm mệt mỏi tối thiểu khi hai người gặp nhau trên trục Ox bằng C++

Mô tả bài toán

Hai bạn ở vị trí a và b trên trục Ox. Mỗi bước di chuyển 1 đơn vị, độ mệt tăng theo cấp số cộng: bước 1 mệt 1, bước 2 mệt 2,... Cần tìm tổng mệt mỏi nhỏ nhất để họ gặp nhau tại một điểm nguyên.

Ví dụ

a=5, b=10 → Khoảng cách = 5. Cách tối ưu: người 1 đi 3 bước, người 2 đi 2 bước. Mệt = 1+2+3 + 1+2 = 9.

Thuật toán

Khoảng cách d = |a-b|. Họ nên chia đều khoảng cách: một người đi floor(d/2), người kia đi ceil(d/2). Tổng mệt = sum(1..x) + sum(1..y) với x+y=d, x≈y. Công thức: sum = d/2; kết quả = (sum + d%2) * (sum + 1).

Code C++

#include <bits/stdc++.h>
using namespace std;

int solve(int a, int b) {
    int d = abs(a - b);
    int sum = d / 2;
    return (sum + (d % 2)) * (sum + 1);
}

int main() {
    int a = 5, b = 10;
    cout << solve(a, b) << endl;
    return 0;
}

Đầu vào / Đầu ra

Input: 5, 10

Output: 9