ผลต่างระหว่างรุ่นของ "Baltic2014"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 2: แถว 2:
 
== Day1: Cop and Robber  ==
 
== Day1: Cop and Robber  ==
  
ณ เมืองไบท์มอร์ ระดับของอาชญากรรมได้เพิ่มขึ้นมากจนเป็นจุดสูงสุดในประวัติศาสตร์ ท่ามกลางการก่ออาชญากรรมประเภทเบานั้นการขโมยของได้เกิดขึ้นเป็นประจำทุกวี่วัน
+
ณ เมืองไบท์มอร์ ระดับของอาชญากรรมได้เพิ่มขึ้นมากจนเป็นจุดสูงสุดในประวัติศาสตร์ ท่ามกลางการก่ออาชญากรรมประเภทเบานั้นการขโมยของได้เกิดขึ้นเป็นประจำทุกวี่วัน และเมื่อมีการขโมยเกิดขึ้นนั้นก็มักจะลงเอยตด้วยการที่ตำรวจสายตรวจรายหนึ่งที่เดินตรวจตราอยู่นั้นเป็นผู้ไล่ตามจับหัวขโมยไปในตรอกซอยเล็กๆ ที่เชื่อมระหว่างหัวมุมถนน (เพื่อความงายขออ้างอิงด้วยคำว่าง ''หัวมุมถนน'') แต่โชคไม่ดีเสียเลยที่บ่อยครั้ง หัวขโมยสามารถหลบหนีจากการติดตามของตำรวจได้ เพราะว่าหัวขโมยรู้จักเส้นทางในตัวเมืองดีกว่าตำรวจ
 +
 
 +
สถานีตำรวจแห่งเมืองไบท์มอร์ถูกจัดตั้งขึ้นเพื่อลดปริมาณการเกิดอาชญากรรมภยในเมือง แนวคิดหนึ่งที่จะนำมาลดปัญหาอาชญากรรมนี้คือการใช้ระบบคอมพิวเตอร์เพื่อช่วยในการติดตามจับหัวขโมย ในการนี้สถานีตำรวจแห่งเมืองไบท์มอร์ได้สร้างแผนที่ตัวเมืองอย่างชัดเจนขึ้นเรียบร้อยแล้ว ตอนนี้พวกเขาต้องการซอฟตร์แวร์ที่ใช้ในกำหนดกลยุทธในการติดตามหัวขโมย
 +
 
 +
ในการติดตามหัวขโมยโดยเจ้าหน้าที่ตำรวจรายหนึ่งนั้นจะมีรูปแบบเป็นลำดับขั้นตอนดังนี้:
 +
1. ตำรวจเลือกหัวมุมถนนหนึ่งที่จะใช้เดินสำรวจ
 +
2. ขโมยเลือกหัวมุมถนนหนึ่งที่จะทำการก่ออาชญากรรม (ทั้งนี้ขโมยรู้ว่าตำรวจอยู่ที่ใด) และตั้งแต่นี้เป็นต้นไปจะสมมติว่าทั้งตำรวจและขโมยรู้ตำแหน่งของอีกฝ่ายหนึ่งตลอดเวลา
 +
3. ตำรวจสามารถเดินไปยังหัวมุมถนนที่ติดกัน (นับจากหัวมุมถนนปัจจุบันที่เขาอยู่โดยผ่านทางเดินเส้นหนึ่ง) หรือสามารถเลือกที่จะหยุดรอ (คือเลือกที่จะไม่เดินได้)
 +
4. ขโมยจะเดินไปยังหัวมุมถนนที่ติดกันนับจากตำแหน่งที่เขาอยู่ แต่ทว่าแตกต่างจากตำรวจคือ หัวขโมยไม่สามารถหยุดรอได้ เนื่องด้วยสัญชาตญาณของขโมยจึงทำให้เค้าต้องย้ายตำแหน่งตลอดเวลา
 +
5. ตำรวจและขโมยจะเดินสลับกันคนละหนึ่งครั้ง (เริ่มต้นที่ตำรวจ) จนกว่าหนึ่งในเหตุการณ์นี้จะเกิดขึ้น:
 +
* เกิดสภาพการเดินซ้ำ (สภาพการเดินจะนิยามจากตำแหน่งของทั้งสองคนและผู้ที่จะเดินรายต่อไป) ในกรณีนี้นี้ขโมยจะสามารถหลบหนีการจับกุมได้อย่างแน่นอน ดังนั้นจะถือว่าขโมยสามารถหลบหนีสำเร็จ
 +
* ตำรวจและขโมยพบกันที่หัวมุมถนนแห่งหนึ่งภายหลังจากการเดินของฝ่ายใดฝ่ายหนึ่งก็ได้ ในกรณีนี้จะหมายถึงตำรวจสามารถจับขโมยได้สำเร็จ
 +
 
 +
** หน้าที่ของคุณ **
 +
ให้คุณเขียนโปรแกรมที่รับแผนที่ของเมืองแล้วหาว่า ตำรวจจะจับหัวขโมยได้สำเร็จหรือไม่ ถ้าสำเร็จให้แสดงการเดินเพื่อให้ตำรวจสามารถจับหัวขโมยให้ด้วย
 +
 
 +
โปรแกรมของคุณต้องสมมติว่าขโมยจะเดินด้วยวิธีการที่ดีที่สุด
 +
 
 +
** Implementation **
 +
คุณต้องเขียนสองฟังก์ชันคือ:
 +
start(N,A) เพื่อให้ในการรับแผนที่เริ่มต้น
 +
nextMove(R) เพื่อใช้ในการรับอินพุตว่าขโมยจะเดินไปที่ใด
 +
ในรายละเอียด ให้อ่านต่อที่: [Cob and Robber, BOI2014](http://www.boi2014.lmio.lt/tasks/coprobber-en.pdf)
  
 
== Day1: Three Friends ==
 
== Day1: Three Friends ==
 
== Day1: Sequence ==
 
== Day1: Sequence ==

รุ่นแก้ไขเมื่อ 04:06, 23 มิถุนายน 2557

Source: Baltic Olympiad in Informatics 2014

Day1: Cop and Robber

ณ เมืองไบท์มอร์ ระดับของอาชญากรรมได้เพิ่มขึ้นมากจนเป็นจุดสูงสุดในประวัติศาสตร์ ท่ามกลางการก่ออาชญากรรมประเภทเบานั้นการขโมยของได้เกิดขึ้นเป็นประจำทุกวี่วัน และเมื่อมีการขโมยเกิดขึ้นนั้นก็มักจะลงเอยตด้วยการที่ตำรวจสายตรวจรายหนึ่งที่เดินตรวจตราอยู่นั้นเป็นผู้ไล่ตามจับหัวขโมยไปในตรอกซอยเล็กๆ ที่เชื่อมระหว่างหัวมุมถนน (เพื่อความงายขออ้างอิงด้วยคำว่าง หัวมุมถนน) แต่โชคไม่ดีเสียเลยที่บ่อยครั้ง หัวขโมยสามารถหลบหนีจากการติดตามของตำรวจได้ เพราะว่าหัวขโมยรู้จักเส้นทางในตัวเมืองดีกว่าตำรวจ

สถานีตำรวจแห่งเมืองไบท์มอร์ถูกจัดตั้งขึ้นเพื่อลดปริมาณการเกิดอาชญากรรมภยในเมือง แนวคิดหนึ่งที่จะนำมาลดปัญหาอาชญากรรมนี้คือการใช้ระบบคอมพิวเตอร์เพื่อช่วยในการติดตามจับหัวขโมย ในการนี้สถานีตำรวจแห่งเมืองไบท์มอร์ได้สร้างแผนที่ตัวเมืองอย่างชัดเจนขึ้นเรียบร้อยแล้ว ตอนนี้พวกเขาต้องการซอฟตร์แวร์ที่ใช้ในกำหนดกลยุทธในการติดตามหัวขโมย

ในการติดตามหัวขโมยโดยเจ้าหน้าที่ตำรวจรายหนึ่งนั้นจะมีรูปแบบเป็นลำดับขั้นตอนดังนี้: 1. ตำรวจเลือกหัวมุมถนนหนึ่งที่จะใช้เดินสำรวจ 2. ขโมยเลือกหัวมุมถนนหนึ่งที่จะทำการก่ออาชญากรรม (ทั้งนี้ขโมยรู้ว่าตำรวจอยู่ที่ใด) และตั้งแต่นี้เป็นต้นไปจะสมมติว่าทั้งตำรวจและขโมยรู้ตำแหน่งของอีกฝ่ายหนึ่งตลอดเวลา 3. ตำรวจสามารถเดินไปยังหัวมุมถนนที่ติดกัน (นับจากหัวมุมถนนปัจจุบันที่เขาอยู่โดยผ่านทางเดินเส้นหนึ่ง) หรือสามารถเลือกที่จะหยุดรอ (คือเลือกที่จะไม่เดินได้) 4. ขโมยจะเดินไปยังหัวมุมถนนที่ติดกันนับจากตำแหน่งที่เขาอยู่ แต่ทว่าแตกต่างจากตำรวจคือ หัวขโมยไม่สามารถหยุดรอได้ เนื่องด้วยสัญชาตญาณของขโมยจึงทำให้เค้าต้องย้ายตำแหน่งตลอดเวลา 5. ตำรวจและขโมยจะเดินสลับกันคนละหนึ่งครั้ง (เริ่มต้นที่ตำรวจ) จนกว่าหนึ่งในเหตุการณ์นี้จะเกิดขึ้น:

  • เกิดสภาพการเดินซ้ำ (สภาพการเดินจะนิยามจากตำแหน่งของทั้งสองคนและผู้ที่จะเดินรายต่อไป) ในกรณีนี้นี้ขโมยจะสามารถหลบหนีการจับกุมได้อย่างแน่นอน ดังนั้นจะถือว่าขโมยสามารถหลบหนีสำเร็จ
  • ตำรวจและขโมยพบกันที่หัวมุมถนนแห่งหนึ่งภายหลังจากการเดินของฝ่ายใดฝ่ายหนึ่งก็ได้ ในกรณีนี้จะหมายถึงตำรวจสามารถจับขโมยได้สำเร็จ
    • หน้าที่ของคุณ **

ให้คุณเขียนโปรแกรมที่รับแผนที่ของเมืองแล้วหาว่า ตำรวจจะจับหัวขโมยได้สำเร็จหรือไม่ ถ้าสำเร็จให้แสดงการเดินเพื่อให้ตำรวจสามารถจับหัวขโมยให้ด้วย

โปรแกรมของคุณต้องสมมติว่าขโมยจะเดินด้วยวิธีการที่ดีที่สุด

    • Implementation **

คุณต้องเขียนสองฟังก์ชันคือ: start(N,A) เพื่อให้ในการรับแผนที่เริ่มต้น nextMove(R) เพื่อใช้ในการรับอินพุตว่าขโมยจะเดินไปที่ใด ในรายละเอียด ให้อ่านต่อที่: [Cob and Robber, BOI2014](http://www.boi2014.lmio.lt/tasks/coprobber-en.pdf)

Day1: Three Friends

Day1: Sequence