ในบทช่วยสอนนี้ เราต้องเขียนอัลกอริทึมเพื่อหาวิธีส่งงานการบ้านโดยไม่ให้ครูคุมสังเกตเห็น นักเรียนแต่ละคนต้องส่งงานให้ครูคุม งานของนักเรียน 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 ข้อมูลนำเข้า:
- เวลาทั้งหมดที่ครูคุมจะมองดูในช่วงที่กำหนด
- ช่วงซ้ายสุด (inclusive) ที่ครูคุมมอง
- ช่วงขวาสุด (inclusive) ที่ครูคุมมอง
ต้องการลำดับเอาต์พุต 3 คำ: "Left", "Right", และ "Keep" แสดงการกระทำของนักเรียนว่ากำลังส่งงาน (ซ้าย/ขวา) หรือเก็บไว้ เช่น
ขั้นตอน
ข้อมูลนำเข้า
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++ สามารถเขียนใน Java, Python และภาษาอื่นๆ ได้ อัลกอริทึมข้างต้นเป็นอัลกอริทึมสำคัญสำหรับการแข่งขันเขียนโค้ดแบบแข่งขัน คำถามนี้รวมปัญหาจริง ซึ่งเราแก้ด้วยโค้ด C++ หวังว่าบทช่วยสอนนี้จะมีประโยชน์
