Trong hướng dẫn này, chúng ta phải viết một thuật toán để tìm cách vượt qua một bài tập mà không bị người giám sát bắt quả tang. Mỗi học sinh phải nộp bài tập của mình cho người giám sát. Bài tập của Học sinh A cùng với Học sinh B, vì vậy Học sinh B phải trả lại / chuyển bài tập cho Học sinh A mà người giám sát không nhận thấy họ.
Tất cả học sinh đang ngồi xếp hàng. Chúng ta cần tìm cách chuyển bài tập lại cho Sinh viên A mà không bị bắt. Các yêu cầu khác nhau mà họ có thể vượt qua bài tập như sau -
-
Sinh viên A (Ở chỉ mục i) có thể chuyển bài tập cho người hàng xóm của mình đang ở chỉ mục (i-1) và (i + 1)
-
Học sinh có thể đưa, nhận hoặc giữ lại bài tập cùng với họ.
-
Người giám sát đang theo dõi tất cả học sinh từ chỉ mục [il, rl].
-
Khi học sinh ở trong tầm theo dõi của người giám sát, học sinh không thể gửi hoặc nhận bài tập.
-
Nếu học sinh vẫn giữ bài tập với họ trong phạm vi đó, người giám sát sẽ không bắt được họ.
Chúng tôi được đưa ra bốn đầu vào p, q, r, s trong đó p là tổng số học sinh, q là tổng số bước trong đó người giám sát đang theo dõi từ il đến rl, c là vị trí của học sinh 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 người giám sát sẽ theo dõi trong phạm vi nhất định.
-
Trong phạm vi bao gồm ngoài cùng bên trái, người giám sát đang theo dõi.
-
Phạm vi bao gồm ngoài cùng bên phải, người bảo vệ, đang theo dõi.
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 học sinh nếu họ đang vượt qua bài tập (trái / phải) hoặc giữ nó. 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ẽ được chuyển từ học sinh ở chỉ số 2 đến học sinh ở 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ẽ được chuyển từ học sinh ở chỉ số 1 đến học sinh ở chỉ số 3 mà không bị bắt.
Phương pháp tiếp cận để tìm giải pháp
Tại một trường hợp cụ thể, nếu người giám sát đang theo dõi trong phạm vi đó, học sinh hiện đang có bài tập hoặc học sinh được gửi bài tập cho, thì học sinh đó sẽ giữ bài tập đó bên mình. Nếu không, anh ấy sẽ chuyển nó cho học sinh kế cận của mình theo hướng của mục tiêu cuối cùng.
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 một thuật toán để tìm cách vượt qua một nhiệm vụ mà không bị bắt bởi người giám sát cùng với mã c ++. Chúng tôi cũng có thể viết mã 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 viết mã cạnh tranh. Câu hỏi này bao gồm một vấn đề trong cuộc sống thực, mà chúng tôi đã giải quyết thông qua mã C ++. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.