Editorial for ptit050: Tỉ lệ AC

Hiểu bài toán

Cho một người dùng đã có a bài nộp thành công trên tổng số b bài nộp (tỉ lệ a/b). Yêu cầu tìm số bài nộp thêm ít nhất (ký hiệu là x) sao cho sau khi nộp thêm x bài mới (tất cả đều thành công), tỉ lệ thành công mới trở thành đúng bằng c/d (sau khi tối giản phân số này). Nếu không thể đạt được, in ra -1.

Phân tích bài toán: Gọi x là số bài nộp thêm. Số bài nộp thành công mới là a + x. Tổng số bài nộp mới là b + x. Ta cần tìm x nhỏ nhất sao cho: (a + x) / (b + x) = c / d

Từ phương trình này, ta có thể biến đổi: d * (a + x) = c * (b + x) d*a + d*x = c*b + c*x (d - c) * x = c*b - d*a x = (c*b - d*a) / (d - c)

Các trường hợp cần xét:

1. d - c = 0 (tức là c/d = 1): Nếu a/b = 1 thì x = 0. Nếu a/b < 1 thì không thể đạt được (vì x phải dương, nhưng x không xác định hoặc vô cực). Nếu a/b > 1 (không thể xảy ra theo đề bài a <= b) thì x = 0.
2. d - c != 0: Tính giá trị x theo công thức. Nếu x >= 0 và là số nguyên thì đáp án là x. Nếu không, -1.

Lưu ý:

• c/d có thể không tối giản, cần tối giản trước.
• x phải là số nguyên không âm.
• d - c và c*b - d*a có thể rất lớn (vượt quá 64-bit), cần xử lý số học lớn (bằng __int128 hoặc thư viện big number, hoặc phân tích để tránh tràn số).
• a, b, c, d có thể lên tới 10^9.

Các cách tiếp cận

Cách Giải thích

// Phân tích bài toán:
// Mục tiêu: Tim so bai nop them x (x >= 0, x nguyen) sao cho (a + x) / (b + x) = c / d.
// Ta rut gon phan so c/d bang UCLN(c, d).
// Tu phuong trinh: d*(a + x) = c*(b + x) => (d - c)*x = c*b - d*a.
// Truong hop 1: d = c (tuc ti le la 1/1).
//      Neu a = b (ti le hien tai la 1) => x = 0.
//      Neu a < b (ti le hien tai < 1) => khong the dat ti le 1 (vi x phai > 0, nhung phuong trinh vo nghiem hoac vo cuc).
// Truong hop 2: d != c.
//      Neu (d - c) chia het cho (c*b - d*a) va (c*b - d*a) * (d - c) >= 0 (cung dau).
//      Kiem tra xem x co >= 0 va la so nguyen khong.
//      Nho rang a <= b va c <= d.
//      Neu c < d va a < b, co the can them x.
//      Neu c > d (khong the xay ra vi c <= d).
//      Neu c = d da xet.
//      Neu a = b va c < d (ti le a/b = 1, c/d < 1) => Khong the giam xuong duoi 1.
//      Neu a < b va c = d (ti le a/b < 1, c/d = 1) => Khong the len 1.
//      Neu a = b va c = d (1 = 1) => x = 0.
//      Neu a < b va c < d => Co kha nang.
//      Cong thuc: x = (c*b - d*a) / (d - c).
//      Vi du: a=3, b=10, c=1, d=2. x = (10 - 20) / (2 - 1) = -10 / 1 = -10 (Sai).
//      Sua lai: (c*b - d*a) phai duong.
//      Neu (d - c) > 0 (c < d), can (c*b - d*a) > 0 => c*b > d*a => a/b < c/d.
//      Neu (d - c) < 0 (c > d, cai nay khong xay ra vi c <= d).
//      Nhu vieu, chi can xet truong hop (d - c) > 0.
//      Kiem tra: (c*b - d*a) % (d - c) == 0 va (c*b - d*a) >= 0.
//      Neu (c*b - d*a) < 0 => x < 0 => Khong the.
//      Neu (c*b - d*a) == 0 => x = 0 (Neu a/b = c/d).
//      Kiem tra so lon: c*b va d*a co the vuot qua 64-bit. Can su dung __int128.

• Time Complexity: O(log(min(c, d))) cho UCLN
• Space Complexity: O(1)

Đây là lời giải chi tiết cho bài toán.

Bước 1: Tối giản phân số mục tiêu Đầu tiên, ta cần tối giản phân số c/d bằng cách chia cả tử số và mẫu số cho UCLN(c, d). Gọi kết quả là c_opt và d_opt.

Bước 2: Phân tích phương trình Ta cần tìm x sao cho (a + x)/(b + x) = c_opt/d_opt. Phương trình biến đổi thành: d_opt * (a + x) = c_opt * (b + x) d_opt*a + d_opt*x = c_opt*b + c_opt*x (d_opt - c_opt) * x = c_opt*b - d_opt*a

Bước 3: Xử lý các trường hợp

1. Trường hợp d_opt = c_opt: Tỉ lệ mục tiêu là 1/1.

   • Nếu a = b (tỉ lệ hiện tại là 1), Tony đã đạt yêu cầu. x = 0.
   • Nếu a < b (tỉ lệ hiện tại < 1), không thể đạt tỉ lệ 1 bằng cách thêm bài nộp (vì a+x <= b+x nếu x >= 0 nên tỉ lệ không bao giờ vượt quá 1). Trả về -1.

2. Trường hợp d_opt > c_opt: Tỉ lệ mục tiêu nhỏ hơn 1.

   • Ta cần x >= 0. Do d_opt > c_opt nên (d_opt - c_opt) là số dương. Để x dương (hoặc 0), ta cần (c_opt*b - d_opt*a) cũng là số dương hoặc 0.
   • Điều kiện c_opt*b - d_opt*a >= 0 tương đương với a/b <= c_opt/d_opt. Nếu a/b > c_opt/d_opt (tỉ lệ hiện tại lớn hơn mục tiêu), ta không thể giảm tỉ lệ bằng cách thêm bài nộp thành công. Trả về -1.
   • Kiểm tra tính chia hết: (c_opt*b - d_opt*a) phải chia hết cho (d_opt - c_opt).
   • Nếu thỏa mãn cả hai, x = (c_opt*b - d_opt*a) / (d_opt - c_opt) là đáp án.

Vấn đề số lớn: Vì a, b, c, d lên tới 10^9, các phép nhân c*b hay d*a có thể lên tới 10^{18}, vượt quá giới hạn của long long (khoảng 9.2 imes 10^{18}). Cần dùng __int128 (trong C/C++) hoặc thư viện big number để tính toán chính xác.

Ví dụ: a=3, b=10, c=1, d=2 c_opt=1, d_opt=2 d_opt > c_opt. c_opt*b - d_opt*a = 1*10 - 2*3 = 10 - 6 = 4 (>= 0). d_opt - c_opt = 2 - 1 = 1. 4 % 1 == 0. x = 4 / 1 = 4.

Cách Approach 2 (Sử dụng số lớn)

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

// Hàm tính UCLN
long long gcd(long long a, long long b) {
    while (b) {
        long long t = a % b;
        a = b;
        b = t;
    }
    return a;
}

void solve() {
    long long a, b, c, d;
    cin >> a >> b >> c >> d;

    // Tối giản c/d
    long long g = gcd(c, d);
    c /= g;
    d /= g;

    // Truong hop dac biet: ti le muc tieu la 1/1
    if (c == d) {
        if (a == b) {
            cout << 0 << "\n";
        } else {
            cout << -1 << "\n";
        }
        return;
    }

    // Truong hop chung: d > c (vi c <= d va c != d)
    // Can tim x: (a + x) / (b + x) = c / d
    // => d(a + x) = c(b + x)
    // => (d - c)x = cb - da
    // => x = (cb - da) / (d - c)

    // Su dung __int128 de tranh tràn số
    __int128 _a = a, _b = b, _c = c, _d = d;
    __int128 num = _c * _b - _d * _a;
    __int128 den = _d - _c;

    // Neu mau so am (khong the xay ra vi d > c) hoac tu so am (khong the dat duoc)
    if (num < 0) {
        cout << -1 << "\n";
        return;
    }

    if (num % den != 0) {
        cout << -1 << "\n";
        return;
    }

    __int128 x = num / den;

    if (x < 0) {
        cout << -1 << "\n";
        return;
    }

    // In ket qua (ep kieu neu can, vi x duoc bao dam nho)
    cout << (long long)x << "\n";
}

int main() {
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

• Time Complexity: O(log(min(c, d)))
• Space Complexity: O(1)

Đây là cách tiếp cận trực tiếp từ công thức toán học.

1. Tối giản c/d: Sử dụng hàm gcd để tìm ước chung lớn nhất và chia cả c và d cho nó.
2. Xử lý c == d: Nếu c == d, tỉ lệ mục tiêu là 1.
   • Nếu a == b, tỉ lệ hiện tại là 1. Cần 0 bài nộp thêm.
   • Nếu a < b, tỉ lệ hiện tại < 1. Không thể đạt 1 bằng cách thêm bài nộp thành công. In -1.
3. Xử lý c < d:
   • Tính num = c*b - d*a và den = d - c.
   • Sử dụng __int128 cho các phép tính này để đảm bảo không tràn số.
   • Kiểm tra num >= 0. Nếu num < 0, x sẽ âm, không hợp lệ. In -1.
   • Kiểm tra num % den == 0. Nếu không chia hết, x không phải số nguyên. In -1.
   • Tính x = num / den. Đảm bảo x >= 0 (đã kiểm tra num >= 0 và den > 0).
   • In ra x.

Lưu ý: __int128 là kiểu dữ liệu mở rộng trong GCC/Clang, không chuẩn ISO C++. Tuy nhiên, trong lập trình thi đấu (đặc biệt trên các nền tảng như Codeforces, VietJudge, OJ của PTIT), nó thường được hỗ trợ và là cách dễ nhất để xử lý số lớn mà không cần thư viện phức tạp.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Biến đổi bài toán thành phương trình toán học (a+x)/(b+x) = c/d giúp giải quyết triệt để.
• Phải tối giản phân số c/d trước khi so sánh hay tính toán.
• Phép chia (c*b - d*a) / (d - c) có thể tạo ra số rất lớn (lên tới 10^{18}), bắt buộc phải sử dụng số lớn (__int128 hoặc BigInt).

Lỗi thường gặp

• Quên kiểm tra tính chia hết: (c*b - d*a) % (d - c) == 0. Nếu không chia hết thì không tồn tại x nguyên.
• Quên kiểm tra dấu của x: x phải là số không âm (x >= 0). Điều này tương đương với việc kiểm tra c*b >= d*a.
• Lỗi tràn số khi tính c*b hoặc d*a nếu dùng long long thay vì __int128.