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]

Prefixuffix

source: [6]

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