HSG9 Quảng Ngãi 2026 - Bài 2

Xem dạng PDF

Gửi bài giải

Điểm: 11,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Output Only, Pascal, PyPy, Python, Scratch, TEXT

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

An muốn cắt sợi dây có chiều dài ~N~ mét thành ba đoạn dây có chiều dài mỗi đoạn là số nguyên dương (đơn vị mét) sao cho ba đoạn dây này là ba cạnh của một tam giác cân có cạnh đáy lớn hơn cạnh bên.

Tam giác cân là tam giác có hai cạnh bên bằng nhau, cạnh còn lại gọi là cạnh đáy.

Yêu cầu: Em hãy giúp An tính có bao nhiêu cách cắt sợi dây này.

Input

Gồm một số nguyên dương ~N~ ~(0 < N \le 10^{16})~.

Output

Số nguyên duy nhất là số cách cắt sợi dây theo yêu cầu. Nếu không thoả mãn, in ra 0.

Sample Input 1

25

Sample Output 1

2

Notes

Có ~2~ cách cắt sợi dây thành ~3~ đoạn thỏa mãn theo đề là ~(7, 7, 11)~ và ~(8, 8, 9)~.

Lưu ý: Các cách cắt sợi dây thành ba đoạn chỉ chọn dạng (~x~ mét, ~x~ mét, ~y~ mét).


Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 1
    thinhphamminh274  đã bình luận lúc 10, Tháng 11, 2026, 6:13

    PHÂN TÍCH BÀI TOÁN VÀ GIẢI THUẬT: CẮT SỢI DÂY

    1. Phân tích bài toán

    • Đề bài:
      • Cần cắt sợi dây có chiều dài $N$ thành 3 đoạn có độ dài là các số nguyên dương, sao cho chúng là 3 cạnh của một tam giác cân có cạnh đáy lớn hơn cạnh bên.
      • Gọi độ dài hai cạnh bên là $x$ và cạnh đáy là $y$ ($x, y \in \mathbb{N}^*$).
      • Tổng chiều dài sợi dây là: $2x + y = N$.
    • Điều kiện của tam giác cân:
      • Bất đẳng thức tam giác: Tổng hai cạnh bên lớn hơn cạnh đáy ($2x > y$).
      • Theo yêu cầu đề bài: Cạnh đáy lớn hơn cạnh bên ($y > x$).
    • Biến đổi toán học để tìm khoảng của $x$:
      • Thay $y = N - 2x$ vào điều kiện $2x > y$: $$2x > N - 2x \iff 4x > N \iff x > \frac{N}{4}$$
      • Thay $y = N - 2x$ vào điều kiện $y > x$: $$N - 2x > x \iff 3x < N \iff x < \frac{N}{3}$$
      • Kết hợp lại, ta có điều kiện cho số nguyên $x$: $$\frac{N}{4} < x < \frac{N}{3}$$
      • Số cách cắt sợi dây chính là số lượng các giá trị nguyên $x$ thỏa mãn khoảng trên.

    2. Giải thuật chi tiết trong code

    • Hàm tính toán d(n):
      • ll a = (n - 1) / 3;: Tính toán chặn trên tương đương với điều kiện $x < \frac{N}{3}$ trong tập số nguyên (tức là $\lfloor \frac{N-1}{3} \rfloor$).
      • ll b = n / 4;: Tính toán chặn dưới tương đương với điều kiện $x > \frac{N}{4}$ trong tập số nguyên (tức là $\lfloor \frac{N}{4} \rfloor$).
      • Hiệu a - b chính là số lượng các giá trị nguyên $x$ thỏa mãn.
      • if (a - b < 0) return 0; else return a - b;: Đảm bảo nếu không có giá trị nào thỏa mãn thì trả về kết quả là $0$.
    • Chương trình chính (main):
      • Đọc vào số nguyên dương $N$.
      • Gọi hàm d(n) và in kết quả ra màn hình.

    3. Đánh giá độ phức tạp

    • Độ phức tạp thời gian: $O(1)$ do chỉ thực hiện các phép toán số học cơ bản (chia và trừ số nguyên), chạy cực kỳ nhanh với giới hạn $N \le 10^{16}$.
    • Độ phức tạp không gian: $O(1)$.
      #include <bits/stdc++.h>
      #define ll long long
      #define Sonic() cin.tie(NULL)->syncwithstdio(0);
      #define el '\n'
      using namespace std;
      ll d(ll n){
          ll a=(n-1)/3;
          ll b=n/4;
          if(a-b<0)return 0;
          else return a-b;
      }
      
      
      

      int main(){ Sonic(); ll n;cin>>n; cout<<d(n); return 0; }