Editorial for gheptg: Ghép tam giác

Hiểu bài toán

Cho ba thanh nhựa có độ dài nguyên dương a, b, c. Nhiệm vụ là tìm thời gian tối thiểu (tính bằng phút) cần để kéo giãn một số thanh (mỗi đơn vị độ dài tốn 1 phút) sao cho ba thanh có thể tạo thành một tam giác có diện tích dương.

Điều kiện để ba đoạn thẳng tạo thành một tam giác là: tổng độ dài của hai cạnh ngắn nhất phải lớn hơn độ dài của cạnh dài nhất. Nếu gọi ba cạnh đã sắp xếp theo thứ tự tăng dần là x, y, z (với z là cạnh dài nhất), điều kiện này là: x + y > z.

Nếu tam giác đã hợp lệ (x + y > z), thời gian cần thiết là 0. Nếu chưa hợp lệ, ta cần tăng độ dài của các cạnh sao cho điều kiện thỏa mãn. Do chi phí tăng độ dài của bất kỳ cạnh nào đều như nhau (1 đơn vị độ dài tốn 1 phút), ta nên tập trung vào việc đáp ứng điều kiện tam giác một cách tối ưu nhất.

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

Cách Phân tích trực tiếp theo điều kiện tam giác

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(long long*)a - *(long long*)b);
}

int main() {
    long long sides[3];
    scanf("%lld %lld %lld", &sides[0], &sides[1], &sides[2]);
    qsort(sides, 3, sizeof(long long), compare);

    long long x = sides[0];
    long long y = sides[1];
    long long z = sides[2];

    // Kiểm tra xem tam giác đã hợp lệ chưa
    if (x + y > z) {
        printf("0");
    } else {
        // Nếu không, ta cần tăng tổng của x và y lên để nó lớn hơn z.
        // Mục tiêu: x + y > z
        // Hiện tại: x + y <= z
        // Cần tăng tổng x + y lên: (x + y) + k > z => k > z - (x + y)
        // Giá trị nhỏ nhất của k là z - (x + y) + 1
        printf("%lld", z - (x + y) + 1);
    }
    return 0;
}

• Time Complexity: O(1) (hoặc O(log 3) do sắp xếp 3 phần tử)
• Space Complexity: O(1)

Cách tiếp cận này dựa trên việc nhận ra rằng để tạo thành tam giác, ta chỉ cần quan tâm đến tổng độ dài của hai cạnh ngắn nhất và cạnh dài nhất.

1. Sắp xếp ba cạnh theo thứ tự tăng dần: x ≤ y ≤ z.
2. Kiểm tra điều kiện tam giác: x + y > z.
3. Nếu thỏa mãn, đáp án là 0.
4. Nếu không thỏa mãn, ta cần tăng tổng độ dài của hai cạnh ngắn nhất (x và y) sao cho tổng này vượt quá z.
   • Chi phí tăng độ dài của x hay y là như nhau.
   • Lượng cần tăng thêm tối thiểu để (x + y) trở thành (z + 1) là: (z + 1) - (x + y).
   • Đáp án là z - (x - y) + 1. Lưu ý: Cần dùng kiểu dữ liệu long long để tránh tràn số vì a, b, c có thể lên tới 10^9.

Cách Kiểm tra từng trường hợp vi phạm

#include <stdio.h>

int main() {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    int x = a + b;
    int y = a + c;
    int z = b + c;
    // x là tổng của a, b (cạnh còn lại là c)
    // y là tổng của a, c (cạnh còn lại là b)
    // z là tổng của b, c (cạnh còn lại là a)

    if (x <= c) {
        printf("%d", c - x + 1);
    } else if (y <= b) {
        printf("%d", b - y + 1);
    } else if (z <= a) {
        printf("%d", a - z + 1);
    } else {
        printf("0");
    }
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Cách tiếp cận này kiểm tra trực tiếp từng trường hợp mà tam giác bị vi phạm. Một tam giác không hợp lệ khi một cạnh bằng hoặc lớn hơn tổng hai cạnh còn lại.

1. Tính tổng của từng cặp cạnh: a+b, a+c, b+c.
2. Kiểm tra từng cặp:
   • Nếu a + b <= c: Cạnh c quá dài. Ta cần tăng tổng a+b lên để nó lớn hơn c. Chi phí là c - (a+b) + 1. Sau khi tăng, tam giác (a', b', c) sẽ hợp lệ.
   • Tương tự cho các trường hợp a + c <= b và b + c <= a.
3. Nếu không có trường hợp nào bị vi phạm, tam giác đã hợp lệ, chi phí là 0. Cách này không cần sắp xếp nhưng logic kiểm tra rẽ nhánh cũng tương đương.

Cách Giải pháp Logic Đơn giản (Từ các submission)

#include <stdio.h>
int max(int a, int b) { return a > b ? a : b; }
int main() {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    int maxx = max(a, max(b, c));
    int tong = a + b + c - maxx; // Tổng của hai cạnh còn lại
    if (tong > maxx) printf("0");
    else printf("%d", maxx + 1 - tong);
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu nhất về mặt ngắn gọn.

1. Tìm cạnh dài nhất (maxx).
2. Tính tổng của hai cạnh còn lại (tong).
3. Điều kiện tam giác là tong > maxx.
   • Nếu đúng, in ra 0.
   • Nếu sai, ta cần tăng tổng tong lên để nó vượt quá maxx. Lượng cần tăng là maxx + 1 - tong. Đáp án chính là maxx + 1 - tong.

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

Bài học kinh nghiệm

• Điều kiện tam giác ABC: Hai cạnh ngắn nhất cộng lại phải lớn hơn cạnh dài nhất.
• Vì chi phí kéo dài các thanh như nhau, ta chỉ cần tập trung vào việc làm sao cho tổng hai cạnh ngắn nhất vượt quá cạnh dài nhất.
• Sử dụng long long là bắt buộc do giới hạn độ dài cạnh lên tới 10^9.

Lỗi thường gặp

• Tràn số integer: Nếu dùng int để tính tổng a + b + c khi a, b, c lên tới 10^9, tổng có thể vượt quá giới hạn của int (khoảng 2*10^9). Cần dùng long long.
• Sai công thức: Tính sai lượng cần tăng thêm. Ví dụ, nếu tổng hai cạnh nhỏ hơn cạnh dài nhất là 5, cần tăng tổng lên tối thiểu là cạnh dài nhất + 1. Lượng tăng là (cạnh dài nhất + 1) - tổng.
• Quên kiểm tra trường hợp đã hợp lệ: Nếu input đã thỏa mãn điều kiện tam giác, output phải là 0.