Tý muốn cắt một sợi dây có chiều dài NN (mét) thành 3 đ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 3 đoạn dây này là 3 cạnh của một tam gịác cân có cạnh đáy lớn hơn cạnh bên. Lưu ý: Tam giác cân là

2024-10-16 13:59:05

Tý muốn cắt một sợi dây có chiều dài NN (mét) thành 3 đ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 3 đoạn dây này là 3 cạnh của một tam gịác cân có cạnh đáy lớn hơn cạnh bên. Lưu ý: Tam giác cân là tam giác có hai cạnh bằng nhau, hai cạnh bằng nhau gọi là hai cạnh bên, cạnh còn lại gọi là cạnh đáy. Yêu cầu: Em hãy giúp Tý tính có bao nhiêu cách cắt đoạn dây này. Dữ liệu Một số nguyên dương NN (N<1016N<1016) Kết quả Ghi ra số MM là số cách cắt sợi dây theo yêu cầu. Input Copy19 Output Copy2 Giải thích: Có 2 cách cắt sợi dây thành 3 đoạn thỏa mãn đề là: (5m;5m;9m5m;5m;9m) và (6m;6m;7m6m;6m;7m). Lưu ý:: Các cách cắt sợi dây thành 3 đoạn (xx mét; xx mét; yy mét) và các hoán vị của bộ 3 số . (x;x;yx;x;y) chì được tính là 1 cách cắt. Chẳng hạn: Cách cắt thành các đoạn (5m;5m;9m5m;5m;9m) và các hoán vị của nó là (5m;9m;5m5m;9m;5m) hoặc (9m;5m;5m9m;5m;5m) chỉ được tính là 1 cách cắt. Giới hạn Có 20% test ứng với N≤102N≤102; Có 30% test ứng với 102<N≤106102<N≤106; Có 30% test ứng với 106<N≤109106<N≤109; Có 20% test ứng với 109<N≤1016109<N≤1016. Dựa theo code này ko dùng for đơn giản dễ hiểu: #include <iostream> using namespace std; int main() { long long N; cin >> N; int count = 0; for (long long x = 1; 2 * x < N; ++x) { long long y = N - 2 * x; if (y > x and 2 * x > y) { count++; } } cout << count << endl; return 0; }

Câu trả lời này dùng AI, hãy kiểm tra lại trước khi sử dụng

Để giải bài toán này, chúng ta cần tìm số cách cắt một sợi dây có chiều dài N thành 3 đoạn thì thỏa mãn điều kiện là lập thành một tam giác cân. Theo đặc điểm của tam giác cân, hai cạnh bên phải bằng nhau và cạnh đáy phải lớn hơn hai cạnh bên.

Giả sử độ dài của hai đoạn dây bằng nhau là x (x > 0), và độ dài đoạn dây còn lại (cạnh đáy) là y (y > 0). Ta có:

1. Tổng chiều dài của sợi dây là: 2x + y = N
2. Điều kiện của tam giác cân là: y > x và 2x > y

Từ điều kiện 1 (2x + y = N), ta có thể suy ra rằng y = N - 2x. Thay vào điều kiện 2, ta nhận được hai bất phương trình:

- N - 2x > x => N > 3x => x < N / 3
- 2x > N - 2x => 4x > N => x > N / 4

Vậy từ đó chúng ta có:

- x phải thoả mãn: N / 4 < x < N / 3

Tiếp theo, chúng ta sẽ xác định khoảng giá trị của x. Để tính số nguyên hợp lệ của x trong khoảng này:

1. Giá trị nhỏ nhất của x là: ceil(N / 4)
2. Giá trị lớn nhất của x là: floor(N / 3)

Số nguyên hợp lệ của x sẽ là: floor(N / 3) - ceil(N / 4) + 1, với điều kiện rằng giá trị lớn hơn hoặc bằng 1 (x > 0).

Dựa theo điều này, ta sẽ có số cách cắt sợi dây theo yêu cầu là:

```cpp
#include
using namespace std;

int main() {
long long N;
cin >> N;

long long minX = (N + 3) / 4; // ceil(N / 4)
long long maxX = N / 3; // floor(N / 3)

long long count = max(0LL, maxX - minX + 1);

cout << count << endl;
return 0;
}
```

Với đoạn code này, chúng ta không sử dụng vòng lặp nhưng vẫn tính được số lượng cách cắt sợi dây một cách chính xác và hiệu quả.

Khi N = 19, số cách cắt sẽ là 2, bởi vì chúng ta có thể cắt sợi dây thành các đoạn 5, 5, 9 và 6, 6, 7 thỏa mãn các điều kiện đã nêu.

Đăng phản hồi