Đề bài:qvluom đã viết: Bài 1.
- Có một số cây có chiều dài cho trước. Cần bắt qua những con kênh có chiều rộng cho trước (không quá 100 cây và 100 con kênh).
- Điều kiện: + Nếu cây dài quá thì bạn có thể chặt nó ra thành vài khúc xài cũng được
+ Chỉ được dùng 1 khúc cây để bắt qua 1 con kênh
+ Khúc cây được dùng để bắt qua con kênh phải có chiều dài lớn hơn chiều rộng của con kênh ít nhất là 1m.
- Bài toán đặt ra là bắt như thế nào để số cây còn lại phải là nhiều nhất (chú ý chỉ tính những cây mà bạn chưa chặt ra).
- Test thì bạn cứ tuỳ ý cho thế nào cũng được.
Ý tưởng:- Do "Khúc cây được dùng để bắt qua con kênh phải có chiều dài lớn hơn chiều rộng của con kênh ít nhất là 1m". Ta tăng chiều rộng của mỗi con kênh lên 1m để dễ làm việc.
- Điều kiện cơ bản để bài toán có lời giải là TỔNG ĐỘ DÀI CỦA CÁC CÂY phải lớn hơn hoặc bằng TỔNG CHIỀU RỘNG CỦA CÁC KÊNH; và CHIỀU RỘNG CỦA KÊNH RỘNG NHẤT không lớn hơn CHIỀU DÀI CỦA CÂY DÀI NHẤT
- Sắp xếp các cây và các con kênh theo thứ tự giảm dần của chiều dài (chiều rộng)
- Thử chọn 1 cây để bắc qua các con kênh (chọn cây đầu tiên, cũng tức là cây dài nhất)
- Nếu kiểm tra
(*) thỏa mãn thì kết thúc. Ngược lại ta sẽ tăng dần lên 2 cây, rồi 3 cây,...
Chú ý: ta chỉ chọn những cây có độ dài lớn nhất, vì yêu cầu đặt ra chỉ là số cây còn lại là nhiều nhất, chứ không phải tổng độ dài của các cây còn lại là lớn nhất!- Nếu tăng lên đến số lượng cây tối đa, mà vẫn không thỏa mãn thì kết luận không có đáp án thỏa mãn yêu cầu.
(*) kiểm tra- Ta cần kiểm tra TỔNG ĐỘ DÀI CỦA CÁC CÂY ĐƯỢC CHỌN phải lớn hơn hoặc bằng TỔNG CHIỀU RỘNG CỦA CÁC KÊNH.
- Bắc cầu lần lượt cho các con kênh từ lớn đến bé (theo thứ tự đã sắp xếp)
- Với mỗi con kênh, ta sẽ chọn cây có độ dài nhỏ nhất để thử, nếu không đủ dộ dài thì chọn cây dài hơn. Nếu không có cây nào thỏa thì không thể bắc cầu VỚI SỐ CÂY ĐƯỢC CHỌN TRÊN.
- Với mỗi cây sau khi đem bắc cầu thì độ dài còn lại sẽ là độ dài ban đầu trừ đi độ rộng con kênh, sau đó ta sắp xếp lại độ dài của các cây cho theo thứ tự. Nếu độ dài của cây ngắn nhất bằng 0 thì loại hẳn cây đó ra.
- Nếu bắc cầu được hết cho các con kênh, coi như bài toán đã hoàn thành. Xuất ra SỐ CÂY ĐÃ SỬ DỤNG, SỐ CÂY CÒN LẠI.
Code C++:Code:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define fi "C:\\bai1.inp"
#define fo "C:\\bai1.out"
int SoCay, SoKenh, error;
int Cay[100], Kenh[100];
void DocFile()
{
FILE *f;
int i, s;
f = fopen(fi,"r");
if (f!=NULL)
{
if (fscanf(f,"%d",&s))
SoCay=s;
else {error=1; exit;}
fscanf(f,"\n");
for (i=0; i<SoCay; i++)
{
if (fscanf(f,"%d",&s))
Cay[i] = s;
else {error=1; exit;}
}
if (fscanf(f,"%d\n",&s))
SoKenh=s;
else {error=1; exit;}
fscanf(f,"\n");
for (i=0; i<SoKenh; i++)
{
if (fscanf(f,"%d",&s))
Kenh[i] = s;
else {error=1; exit;}
}
}
else error=1;
fclose(f);
}
long Tong(int A[], int n)
{
long temp = 0;
for (int i=0; i<n; i++)
temp += A[i];
return temp;
}
int GTLonNhat(int A[], int n)
{
int m = 0;
for (int i=0; i<n; i++)
if (m < A[i])
m = A[i];
return m;
}
void BubbleSort(int A[], int n, int index) // index = 1 : sap xep tang; index = 0 : sap xep giam;
{
for (int i=n-1; i>0; i--)
for (int j=0; j<i; j++)
if ((A[j] > A[j+1]) == index)
{
int temp = A[j];
A[j] = A[j+1];
A[j+1] = temp;
}
}
void ChuanHoa(int C[], int &sC, int index)
{
while (index<sC-1 && C[index]<C[index+1])
{
int temp = C[index];
C[index] = C[index+1];
C[index+1] = temp;
index++;
}
if (C[sC-1] == 0) sC --;
}
int Try(int C[], int sC, int K[], int sK)
{
for (int i=0; i<sK; i++)
{
int j = sC - 1;
while (j>=0 && C[j]<K[i]) j--;
if (j>=0)
{
C[j] = C[j] - K[i];
ChuanHoa(C, sC, j);
}
else
return 0;
}
return 1;
}
void XuLy()
{
int i, j, temp[100], sl, flag=0;
for (i=0; i<SoKenh; i++)
Kenh[i] += 1;
long TongChieuRongKenh=Tong(Kenh, SoKenh);
if ((TongChieuRongKenh > Tong(Cay, SoCay)) || (GTLonNhat(Kenh, SoKenh) > GTLonNhat(Cay, SoCay)))
{
FILE *f;
f = fopen(fo,"w");
fprintf(f,"Khong co ket qua nao thoa man du lieu nay!");
fclose(f);
}
else
{
BubbleSort(Kenh, SoKenh, 0);
BubbleSort(Cay, SoCay, 0);
i=0;
while (i<SoCay && !flag)
{
sl = i+1;
for (j=0; j<sl; j++)
{
temp[j] = Cay[j];
}
if (TongChieuRongKenh <= Tong(temp, sl))
{
if (Try(temp, sl, Kenh, SoKenh))
{
FILE *f;
f = fopen(fo,"w");
fprintf(f,"So cay da dung la: %d \n", sl);
fprintf(f,"So cay con lai la: %d", SoCay-sl);
fclose(f);
flag = 1;
}
}
i++;
}
if (!flag)
{
FILE *f;
f = fopen(fo,"w");
fprintf(f,"Khong co ket qua nao thoa man du lieu nay!");
fclose(f);
}
}
}
void main()
{
DocFile();
XuLy();
}
- Dòng 1: số cây
- Dòng 2: Danh sách các chiều dài của các cây (mỗi số cách nhau ít nhất 1 khoảng trắng)
- Dòng 3: số kênh
- Dòng 4: Danh sách các chiều rộng của các kênh (mỗi số cách nhau ít nhất 1 khoảng trắng)
Ví dụ:Code:
6
3 2 5 4 7 8
4
4 3 6 2
Bài này đã quá hạn giải lâu lắm rồi, nhưng em rất mong nhận xét của thầy!
(Dương Tấn Thành)
