Editorial for ptit028: Làm tròn số

Hiểu bài toán

Cho một số thực decimal x (|-10000| <= x <= 10000). Tìm hai số nguyên sao cho:

1. Số nguyên lớn nhất nhưng nhỏ hơn hoặc bằng x (sàn).
2. Số nguyên nhỏ nhất nhưng lớn hơn x (trần).

Đề bài yêu cầu in hai số này theo thứ tự tăng dần, cách nhau bởi một dấu cách.

Ví dụ:

• Với x = -5.23: Số lớn nhất ≤ -5.23 là -6 (vì -5 > -5.23), số nhỏ nhất > -5.23 là -5. Kết quả: -6 -5.
• Với x = 98.222: Số lớn nhất ≤ 98.222 là 98, số nhỏ nhất > 98.222 là 99. Kết quả: 98 99.

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

Cách Phép chia lấy phần nguyên

#include<stdio.h>

int main(){
    double x;
    scanf("%lf",&x);
    int p = x;
    if(p < 0) printf("%d %d",p - 1,p);
    else printf("%d %d",p,p + 1);
    return 0;
}

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

Phương pháp này dựa vào hành vi của phép chia lấy phần nguyên trong C:

1. Khai báo biến p kiểu int và gán p = x. Khi ép kiểu từ số thực sang số nguyên, C sẽ cắt bỏ phần thập phân (trừ số âm).
2. Xử lý số âm (x < 0):
   • Nếu x = -5.23, p sẽ là -5 (cắt bỏ .23).
   • Vì -5 > -5.23, ta cần số nhỏ hơn. Số nguyên lớn nhất ≤ x là p - 1 = -6.
   • Số nguyên nhỏ nhất > x là p = -5.
   • In ra p - 1 và p.
3. Xử lý số dương hoặc 0 (x >= 0):
   • Nếu x = 98.222, p sẽ là 98.
   • Số nguyên lớn nhất ≤ x là p = 98.
   • Số nguyên nhỏ nhất > x là p + 1 = 99.
   • In ra p và p + 1.

Cách Sử dụng hàm floor và ceil

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

int main() {
    float n;
    scanf("%f",&n);
    if(n-(int)n==0) printf("%d %d",(int)floor(n),(int)ceil(n)+1);
    else printf("%d %d",(int)floor(n),(int)ceil(n));
    return 0;
}

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

Phương pháp này sử dụng các hàm toán học chuẩn để xác định ranh giới:

1. floor(n): Trả về số nguyên lớn nhất không lớn hơn n. Đây chính là số sàn (lower bound).
2. ceil(n): Trả về số nguyên nhỏ nhất không nhỏ hơn n.
3. Logic xử lý:
   • Nếu n là số nguyên (kiểm tra n - (int)n == 0):
     • Số sàn là floor(n) (chính là n).
     • Số trần phải lớn hơn n, nên là ceil(n) + 1.
   • Nếu n là số thực không nguyên:
     • Số sàn là floor(n).
     • Số trần là ceil(n).
4. Hàm floor và ceil xử lý đúng cả số âm và dương (ví dụ floor(-5.23) = -6, ceil(-5.23) = -5).

Cách Phương pháp xử lý số âm trực tiếp

#include <stdio.h>

int main() {
    float n;
    scanf("%f", &n);
    int x = n;
    if (x < 0) printf("%d %d", x - 1, x);
    else printf("%d %d", x, x + 1);
    return 0;
}

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

Đây là biến thể của cách 1, sử dụng biến float để nhập.

1. Ép kiểu float sang int:
   • int x = n (n là float).
   • Hành vi tương tự: bỏ phần thập phân.
2. Logic:
   • Nếu n âm (kiểm tra qua x < 0):
     • Do ép kiểu làm tròn về 0 (ví dụ -5.23 thành -5), ta cần lùi lại 1 đơn vị cho số sàn: x - 1.
     • Số trần giữ nguyên: x.
   • Nếu n dương hoặc 0:
     • Ép kiểu cho ra số sàn: x.
     • Số trần là x + 1.
   • Lưu ý: Trong C, ép kiểu float sang int cho số âm cũng cắt bỏ phần thập phân (truncation toward zero), không phải floor. Do đó -5.23 thành -5. Logic x < 0 xử lý trường hợp này.

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

Bài học kinh nghiệm

• Vấn đề cốt lõi là tìm số sàn (floor) và số trần (ceiling) của số x, nhưng với định nghĩa trần là số nhỏ nhất lớn hơn x (strictly greater). Do đó, nếu x là số nguyên, trần sẽ là x + 1.
• Phép chia lấy phần nguyên (hoặc ép kiểu sang int) trong C/C++ đối với số âm sẽ 'truncates toward zero' (cắt bỏ phần thập phân), không phải làm tròn xuống (floor). Ví dụ: (int)-5.23 = -5. Điều này dẫn đến kết quả sai nếu không xử lý riêng.
• Các hàm toán học floor và ceil trong thư viện <math.h> (C) hoặc <cmath> (C++) xử lý chính xác các trường hợp số âm và số nguyên, giúp code ngắn gọn và dễ hiểu hơn.

Lỗi thường gặp

• Lỗi sai với số âm: Nếu chỉ đơn thuần lấy (int)x cho tất cả x, với x = -5.23, ta được -5. Nếu coi -5 là số sàn thì sai (vì -5 > -5.23). Cần phải trừ 1 cho số âm.
• Trường hợp x là số nguyên: Nếu x = 5.0, số sàn là 5. Nếu dùng hàm ceil(5.0) thì kết quả là 5, nhưng yêu cầu số trần phải là số lớn hơn 5, tức là 6. Cần kiểm tra điều kiện x là số nguyên để tăng giá trị trần lên 1.