Bài toán – Những chiếc gậy
George có những chiếc gậy với chiều dài như nhau và chặt chúng thành những đoạn có chiều dài ngẫu nhiên cho đến khi tất cả các phần trở thành đều có chiều dài tối đa là 50 đơn vị. Bây giờ anh ta muốn ghép các đoạn lại như ban đầu nhưng lại quên mất nó như thế nào và chiều dài ban đầu của chúng là bao nhiêu. Hãy giúp George thiết kế chương trình để ước tính nhỏ nhất có thể của chiều dài những cái gậy này. Tất cả chiều dài được biểu diễn bằng đơn vị là những số nguyên lớn hơn 0.
Input. Dữ liệu vào trong file Input.txt chứa các khối mỗi khối 2 dòng. Dòng đầu tiên chứa số phần của chiếc gậy sau khi cắt. Dòng thứ 2 là chiều dài của các phần này cách nhau bởi một dấu cách. Dòng cuối cùng kết thúc file Input là số 0.
Output. Kết quả ra trong file Output.txt chứa chiều dài nhỏ nhất có thể của những cái gậy, mỗi chiếc trong mỗi khối trên một dòng.
Thuật toán
Để giải bài toán này, ta có thể sử dụng thuật toán tìm kiếm nhị phân. Đầu tiên, ta sẽ tính tổng chiều dài của tất cả các phần gậy và lưu vào biến sum. Sau đó, ta sẽ thực hiện tìm kiếm nhị phân để tìm chiều dài nhỏ nhất của một chiếc gậy. Ta sẽ bắt đầu với khoảng giá trị từ 1 đến sum. Ở mỗi bước lặp, ta sẽ tính toán số lượng chiếc gậy cần thiết để ghép lại với chiều dài cho trước. Nếu số lượng chiếc gậy này nhỏ hơn hoặc bằng số phần gậy được cắt ban đầu, ta sẽ thực hiện tìm kiếm nhị phân với khoảng giá trị từ giá trị hiện tại đến giá trị trung bình của khoảng giá trị hiện tại. Nếu số lượng chiếc gậy này lớn hơn số phần gậy được cắt ban đầu, ta sẽ tăng khoảng giá trị lên từ giá trị trung bình của khoảng giá trị hiện tại đến giá trị lớn nhất của khoảng giá trị hiện tại. Quá trình tìm kiếm này sẽ tiếp tục cho đến khi giá trị tìm được hội tụ với độ chính xác mong muốn.
Sau khi tìm được chiều dài nhỏ nhất của một chiếc gậy, ta sẽ in kết quả ra file Output.txt, mỗi chiếc gậy trên một dòng.
Cài đặt bài toán với Python
def count_sticks_length(sticks, length):
count = 0
sum_length = 0
for stick in sticks:
if sum_length + stick > length:
count += 1
sum_length = stick
else:
sum_length += stick
if sum_length > 0:
count += 1
return count
with open('Input.txt', 'r') as f_in, open('Output.txt', 'w') as f_out:
while True:
n = int(f_in.readline().strip())
if n == 0:
break
sticks = list(map(int, f_in.readline().strip().split()))
sum_length = sum(sticks)
left = 1
right = sum_length
while left < right:
mid = (left + right) // 2
count = count_sticks_length(sticks, mid)
if count > n:
left = mid + 1
else:
right = mid
f_out.write(str(left) + '\n')
Cài đặt bài toán với C++
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int count_sticks_length(const vector<int>& sticks, int length) {
int count = 0;
int sum_length = 0;
for (int i = 0; i < sticks.size(); i++) {
if (sum_length + sticks[i] > length) {
count++;
sum_length = sticks[i];
} else {
sum_length += sticks[i];
}
}
if (sum_length > 0) {
count++;
}
return count;
}
int main() {
ifstream fin("Input.txt");
ofstream fout("Output.txt");
while (true) {
int n;
fin >> n;
if (n == 0) {
break;
}
vector<int> sticks(n);
int sum_length = 0;
for (int i = 0; i < n; i++) {
fin >> sticks[i];
sum_length += sticks[i];
}
int left = 1;
int right = sum_length;
while (left < right) {
int mid = (left + right) / 2;
int count = count_sticks_length(sticks, mid);
if (count > n) {
left = mid + 1;
} else {
right = mid;
}
}
fout << left << endl;
}
fin.close();
fout.close();
return 0;
}