이 튜토리얼에서는 감독자에게 잡히지 않고 할당을 통과하는 방법을 찾는 알고리즘을 작성해야 합니다. 각 학생은 감독관에게 과제를 제출해야 합니다. 학생 A의 과제는 학생 B에게 있으므로 학생 B는 감독관이 눈치채지 못한 채 학생 A에게 과제를 반환/전달해야 합니다.
모든 학생들이 줄을 서고 있습니다. 잡히지 않고 학생 A에게 과제를 다시 전달할 수 있는 방법을 찾아야 합니다. 그들이 과제를 통과할 수 있는 다양한 요구 사항은 다음과 같습니다 -
-
학생 A(인덱스 i)는 인덱스 (i-1) 및 (i+1)에 있는 이웃에게 할당을 전달할 수 있습니다.
-
학생들은 과제를 주고 받거나 유지할 수 있습니다.
-
감독관은 색인 [il, rl]에서 모든 학생을 지켜보고 있습니다.
-
학생이 감독관의 감시 범위 안에 있으면 과제를 보내거나 받을 수 없습니다.
-
학생이 그 범위에 있는 동안 과제를 계속 가지고 있으면 감독관이 이를 잡지 못합니다.
네 개의 입력 p, q, r, s가 주어집니다. 여기서 p는 총 학생 수, q는 감독자가 il에서 rl까지 감시하는 동안의 총 단계 수, c는 학생 A의 위치, d 학생 B의 입장입니다.
각 단계(q)에는 3개의 입력이 있습니다. -
-
감독관이 주어진 범위에서 감시하는 총 시간입니다.
-
가장 왼쪽에 있는 범위에서 감독관이 지켜보고 있습니다.
-
가장 오른쪽에 있는 범위인 감독자가 보고 있습니다.
"Left", "Right", "Keep"이라는 3단어의 출력 시퀀스가 필요하며, 이는 학생이 과제(왼쪽/오른쪽)를 통과하거나 유지하는 경우 학생의 활동을 나타냅니다. 예를 들어,
단계
입력
8 3 2 7 1 4 6 2 1 8 3 5 6
출력
Right Keep Right Right Right Right
설명
이 지침을 따르면 과제는 잡히지 않고 색인 2의 학생에서 색인 7의 학생에게 도달합니다.
입력
5 1 1 3 1 2 5
출력
Keep Right Right
설명
이 지침을 따르면 과제는 잡히지 않고 색인 1의 학생에서 색인 3의 학생에게 도달합니다.
해결책을 찾기 위한 접근 방식
주어진 경우에 감독관이 현재 과제를 가지고 있는 학생이나 과제를 보낼 학생 중 어느 쪽이든 그 범위에서 감시하고 있다면, 그 학생은 그 과제를 그와 함께 유지할 것입니다. 그렇지 않으면 최종 목표 방향으로 인접한 학생에게 전달합니다.
예시
#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;
} 출력
Right Keep Right Right Right Right
결론
이 튜토리얼에서는 C++ 코드와 함께 감독자에게 잡히지 않고 할당을 전달하는 방법을 찾는 알고리즘을 작성하는 방법을 배웠습니다. 우리는 또한 자바, 파이썬 및 기타 언어로 이 코드를 작성할 수 있습니다. 위의 알고리즘은 경쟁 코딩 대회에서 중요한 알고리즘입니다. 이 질문에는 C++ 코드를 통해 해결한 실생활 문제가 포함되어 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.