ดูต้นฉบับสำหรับ Poi19

== Bidding (Stage III day 1) ==

Source: [http://main.edu.pl/en/archive/oi/19/lic]

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: [http://main.edu.pl/en/archive/oi/19/pen]

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: [http://main.edu.pl/en/archive/oi/19/wyr]

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

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


== Minimalist Security ==

source: [http://main.edu.pl/en/archive/oi/19/bez]

คุณได้รับแผนที่ของระบบเครือข่ายถนนของเมือง 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: [http://main.edu.pl/en/archive/oi/19/hur]

== Prefixuffix ==

source: [http://main.edu.pl/en/archive/oi/19/pre]

ในข้อนี้เราพิจารณาสตริงที่ประกอบไปด้วยตัวอักษรภาษาอังกฤษพิมพ์เล็กเท่านั้น  เราจะเรียกส่วนเริ่มต้นของสตริงว่า 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''' จะต้องมีค่ามากที่สุด