C++で割り当てを渡す

このチュートリアルでは、インビジレーターに捕らわれることなく割り当てを渡す方法を見つけるためのアルゴリズムを作成する必要があります。各生徒は、課題を試験監督官に提出する必要があります。生徒Aの課題は生徒Bと一緒であるため、生徒Bは、指導者に気付かれることなく、課題を生徒Aに返却/渡す必要があります。

生徒全員が列に並んでいます。捕まることなく課題を生徒Aに戻す方法を見つける必要があります。割り当てを渡すことができるさまざまな要件は次のとおりです-

• 生徒A（インデックスi）は、インデックス（i-1）および（i + 1）にいる隣人に課題を渡すことができます

• 生徒は課題を与えたり、受け取ったり、保持したりできます。

• インビジレーターは、インデックス[il、rl]からすべての生徒を監視しています。

• 生徒が監視員の時計の範囲内にいる場合、課題を送受信することはできません。

• 生徒がその範囲内で課題を保持している場合、試験監督官は生徒を捕まえません。

4つの入力p、q、r、sが与えられます。ここで、pは生徒の総数、qは監視員がilからrlまで監視している合計ステップ数、cは生徒Aの位置、dです。は学生Bの役職です。

各ステップ（q）には3つの入力があります-

• インビジレーターが指定された範囲を監視し続ける合計時間。

• 左端の包括的範囲では、インビジレーターが監視しています。

• 右端の包括的範囲であるインビジレーターが見ています。

「左」、「右」、「維持」の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++コードとともにinvigilatorに捕らわれることなく割り当てを渡す方法を見つけるためのアルゴリズムを作成する方法を学びました。このコードは、Java、Python、およびその他の言語で作成することもできます。上記のアルゴリズムは、競技コーディングの競争にとって重要なアルゴリズムです。この質問には、C++コードで解決した実際の問題が含まれています。このチュートリアルがお役に立てば幸いです。