USACO Jan 2012

Problem 1: Video Game Combos [Neal Wu, 2012]

Source: USACO

เบซซี่กำลังเล่นวิดีโอเกม ในเกมนี้ ตัวอักษร ‘A’, ‘B’, และ ‘C’ เป็นปุ่มที่กดได้เท่านั้น  เบซซี่สามารถกดปุ่มเหล่านี้ในลำดับใด ๆ ก็ได้ที่เธอชอบ อย่างไรก็ตาม จะมีรูปแบบคอมโบที่เป็นไปได้แตกต่งกันทั้งสิ้น N รูปแบบ  (1 <= N <= 20) คอมโบที่ i จะแสดงด้วยสตริง S_i ที่มีความยาวระหว่าง 1 ถึง 15 ที่ประกอบด้วยตัวอักษร ‘A’, ‘B’ หรือ ‘C’

เมื่อใดที่เบซซี่กดปุ่มแล้วได้รูปแบบตรงกับคอมโบ เธอจะได้รับคะแนนหนึ่งแต้มสำหรับคอมโบนั้น คอมโบสามารถซ้อนทับกันได้ หรือกระทั่งกดเสร็จได้พร้อมกัน  ยกตัวอย่างเช่น ถ้า N = 3 และคอมโบที่เป็นไปได้คือ “ABA”, “CB”, และ “ABACB”  ถ้าเบซซี่กด “ABACB” เธอจะได้คะแนน 3 แต้ม  เบซซี่สามารถได้คะแนนจากบางคอมโบได้มากกว่าหนึ่งครั้ง

แน่นอนที่เบซซี่ต้องการจะได้คะแนนให้ได้เร็วที่สุดเท่าที่จะทำได้ ถ้าเธอกดปุ่ม K ปุ่ม (1 <= K <= 1,000) คะแนนมากที่สุดที่เธอทำได้เป็นเท่าใด?


Problem 2: Cow Run [Mark Gordon, 2011]

Source: USACO

ชาวนาจอห์นและเบซซี่ได้คิดค้นเกมสำหรับออกกำลังกายแบบใหม่สำหรับวัว  เหล่าวัวจะวิ่งบนลู่วิ่งวงกลมความยาว M (2 <= M <= 1,000,000,000) โดยเริ่มจากจุดเริ่มต้นเดียวกัน  เกมจะดำเนินไป N รอบ (1 <= N <= 14) และใช้สำรับไพ่ขนาด 8N ใบ ที่แต่ละใบมีหมายเลข X_i (0 <= X_i < M) เขียนอยู่

ในแต่ละรอบ ชจ. จะแยกไพ่ด้านบนสุด 8 ใบไปยังกองไพ่ใหม่ จากนั้นจะเลือกไพ่ 4 ใบด้านบน หรือ 4 ใบด้านล่างให้เบซซี่นำไปเล่น  เบซซี่จะเลือกไพ่ด้านบน 2 ใบ หรือด้านล่าง 2 ใบจากไพ่ 4 ใบที่ ชจ. เลือก หลังจากนั้น ชจ. จะอ่านจำนวน X_top บนไพ่ใบบน และเหล่าวัวจะวิ่งไปเป็นระยะทาง R*X_top, โดยที่ R คือระยะทางที่วัววิ่งมาแล้ว.  เบซซี่ก็จะอ่านจำนวน X_bottom ที่อยู่ที่ไพ่ใบล่าง และเหล่าวัวก็จะวิ่งไปอีกเป็นระยะทาง X_bottom

ชจ. เป็นห่วงว่าหลังจากการออกกำลังกาย เหล่าวัวจะเหนื่อยเกินไปที่จะกลับไปที่จุดเริ่มต้นของลู่วิ่งถ้าพวกมันไปหยุดที่จุดที่ห่างไกลเกินไป  เขาเชื่อว่าถ้าวัวไปหยุดที่ระยะทางมากกว่า K (0 <= K <= floor(M/2)) จากจุดเริ่มต้น พวกมันจะไม่สามารถกลับบ้านได้

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


Problem 3: Bovine Alliance [Mark Gordon, 2011]

Source: USACO

เบซซี่และเพื่อนของเธอในฟาร์มใกล้ ๆ กันได้ตกลงว่าจะเชื่อมฟาร์มเข้าด้วยกันด้วยทางเดินเพื่อเป็นการสร้างพันธมิตรที่ต่อต้านเหล่าเหล่าชาวนา  เหล่าวัวในฟาร์มจำนวน N ฟาร์ม (1 <= N <= 100,000) ได้รับคำสั่งให้สร้างทางเชื่อมไปยังอีกหนึ่งฟาร์มพอดี (หนึ่งฟาร์มเท่านั้น ไม่มากไม่น้อยกว่านี้) ทำให้มีจำนวนทางเดินที่จะสร้างทั้งสิ้น N ทางเดิน อย่างไรก็ตาม ผ่านไปหลายเดือน ทางเดินที่สร้างเสร็จมีเพียงแค่ M ทางเท่านั้น (1 <= M < N)

ข้อถกเถียงระหว่างฟาร์มว่าฟาร์มใดสร้างทางไม่เสร็จแทบจะทำให้พันธมิตรแทบแตกสลาย  เพื่อลดความตึงเครียด เบซซี่ต้องการที่จะคำนวณหาจำนวนวิธีที่เป็นไปได้ที่ทางที่สร้างแล้ว M เส้นนี้จะถูกสร้างโดยฟาร์มใด  ยกตัวอย่างเช่น ถ้ามีทางเชื่อมระหว่างฟาร์ม 3 และ 4  ความเป็นไปได้หนึ่งก็คือฟาร์ม 3 สร้างทางเชื่อม อีกความเป็นไปได้หนึ่งก็คือฟาร์ม 4 สร้างทางเชื่อม  ช่วยเบซซี่คำนวณจำนวนวิธีที่จะกำหนดทางเชื่อมให้กับฟาร์มที่เป็นคนสร้าง (modulo 1,000,000,007)   วิธีสองวิธีจะแตกต่างกันถ้ามีอย่างน้อยหนึ่งเส้นทางที่ถูกเลือกฟาร์มที่สร้างที่แตกต่างกัน

 

Advertisements

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s