SPOJ.COM – Thuật toán bài CTAIN - Containers
Đề bài:
Bạn được đưa cho n thùng chứa, trong đó 1 <= n <= 4. Lúc đầu, tất cả chúng đều đầy nước. Dung lượng tối đa của thùng thứ i là một số tự nhiên oi thỏa mãn 1 <= oi <= 49.
Có 3 loại hành động có thể thực hiện:
- 1. Đổ toàn bộ nước từ một thùng sang một thùng khác
- 2. Đổ đầy một thùng với phần nước từ một thùng khác.
- 3. Đổ hết nước từ một thùng xuống cống
Nhiệm vụ:
Viết một chương trình cho mỗi test case:
- Đọc vào số lượng thùng n, dung lượng tối đa của mỗi thùng và lượng nước được yêu cầu từ mỗi thùng.
- Kiểm tra xem nếu tồn tại một chuỗi hành động có thể dẫn tới lượng nước yêu cầu của mỗi thùng, thì tính xem số bước nhỏ nhất để làm được việc đó.
- In ra kết quả. Kết quả là số bước nhỏ nhất để đạt được yêu cầu hoặc in ra "NO" nếu không thể đạt được yêu cầu.
Đầu vào:
Một số nguyên ở dòng đầu tiên, là số lượng test case, theo sau là một dòng trắng. Cho biết là sẽ không quá 20 test case.
Mỗi test case, dòng đầu tiên sẽ là một số nguyên dương n, với n <= 4 là số lượng thùng. Dòng tiếp theo là n số nguyên dương, là dung lượng tối đa của mỗi thùng oi , thỏa mãn 1 <= oi <= 49. Dòng tiếp theo sẽ là n số nguyên dương wi, là lượng nước yêu cầu của mỗi thùng, thỏa mãn 0 <= wi <= oi. Tất cả số nguyên ở dòng thứ 2 và thứ 3 của mỗi test case được cách nhau bởi một dấu cách. Các test case được phân cách nhau bởi một dấu cách.
Đầu ra:
Mỗi test case in ra một số nguyên - là số bước nhỏ nhất để đạt được yêu cầu. Ngược lại thì in ra "NO".
Ví dụ:
Đầu vào:
2
3
3 5 5
0 0 4
2
20 25
10 16
Đầu ra:
6
NO
Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/CTAIN/
Phân tích:
-
Tại một thời điểm, ta sẽ có một trạng thái ứng với lượng nước trong mỗi thùng. Bài toán cho trước trạng thái ban đầu và yêu cầu tìm ra số bước nhỏ nhất để đạt được trạng thái đích. Do đó, tôi sẽ dụng thuật toán tìm kiếm theo chiều rộng BFS để giải quyết bài toán.
-
Vì có tối đa là 4 thùng nên tôi sẽ sử dụng mảng 4 chiều, trong đó mỗi chiều sẽ có tối đa 50 phần tử từ 0 đến 49 đại diện cho lượng nước từ 0 đến 49, để đánh dấu số bước nhỏ nhất có thể đạt được trạng thái đó. Ban đầu các giá trị của mảng sẽ được đánh dấu là MAXINT. Sau quá trình duyệt nếu như giá trị của mảng tại trạng thái cần tìm vẫn là MAXINT thì có nghĩa là sẽ không có cách để đạt được trạng thái đó và in ra là "NO". Ngược lại tôi sẽ in ra giá trị của mảng tại trạng thái đó.
-
Tại một trạng thái thì các trạng thái kề với nó sẽ có được bằng cách thực hiện 3 hành động cho trong đề bài.
Lời giải:
(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)
Code C/C++:
| #include<iostream> | |
| using namespace std; | |
| const int MAX = 5; | |
| const int MAX_QUEUE = 1000000; | |
| const int MAX_INT = 1 << 30; | |
| const int MAX_STATE = 50; | |
| int N; //số lượng thùng | |
| int Capacity[MAX]; //dung lượng mối thùng | |
| int Water[MAX]; //lượng nước hiện tại mỗi thùng | |
| int Need[MAX]; //lượng nước cần | |
| int Answer; //kết quả | |
| bool Flag, Finish; | |
| // Đánh dấu trạng thái | |
| int State[MAX_STATE][MAX_STATE][MAX_STATE][MAX_STATE]; | |
| typedef struct Point | |
| { | |
| int *water; | |
| int step; | |
| Point():step(0),water(0){} | |
| Point(int st, int *wa):step(st),water(wa){} | |
| }Point; | |
| Point queue[MAX_QUEUE]; | |
| int fr, re, leng; | |
| /** | |
| * copy mảng: từ mảng src sang mảng dst*/ | |
| void CpyArray(int *dst, int *src) | |
| { | |
| for(int i = 0; i < N; i++) | |
| dst[i] = src[i]; | |
| } | |
| // implement hàng đợi vòng | |
| void Enqueue(Point p) | |
| { | |
| queue[re] = p; | |
| re = (re + 1) % MAX_QUEUE; | |
| leng++; | |
| } | |
| Point Dequeue() | |
| { | |
| Point p = queue[fr]; | |
| fr = (fr + 1) % MAX_QUEUE; | |
| leng--; | |
| return p; | |
| } | |
| /** | |
| * Lấy giá trị của mảng 4 chiều tại một trạng thái | |
| */ | |
| int GetValueState(int *tmp) | |
| { | |
| int a,b,c,d; | |
| a = b = c = d = 0; | |
| if(N == 1) a = tmp[0]; | |
| else if(N == 2) {a = tmp[0]; b = tmp[1];} | |
| else if(N == 3) {a = tmp[0]; b = tmp[1]; c = tmp[2];} | |
| else if(N == 4) {a = tmp[0]; b = tmp[1]; c = tmp[2]; d = tmp[3];} | |
| return State[a][b][c][d]; | |
| } | |
| /** | |
| * Xét giá trị value cho mảng 4 chiều tại trạng thái cho trước | |
| */ | |
| void SetValueState(int *tmp, int value) | |
| { | |
| int a,b,c,d; | |
| a = b = c = d = 0; | |
| if(N == 1) a = tmp[0]; | |
| else if(N == 2) {a = tmp[0]; b = tmp[1];} | |
| else if(N == 3) {a = tmp[0]; b = tmp[1]; c = tmp[2];} | |
| else if(N == 4) {a = tmp[0]; b = tmp[1]; c = tmp[2]; d = tmp[3];} | |
| State[a][b][c][d] = value; | |
| } | |
| // Implement BFS | |
| void BFS(Point st) | |
| { | |
| fr = re = leng = 0; | |
| SetValueState(st.water,0); | |
| Enqueue(st); | |
| while(leng > 0) | |
| { | |
| Point p = Dequeue(); | |
| // Duyệt các thùng và thực hiện 3 hành động | |
| for(int i = 0; i < N; i++) | |
| { | |
| // Hành động 1: đổ hết nước đi | |
| int old_water = p.water[i]; | |
| p.water[i] = 0; | |
| int *tmp1 = new int[N]; | |
| CpyArray(tmp1, p.water); | |
| // Kiểm tra xem trạng thái này đã có chưa | |
| // nếu giá trị tại đó là MAX_INT nghĩa là chưa có | |
| if(GetValueState(tmp1) == MAX_INT) | |
| { | |
| SetValueState(tmp1, p.step + 1); | |
| Enqueue(Point(p.step + 1, tmp1)); | |
| } | |
| p.water[i] = old_water; | |
| // Hành động 2: Đổ đầy bằng 1 thùng khác | |
| // Hành động này chỉ thực hiện khi thùng chưa đầy | |
| if(p.water[i] < Capacity[i]) | |
| { | |
| // thử đổ đầy bằng các thùng còn lại | |
| for(int j = 0; j < N; j++) | |
| { | |
| if(j == i) continue; | |
| if(Capacity[i] - p.water[i] <= p.water[j]) | |
| { | |
| int old_water1 = p.water[i], old_water2 = p.water[j]; | |
| p.water[j] = p.water[j] - (Capacity[i] - p.water[i]); | |
| p.water[i] = Capacity[i]; | |
| int *tmp2 = new int[N]; | |
| CpyArray(tmp2,p.water); | |
| // Kiểm tra xem trạng thái này đã có chưa | |
| // nếu giá trị tại đó là MAX_INT nghĩa là chưa có | |
| if(GetValueState(tmp2) == MAX_INT) | |
| { | |
| SetValueState(tmp2,p.step+1); | |
| Enqueue(Point(p.step+1,tmp2)); | |
| } | |
| p.water[i] = old_water1; | |
| p.water[j] = old_water2; | |
| } | |
| } | |
| } | |
| //Hành động 3: Đổ hết nước sang thùng khác nếu đủ chỗ | |
| //Xét thử các thùng | |
| for(int j = 0; j < N; j++) | |
| { | |
| if(j == i) continue; | |
| if(Capacity[j] - p.water[j] >= p.water[i]) | |
| { | |
| int old_water1 = p.water[i], old_water2 = p.water[j]; | |
| p.water[j] = p.water[j] + p.water[i]; | |
| p.water[i] = 0; | |
| int *tmp3 = new int[N]; | |
| CpyArray(tmp3,p.water); | |
| // Kiểm tra xem trạng thái này đã có chưa | |
| // nếu giá trị tại đó là MAX_INT nghĩa là chưa có | |
| if(GetValueState(tmp3) == MAX_INT) | |
| { | |
| SetValueState(tmp3,p.step+1); | |
| Enqueue(Point(p.step+1,tmp3)); | |
| } | |
| p.water[i] = old_water1; | |
| p.water[j] = old_water2; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| int main() | |
| { | |
| ios::sync_with_stdio(false); | |
| //freopen("input.txt","r",stdin); | |
| int T; | |
| cin >> T; | |
| for(int tc = 0; tc < T; tc++) | |
| { | |
| cin >> N; | |
| for(int i = 0; i < N; i++) | |
| { | |
| cin >> Capacity[i]; | |
| Water[i] = Capacity[i]; | |
| } | |
| for(int i = 0; i < N; i++) | |
| cin >> Need[i]; | |
| Answer = MAX_INT; | |
| for(int i = 0; i < MAX_STATE; i++) | |
| for(int j = 0; j < MAX_STATE; j++) | |
| for(int k = 0; k < MAX_STATE; k++) | |
| for(int m = 0; m < MAX_STATE; m++) | |
| State[i][j][k][m] = MAX_INT; | |
| BFS(Point(0, Water)); | |
| Answer = GetValueState(Need); | |
| if(Answer == MAX_INT) cout << "NO" << endl; | |
| else cout << Answer << endl; | |
| } | |
| return 0; | |
| } |
Code by Phạm Văn Lâm.