Poi19

Bidding (Stage III day 1)

Source: [1]

Alois และ Byteasar เล่นเกมประมูล พวกเขาใช้เบี้ยจำนวนมากเพื่อเล่นเกมนนี้ ผู้เล่นแต่ละคนจะสลับกันเล่น Alois จะเริ่มเล่นก่อน จากนั้นจะตามด้วย Byteasar ปัจจัยที่เกี่ยวข้องกับการเล่นมีสองอย่างคือ: ขนาดปัจจุบันของ pot และขนาดปัจจุบันของ stack เมื่อเริ่มต้น stack จะว่างเปล่า และใน pot จะมีเบี้ยหนึ่งอัน ในแต่ละการเดิน ผู้เล่นจะเลือกทางเลือกได้ดังนี้:

• เพิ่มเบี้ยใน pot ให้เป็นสองเท่า (เช่น จาก 10 กลายเป็น 20)
• เพิ่มเบี้ยใน pot ให้เป็นสามเท่า (เช่น จาก 10 กลายเป็น 30)
• ผ่าน

เมื่อผู้เล่นเลือกผ่าน เบี้ยใน pot จะถูกนำไปรวมใน stack (นี่เป็นวิธีเดียวที่ stack จะเพิ่มขนาดได้) และเกมก็จะกลับไปเริ่มต่อโดยมีเบี้ยหนึ่งอันใน pot อีกครั้ง เมื่อผู้เล่นเลือก "ผ่าน" ตาต่อไปจะเป็นของผู้เล่นอีกคน (Alois จะเริ่มเล่นก่อนเมื่อเกมเริ่มเท่านั้น สำหรับรอบอื่น ๆ จะใช้เกณฑ์ตามที่ระบุข้างต้น) ผู้เล่นที่ทำให้เกิดการ overflow นั่นคือเกิดเหตุการณ์ที่ stack มีเบี้ยไม่น้อยกว่า n จะเป็นฝ่ายแพ้ ถ้าจำนวนของเบี้ยใน stack และใน pot รวมกันแล้วไม่น้อยกว่า n ในตาที่ผู้เล่นจะต้องเลือกเดิน ผู้เล่นจะไม่สามารถเพิ่มเบี้ยใน pot ได้อีก และจะต้องเลือก "ผ่าน" เท่านั้น ซึ่งนั่นจะทำให้ผู้เล่นคนนั้นเป็นฝ่ายแพ้

Alois แพ้บ่อยมาก Byteasar จึงให้เขาไปเขียนโปรแกรมมาเพื่อเล่นเกม แต่เขาเขียนไม่เป็น จึงต้องเป็นหน้าที่ของคุณที่จะช่วยเขาแล้ว

Salaries (Stage III day 1)

Source: [2]

Byteotian Software Corporation (BSC) มีพนักงาน n คน เนื่องจากระบบลำดับชั้นที่เข้มงวดของ BSC พนักงานทุกคนจะมีผู้หัวหน้าที่ขึ้นตรงอยู่ (เป็น direct supervisor) ยกเว้น CEO ที่พนักงานทุกคนใน BSC จะอยู่ภายใต้การดูแล อาจจะขึ้นตรงหรือไม่ก็ได้ พนักงานแต่ละคนจะมีเงินเดือนที่ไม่เท่ากัน โดยมีขอบเขตอยู่ระหว่าง 1 ถึง n บาท หัวหน้าทุกคนจะมีรายได้มากกว่าลูกน้อง

ตามกฎหมายแล้ว เงินเดือนของพนักงานบางคนจะต้องถูกเปิดเผยสู่สาธารณะ ถ้าเงินเดือนของพนักงานคนไหนถูกเปิดเผย เงินเดือนของหัวหน้าของพนักงานคนนั้นก็จะต้องถูกเปิดเผยด้วยเช่นกัน

Byteotian Internal Revenue Anti-Corruption Service (BIRAS) ต้องการเข้าไปตรวจสอบ BSC แต่ก่อนที่จะเข้าไปตรวจ พวกเขาต้องการทราบเงินเดือนของพนักงานทุกคนใน BSC ที่ไม่ถูกเปิดเผย แต่สามารถระบุได้จากข้อมูลของเงินเดือนของพนักงานที่เปิดเผยออกมาแล้ว

Leveling Ground (Stage III day 1)

Source: [3]

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

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

Minimalist Security

source: [4]

คุณได้รับแผนที่ของระบบเครือข่ายถนนของเมือง Mafiatown เครือข่ายประกอบด้วยแยกและถนนสองทิศทางที่เชื่อมระหว่างแยกต่าง ๆ ถนนจะตัดกันเฉพาะที่แยกเท่านั้น แต่ถนนสามารถข้ามกันหรือลอดกันได้ แต่ละคู่ของแยกจะเชื่อมกันด้วยถนนอย่างมากหนึ่งเส้น ที่ทุก ๆ แยก v จะมีสถานีตำรวจที่มีตำรวจดูแล p(v) คน ถนนเชื่อมระหว่างแยก u และ v จะปลอดภัยถ้ามีตำรวจรวมอย่างน้อย b(u,v) คนจากสองสถานีที่เป็นแยกปลายถนนดังกล่าว เมื่อเริ่มต้น p(u)+p(v) >= b(u,v) สำหรับทุก ๆ ถนน

อย่างไรก็ตาม เนื่องจากวิกฤตการณ์ Byteasar ผู้ว่าของเมืองจึงได้สั่งกฎ Minimalist Security Act (MSA) ที่ระบุว่า

• ตำรวจจำนวนหนึ่ง (ซึ่งอาจจะเป็น 0) จะถูกปลดประจำการจากแต่ละสถานีประจำแยก เราจะให้ z(v) แทนจำนวนดังกล่าวสำหรับแยก v

• หลังจากการปลดประจำการ จำนวนตำรวจรวมของแต่ละแยกที่เป็นจุดปลายของถนนเส้นใด (สมมติว่าเป็นแยก u และ v) จะต้องมีจำนวนเท่ากับ b(u,v) พอดี นั่นคือ p(u)-z(u) + p(v)-z(v)=b(u,v)

กฎนี้ไม่จำเป็นต้องระบุรูปแบบการปลดประจำการที่ได้ผลรวมของจำนวนตำรวจที่ปลดประจำการได้แบบเดียว ดังนั้น Byteasar สงสัยว่าจำนวนตำรวจที่จะปลดประจำการที่น้อยที่สุด และจำนวนที่มากที่สุดที่เป็นไปได้ ที่ยังสอดคล้องกับเงื่อนไขดังกล่าวด้านบน จะเป็นเท่าใด

Warehouse Store

source: [5]

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

เพื่อเป้าหมายนี้ เขาจึงได้เตรียมเขียนแผนการทำงานสำหรับอีก n วันถัดไป

เขาได้วิเคราะห์สัญญาที่ทำกับผู้ผลิตพื้น และคำนวณลำดับ a1, a2,..., an โดยที่จำนวน ai จะระบุว่ามีแท่งไม้จำนวน ai แท่งส่งถึงโรงงานในเช้าของวันที่ i

Byteasar ยังได้ทำรายการใบสั่งซื้อจากลูกค้า จากข้อมูลเหล่านั้น เขาสามารถระบุลำดับ b1,b2,...,bn โดยที่จำนวน bi ระบุว่า ตอนเที่ยงของวันที่ i ลูกค้าจะซื้อแท่งไม้จำนวน bi แท่ง ถ้า Byteasar ตกลงว่าจะขายของให้กับลูกค้าในวันนั้น เขาจะต้องส่งมอบแท่งไม้ตามจำนวนนั้นให้กับลูกค้า ถ้ามีแท่งไม้ในโกดังไม่พอเมื่อมีการสั่งซื้อ Byteasar จะต้องปฏิเสธการซื้อนั้นไป แต่ถ้ามีแท่งไม้พอ Byteasar จะสามารถเลือกที่จะขายแท่งไม้ให้ หรือจะปฏิเสธก็ได้

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

Prefixuffix

source: [6]

ในข้อนี้เราพิจารณาสตริงที่ประกอบไปด้วยตัวอักษรภาษาอังกฤษพิมพ์เล็กเท่านั้น เราจะเรียกส่วนเริ่มต้นของสตริงว่า prefix ในขณะที่จะเรียกส่วนท้ายของสตริงว่า suffix นอกจากนี้ สตริงว่าง จะถูกนับว่าเป็นทั้ง prefix และ suffix ของสตริงใด ๆ สตริงสองสตริงจะเรียกว่าเหมือนกันเชิงวงรอบ (cyclically equivalent) ถ้าสตริงหนึ่งสามารถสร้างได้จากอีกสตริงหนึ่ง โดยการย้าย suffix ของสตริงนั้นไปไว้ตอนหน้าของสตริงดังกล่าว ยกตัวอย่างเช่น สตริง ababba และ abbaab นั่นเหมือนกันเชิงวงรอบ ในขณะที่ ababba กับ ababab นั้นไม่ใช่ นอกจากนี้ ทุก ๆ สตริงยังเหมือนกันเชิงวงรอบกับตัวเอง

คุณได้รับสตริง t ที่ประกอบด้วยตัวอักษร n ตัว เราต้องการหา prefix p และ suffix s ที่มีความยาวเท่ากันที่:

• p และ s นั้นเหมือนกันเชิงวงรอบ (cyclically equivalent)
• ความยาวของทั้ง p และ s จะต้องไม่มากกว่า n/2 (นั่นคือ p และ s จะต้องไม่ทับกันใน t)
• ความยาวของทั้ง p และ s จะต้องมีค่ามากที่สุด