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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 10 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 1: แถว 1:
 
Source: [http://www.boi2014.lmio.lt/tasks.html Baltic Olympiad in Informatics 2014]
 
Source: [http://www.boi2014.lmio.lt/tasks.html Baltic Olympiad in Informatics 2014]
 
== Day1: Cop and Robber  ==
 
== Day1: Cop and Robber  ==
 +
ที่มา: [http://www.boi2014.lmio.lt/tasks/coprobber-en.pdf](http://www.boi2014.lmio.lt/tasks/coprobber-en.pdf)
  
 
ณ เมืองไบท์มอร์ ระดับของอาชญากรรมได้เพิ่มขึ้นมากจนเป็นจุดสูงสุดในประวัติศาสตร์ ท่ามกลางการก่ออาชญากรรมประเภทเบานั้นการขโมยของได้เกิดขึ้นเป็นประจำทุกวี่วัน และเมื่อมีการขโมยเกิดขึ้นนั้นก็มักจะลงเอยตด้วยการที่ตำรวจสายตรวจรายหนึ่งที่เดินตรวจตราอยู่นั้นเป็นผู้ไล่ตามจับหัวขโมยไปในตรอกซอยเล็กๆ ที่เชื่อมระหว่างหัวมุมถนน (เพื่อความงายขออ้างอิงด้วยคำว่าง ''หัวมุมถนน'') แต่โชคไม่ดีเสียเลยที่บ่อยครั้ง หัวขโมยสามารถหลบหนีจากการติดตามของตำรวจได้ เพราะว่าหัวขโมยรู้จักเส้นทางในตัวเมืองดีกว่าตำรวจ
 
ณ เมืองไบท์มอร์ ระดับของอาชญากรรมได้เพิ่มขึ้นมากจนเป็นจุดสูงสุดในประวัติศาสตร์ ท่ามกลางการก่ออาชญากรรมประเภทเบานั้นการขโมยของได้เกิดขึ้นเป็นประจำทุกวี่วัน และเมื่อมีการขโมยเกิดขึ้นนั้นก็มักจะลงเอยตด้วยการที่ตำรวจสายตรวจรายหนึ่งที่เดินตรวจตราอยู่นั้นเป็นผู้ไล่ตามจับหัวขโมยไปในตรอกซอยเล็กๆ ที่เชื่อมระหว่างหัวมุมถนน (เพื่อความงายขออ้างอิงด้วยคำว่าง ''หัวมุมถนน'') แต่โชคไม่ดีเสียเลยที่บ่อยครั้ง หัวขโมยสามารถหลบหนีจากการติดตามของตำรวจได้ เพราะว่าหัวขโมยรู้จักเส้นทางในตัวเมืองดีกว่าตำรวจ
แถว 14: แถว 15:
 
* เกิดสภาพการเดินซ้ำ (สภาพการเดินจะนิยามจากตำแหน่งของทั้งสองคนและผู้ที่จะเดินรายต่อไป) ในกรณีนี้นี้ขโมยจะสามารถหลบหนีการจับกุมได้อย่างแน่นอน ดังนั้นจะถือว่าขโมยสามารถหลบหนีสำเร็จ
 
* เกิดสภาพการเดินซ้ำ (สภาพการเดินจะนิยามจากตำแหน่งของทั้งสองคนและผู้ที่จะเดินรายต่อไป) ในกรณีนี้นี้ขโมยจะสามารถหลบหนีการจับกุมได้อย่างแน่นอน ดังนั้นจะถือว่าขโมยสามารถหลบหนีสำเร็จ
 
* ตำรวจและขโมยพบกันที่หัวมุมถนนแห่งหนึ่งภายหลังจากการเดินของฝ่ายใดฝ่ายหนึ่งก็ได้ ในกรณีนี้จะหมายถึงตำรวจสามารถจับขโมยได้สำเร็จ
 
* ตำรวจและขโมยพบกันที่หัวมุมถนนแห่งหนึ่งภายหลังจากการเดินของฝ่ายใดฝ่ายหนึ่งก็ได้ ในกรณีนี้จะหมายถึงตำรวจสามารถจับขโมยได้สำเร็จ
 +
  
 
'''หน้าที่ของคุณ'''
 
'''หน้าที่ของคุณ'''
 +
 
ให้คุณเขียนโปรแกรมที่รับแผนที่ของเมืองแล้วหาว่า ตำรวจจะจับหัวขโมยได้สำเร็จหรือไม่ ถ้าสำเร็จให้แสดงการเดินเพื่อให้ตำรวจสามารถจับหัวขโมยให้ด้วย  
 
ให้คุณเขียนโปรแกรมที่รับแผนที่ของเมืองแล้วหาว่า ตำรวจจะจับหัวขโมยได้สำเร็จหรือไม่ ถ้าสำเร็จให้แสดงการเดินเพื่อให้ตำรวจสามารถจับหัวขโมยให้ด้วย  
  
 
โปรแกรมของคุณต้องสมมติว่าขโมยจะเดินด้วยวิธีการที่ดีที่สุด
 
โปรแกรมของคุณต้องสมมติว่าขโมยจะเดินด้วยวิธีการที่ดีที่สุด
 +
  
 
'''Implementation'''
 
'''Implementation'''
 +
 
คุณต้องเขียนสองฟังก์ชันคือ:
 
คุณต้องเขียนสองฟังก์ชันคือ:
 
start(N,A) เพื่อให้ในการรับแผนที่เริ่มต้น
 
start(N,A) เพื่อให้ในการรับแผนที่เริ่มต้น
 
nextMove(R) เพื่อใช้ในการรับอินพุตว่าขโมยจะเดินไปที่ใด
 
nextMove(R) เพื่อใช้ในการรับอินพุตว่าขโมยจะเดินไปที่ใด
−
ในรายละเอียด ให้อ่านต่อที่: [Cob and Robber, BOI2014](http://www.boi2014.lmio.lt/tasks/coprobber-en.pdf)
+
 
 +
สำหรับรายละเอียดเพิ่มเติม กรุณาอ่านต่อที่: [Cob and Robber, BOI2014](http://www.boi2014.lmio.lt/tasks/coprobber-en.pdf)
  
 
== Day1: Three Friends ==
 
== Day1: Three Friends ==
 +
 +
ที่มา: [http://www.boi2014.lmio.lt/tasks/friends-en.pdf](http://www.boi2014.lmio.lt/tasks/friends-en.pdf)
 +
 +
เพื่อนสามคนเล่นเกมหนึ่งดังนี้ เพื่อนคนที่หนึ่งเลือกสายอักษร S ขึ้นมาหนึ่งสาย ต่อมาเพื่อนคนที่สองจะสร้างสายอักษรใหม่ T ขึ้นจากการเอาสายอักษร S สองชุดมาต่อกัน และท้ายที่สุดเพื่อนคนที่สามจะเติมอักษรเข้าไปหนึ่งตัวไปในสายอักษร T โดยอาจจะเพิ่มที่ตำแหน่งเริ่มต้น, สิ้นสุด, หรือตำแหน่งใดๆ ในสายอักษร T ก็ได้ เพื่อสร้างเป็นสายอักษร U
 +
 +
 +
'''หน้าที่ของคุณ'''
 +
 +
รับสายอักษร U และให้คุณหาช่วยสร้างสายอักษรเริ่มต้น S
 +
 +
 +
'''ข้อมูลนำเข้า'''
 +
 +
บรรทัดแรก ประกอบด้วยจำนวนหนึ่งจำนวน N ที่แสดงความยาวของสายอักษร U, ข้อมูลสายอักษร U จะระบุในบรรทัดที่สอง ซึ่งจะประกอบด้วยอักษรตัวใหญ่ในภาษาอังกฤษ (A,B,C,..,Z) ทั้งสิ้น N อักษร
 +
 +
 +
'''ข้อมูลส่งออก'''
 +
 +
ให้โปรแกรมของคุณแสดงสายอักษรเริ่มต้น S ยกเว้นสองกรณีด้านล่าง:
 +
 +
1. ถ้าสายอักษร U ไม่สามารถถูกสร้างขึ้นโดยใช้กระบวนการสร้างด้านบน ให้โปรแกรมตอบว่า NOT POSSIBLE
 +
 +
2. ถ้าสายอักษรเริ่มต้น S เป็นไปได้มากกว่า 1 รูปแบบ ให้โปรแกรมตอบว่า NOT UNIQUE
 +
 +
 +
'''ตัวอย่าง 1'''
 +
 +
''-- input --''
 +
 +
7
 +
 +
ABXCABC
 +
 +
''-- output --''
 +
 +
ABC
 +
 +
 +
'''ตัวอย่าง 2'''
 +
 +
''-- input --''
 +
 +
6
 +
 +
ABCDEF
 +
 +
''-- output --''
 +
 +
NOT POSSIBLE
 +
 +
 +
'''ตัวอย่าง 3'''
 +
 +
''-- input --''
 +
 +
9
 +
 +
ABABABABA
 +
 +
''-- output --''
 +
 +
NOT UNIQUE
 +
 +
 +
'''เกณฑ์การให้คะแนน'''
 +
 +
35 คะแนน: 2 <= N <= 2001
 +
 +
65 คะแนน: 2 <= N <= 2000001
 +
 
== Day1: Sequence ==
 
== Day1: Sequence ==
 +
 +
ที่มา: [http://www.boi2014.lmio.lt/tasks/sequence-en.pdf](http://www.boi2014.lmio.lt/tasks/sequence-en.pdf)
 +
 +
อดัมเขียนลำดับของจำนวนเต็ม K จำนวนที่ติดกันที่เริ่มต้นด้วยจำนวน N ลงบนกระดานดำ ่แต่ในขณะที่เขาไม่อยู่นั้น บิลลี่ได้เข้ามาในห้องและลบตัวเลขออกโดยเหลือไว้เพียงเลขโดดหนึ่งหลักของแต่ละจำนวนเท่านั้น ดังนั้นจะเหลือเพียงลำดับของตัวเลขโดด K ตัวเท่านั้น
 +
 +
 +
'''หน้าที่ของคุณ'''
 +
 +
จากลำดับของตัวเลขโดดที่เหลืออยู่บนกระดานดำ ให้คุณหาจำนวนที่เล็กที่สุด N ที่เป็นค่าเริ่มต้นของลำดับทั้งหมดบนกระดาน
 +
 +
 +
'''ข้อมูลนำเข้า'''
 +
 +
บรรทัดแรก ประกอบด้วยตัวเลขจำนวนเต็มหนึ่งจำนวน K ที่แสดงถึงความยาวของลำดับ
 +
 +
บรรทัดที่สอง ประกอบด้วยจำนวนเต็มที่แสดงตัวเลขโดดทั้งหมด K ตัว B1, B2, ..., Bk ที่บิลลี่เหลือไว้ให้ (0 <= Bi <= 9) ตามลำดับของตัวเลขที่ปรากฎอยู่บนกระดาน
 +
 +
 +
'''ข้อมูลส่งออก'''
 +
 +
ให้แสดงคำตอบเพียงหนึ่งบรรทัด ที่ประกอบด้วยจำนวนหนึ่งจำนวน N ที่เป็นค่าเริ่มต้นของลำดับ
 +
 +
 +
'''ตัวอย่าง'''
 +
 +
''-- input --''
 +
 +
6
 +
 +
7 8 9 5 1 2
 +
 +
''-- output --''
 +
 +
47
 +
 +
''-- อธิบาย --''
 +
 +
เมื่อ N = 47 หมายถึงลำดับของตัวเลขที่อดัมเขียนไว้คือ 47 48 49 50 51 52 ซึ่งประกอบด้วยตัวเลขทั้งหมดที่บิลลี่เหลือไว้ให้ และไม่มีจำนวนที่เล็กกว่า 47 ที่ทำให้เงื่อนไขเป็นจริงได้ ดังนั้นคำตอบจึงเป็น 47
 +
 +
 +
'''การให้คะแนน'''
 +
 +
9 คะแนน:  1 <= K <= 1,000 และ คำตอบที่ถูกต้องมีค่าไม่เกิน 1000
 +
 +
33 คะแนน:  1 <= K <= 1,000
 +
 +
25 คะแนน:  1 <= K <= 100,000 และ เลขโดดทุกจำนวนมีค่าเท่ากันหมด
 +
 +
33 คะแนน:  1 <= K <= 100,000
 +
 +
 +
'''เงื่อนไข'''
 +
 +
เวลาจำกัด 1 วินาที
 +
 +
หน่วยความจำจำกัด 256 MB

รุ่นแก้ไขปัจจุบันเมื่อ 07:54, 23 มิถุนายน 2557

Source: Baltic Olympiad in Informatics 2014

Day1: Cop and Robber

ที่มา: [1](http://www.boi2014.lmio.lt/tasks/coprobber-en.pdf)

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

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

ในการติดตามหัวขโมยโดยเจ้าหน้าที่ตำรวจรายหนึ่งนั้นจะมีรูปแบบเป็นลำดับขั้นตอนดังนี้: 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

ที่มา: [2](http://www.boi2014.lmio.lt/tasks/friends-en.pdf)

เพื่อนสามคนเล่นเกมหนึ่งดังนี้ เพื่อนคนที่หนึ่งเลือกสายอักษร S ขึ้นมาหนึ่งสาย ต่อมาเพื่อนคนที่สองจะสร้างสายอักษรใหม่ T ขึ้นจากการเอาสายอักษร S สองชุดมาต่อกัน และท้ายที่สุดเพื่อนคนที่สามจะเติมอักษรเข้าไปหนึ่งตัวไปในสายอักษร T โดยอาจจะเพิ่มที่ตำแหน่งเริ่มต้น, สิ้นสุด, หรือตำแหน่งใดๆ ในสายอักษร T ก็ได้ เพื่อสร้างเป็นสายอักษร U


หน้าที่ของคุณ

รับสายอักษร U และให้คุณหาช่วยสร้างสายอักษรเริ่มต้น S


ข้อมูลนำเข้า

บรรทัดแรก ประกอบด้วยจำนวนหนึ่งจำนวน N ที่แสดงความยาวของสายอักษร U, ข้อมูลสายอักษร U จะระบุในบรรทัดที่สอง ซึ่งจะประกอบด้วยอักษรตัวใหญ่ในภาษาอังกฤษ (A,B,C,..,Z) ทั้งสิ้น N อักษร


ข้อมูลส่งออก

ให้โปรแกรมของคุณแสดงสายอักษรเริ่มต้น S ยกเว้นสองกรณีด้านล่าง:

1. ถ้าสายอักษร U ไม่สามารถถูกสร้างขึ้นโดยใช้กระบวนการสร้างด้านบน ให้โปรแกรมตอบว่า NOT POSSIBLE

2. ถ้าสายอักษรเริ่มต้น S เป็นไปได้มากกว่า 1 รูปแบบ ให้โปรแกรมตอบว่า NOT UNIQUE


ตัวอย่าง 1

-- input --

7

ABXCABC

-- output --

ABC


ตัวอย่าง 2

-- input --

6

ABCDEF

-- output --

NOT POSSIBLE


ตัวอย่าง 3

-- input --

9

ABABABABA

-- output --

NOT UNIQUE


เกณฑ์การให้คะแนน

35 คะแนน: 2 <= N <= 2001

65 คะแนน: 2 <= N <= 2000001

Day1: Sequence

ที่มา: [3](http://www.boi2014.lmio.lt/tasks/sequence-en.pdf)

อดัมเขียนลำดับของจำนวนเต็ม K จำนวนที่ติดกันที่เริ่มต้นด้วยจำนวน N ลงบนกระดานดำ ่แต่ในขณะที่เขาไม่อยู่นั้น บิลลี่ได้เข้ามาในห้องและลบตัวเลขออกโดยเหลือไว้เพียงเลขโดดหนึ่งหลักของแต่ละจำนวนเท่านั้น ดังนั้นจะเหลือเพียงลำดับของตัวเลขโดด K ตัวเท่านั้น


หน้าที่ของคุณ

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


ข้อมูลนำเข้า

บรรทัดแรก ประกอบด้วยตัวเลขจำนวนเต็มหนึ่งจำนวน K ที่แสดงถึงความยาวของลำดับ

บรรทัดที่สอง ประกอบด้วยจำนวนเต็มที่แสดงตัวเลขโดดทั้งหมด K ตัว B1, B2, ..., Bk ที่บิลลี่เหลือไว้ให้ (0 <= Bi <= 9) ตามลำดับของตัวเลขที่ปรากฎอยู่บนกระดาน


ข้อมูลส่งออก

ให้แสดงคำตอบเพียงหนึ่งบรรทัด ที่ประกอบด้วยจำนวนหนึ่งจำนวน N ที่เป็นค่าเริ่มต้นของลำดับ


ตัวอย่าง

-- input --

6

7 8 9 5 1 2

-- output --

47

-- อธิบาย --

เมื่อ N = 47 หมายถึงลำดับของตัวเลขที่อดัมเขียนไว้คือ 47 48 49 50 51 52 ซึ่งประกอบด้วยตัวเลขทั้งหมดที่บิลลี่เหลือไว้ให้ และไม่มีจำนวนที่เล็กกว่า 47 ที่ทำให้เงื่อนไขเป็นจริงได้ ดังนั้นคำตอบจึงเป็น 47


การให้คะแนน

9 คะแนน: 1 <= K <= 1,000 และ คำตอบที่ถูกต้องมีค่าไม่เกิน 1000

33 คะแนน: 1 <= K <= 1,000

25 คะแนน: 1 <= K <= 100,000 และ เลขโดดทุกจำนวนมีค่าเท่ากันหมด

33 คะแนน: 1 <= K <= 100,000


เงื่อนไข

เวลาจำกัด 1 วินาที

หน่วยความจำจำกัด 256 MB

ดึงข้อมูลจาก "https://theory.cpe.ku.ac.th/wiki/index.php?title=Baltic2014&oldid=43512"