Trong hướng dẫn này, chúng ta phải viết một thuật toán để tìm cách chuyển bài tập mà không bị giám thị phát hiện. Mỗi sinh viên phải nộp bài tập cho giám thị. Bài tập của Sinh viên A đang ở Sinh viên B, vì vậy Sinh viên B phải trả/truyền bài tập cho Sinh viên A mà không bị giám thị nhận ra.
Tất cả sinh viên ngồi hàng hàng. Chúng ta cần tìm cách chuyển bài tập về cho Sinh viên A mà không bị phát hiện. Các yêu cầu khác nhau để họ có thể chuyển bài tập như sau:
Sinh viên A (tại chỉ số i) có thể chuyển bài tập cho hàng xóm tại chỉ số (i-1) và (i+1)
Sinh viên có thể cho, nhận hoặc giữ bài tập ở lại.
Giám thị đang quan sát tất cả sinh viên từ chỉ số [il, rl].
Khi sinh viên ở trong phạm vi quan sát của giám thị, họ không thể gửi hoặc nhận bài tập.
Nếu sinh viên giữ bài tập khi ở trong phạm vi đó, giám thị sẽ không bắt được.
Chúng ta được cho bốn đầu vào p, q, r, s trong đó p là tổng số sinh viên, q là tổng số bước mà giám thị quan sát từ il đến rl, c là vị trí của Sinh viên A, và d là vị trí của Sinh viên B.
Mỗi bước (q) có ba đầu vào:
Tổng thời gian giám thị sẽ quan sát trong phạm vi cho trước.
Phạm vi bao gồm bên trái nhất mà giám thị quan sát.
Phạm vi bao gồm bên phải nhất mà giám thị quan sát.
Một chuỗi đầu ra gồm 3 từ được yêu cầu: "Left", "Right" và "Keep", biểu thị hoạt động của sinh viên nếu họ chuyển bài tập (trái/phải) hoặc giữ lại. Ví dụ:
Các bước
Đầu vào
8 3 2 7 1 4 6 2 1 8 3 5 6
Đầu ra
Right Keep Right Right Right Right
Giải thích
Bằng cách làm theo các hướng dẫn này, bài tập sẽ đến từ sinh viên tại chỉ số 2 đến sinh viên tại chỉ số 7 mà không bị bắt.
Đầu vào
5 1 1 3 1 2 5
Đầu ra
Keep Right Right
Giải thích
Bằng cách làm theo các hướng dẫn này, bài tập sẽ đến từ sinh viên tại chỉ số 1 đến sinh viên tại chỉ số 3 mà không bị bắt.
Cách tiếp cận để tìm giải pháp
At a given instance, if the invigilator is keeping a watch in that range, either the student currently having the assignment or the student to whom the assignment is to be sent, then that student will retain that assignment with him. Else he passes it to his adjacent student in the direction of the final target.
Ví dụ
#include <bits/stdc++.h> using namespace std; void solve(int p, int q, int r, int s, long t[], int l[], int ar[]){ int dir; string val; if (r < s) { dir = 1; val = "Right"; } else { dir = -1; val = "Left"; } string answer = ""; int i = 0, current = r; long tim = 1; while (1) { if (i < q && tim == t[i]) { if ((current >= l[i] && current <= ar[i]) || (current + dir >= l[i] && current + dir <= ar[i])) { answer += "Keep\n"; tim++; i++; continue; } i++; } current += dir; answer += val+"\n"; tim++; if (current == s) break; } cout << answer << endl; } int main(){ int p = 8, q = 3, r = 2, s = 7; long t[q + 2] = { 1,2,3 }; int l[q + 2] = { 4,1,5 }; int ar[q + 2] = { 6,8,6 }; solve(p, q, r, s, t, l, ar); return 0; }Đầu ra
Right Keep Right Right Right Right
Kết luận
Trong hướng dẫn này, chúng ta đã học cách viết thuật toán tìm cách chuyển bài tập mà không bị giám thị bắt cùng với code C++. Chúng ta cũng có thể viết code này bằng Java, Python và các ngôn ngữ khác. Thuật toán trên là một thuật toán quan trọng cho các cuộc thi lập trình cạnh tranh. Câu hỏi này bao gồm một vấn đề thực tế, mà chúng ta đã giải quyết thông qua code C++. Hy vọng bạn thấy hướng dẫn này hữu ích.