Poi17

เกมรวมแต้มต่ำ (The Minima Game)

หน่วยความจำ 32 MB
ช่วงนี้อลิสและบ๊อบชอบเล่นเกมรวมแต้มต่ำเป็นอย่างมาก กฎิกาของเกมนี้คือ เริ่มต้นจะมีไพ่จำนวนหนึ่งวางหงายอยู่บนโต๊ะ โดยไพ่แต่ละใบจะมีแต้มบนไพ่เป็นจำนวนเต็มบวกหนึ่งจำนวน ผู้เล่นจะสลับกันเล่นทีละคน โดยอลิสจะเป็นผู้เริ่มก่อนเสมอ การเล่นแต่ละครั้งผู้เล่นสามารถที่จะเลือกไพ่อย่างน้อย 1 ใบจากบนโต๊ะแล้วรวมเข้ากับไพ่ในมือของตน และผู้เล่นจะได้รับคะแนนเท่ากับหน้าไพ่ใบที่น้อยที่สุดที่มีในมือ จากนั้นเกมจะสลับให้ผู้เล่นอีกฝ่ายหนึ่งเล่น เกมนี้จะจบลงเมื่อบนโต๊ะไม่เหลือไพ่ใดๆ เป้าหมายของเกมนี้คือ ผู้เล่นต้องการทำคะแนนที่ตนได้รับมีค่ามากกว่าคะแนนที่ฝ่ายตรงข้ามจะได้รับ มากที่สุดเท่าที่จะทำได้ ทั้งนี้อลิสและบ๊อบได้รู้มาว่าในการเล่นเกมนี้นั้นมีกลยุทธที่ดีที่สุด (optimal strategy) ในการเล่นอยู่ ดังนั้นพวกเขาจึงต้องการให้คุณช่วยเขียนโปรแกรมขึ้นเพื่อหาว่า หากทั้งอลิสและบ๊อบใช้กลยุทธที่ดีที่สุดแล้ว ผลลัพธ์สุดท้ายที่คือความต่างระหว่างคะแนนทั้งสองคน จะมีค่าเป็นเท่าไร
ข้อมูลนำเข้า
บรรทัดแรก รับจำนวนเต็มหนึ่งจำนวน n (1 ≤ n ≤ 1,000,000) ที่แสดงถึงจำนวนของไพ่ทั้งหมด (เริ่มต้นไพ่ทั้งหมดอยู่บนโต๊ะ) บรรทัดที่สอง รับจำนวนเต็มทั้งหมด n จำนวนที่แสดงค่าของไพ่ในแต่ละใบ k1, k2, …, kn (1 ≤ ki ≤ 109) คั่นด้วยช่องว่าง
ข้อมูลส่งออก
ให้แสดงคำตอบด้วยจำนวนเต็มหนึ่งจำนวน ที่หมายถึงคะแนนที่อลิสได้รับมากกว่าบ๊อบเมื่อทั้งคู่เล่นโดยใช้กลยุทธที่ดีที่สุด แต่ถ้าบ๊อบได้คะแนนมากว่าให้ตอบเป็นจำนวนเต็มลบ
ตัวอย่าง
ข้อมูลนำเข้า
3

ข้อมูลส่งออก
1 3 1 2

อธิบาย
เริ่มต้นอลิสเลือกไพ่มาหนึ่งใบคือ 3 ทำให้อลิสได้คะแนน 3 หน่วย, จากนั้นบ๊อบเลือกไพ่ทั้งสองใบที่เหลือ และบ๊อบจะได้คะแนน 1 หน่วย, จากนั้นเกมจะจบลงผลต่างคะแนนจึงเป็น 2 หน่วย

---

โคมไฟ (Lamp)

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

ในยามดึกทุกคืนที่หอคู่ดูดาว ซึ่งเป็นที่อาศัยของโนบิตะนั้น จะมีการจุดโคมไฟไว้ที่ทางเข้าที่ชั้นล่างสุดของตึก แต่ว่าแสงไฟอันสว่างจ้าได้ขัดขวางการนอนของโนบิตะทำให้นอนไม่หลับ และถึงแม้ว่าโคมไฟจะไม่ได้ส่องมาที่หน้าต่างของห้องโนบิตะโดยตรง แต่แสงก็ยังสามารถสะท้อนจากหน้าต่างห้องอื่นเข้ามายังห้องของโนบิตะได้เสมอๆ จากการคับแค้นใจที่ไม่ได้นอน โนบิตะจึงต้องการหาทางผ่อนคลายเพื่อปลอบใจตนเองขึ้น คือโนบิตะต้องการทราบว่ามีห้องใดบ้างที่ถูกทรมานในแบบเดียวกัน (คือแสงของโคมไฟไฟส่องเข้าห้องเช่นกัน) โนบิตะได้ขอร้องให้คุณช่วยเหลือเขาในการแก้ปัญหานี้ และคุณรู้ดีว่าถ้าคุณไม่ช่วยโนบิตะแล้วล่ะก็ คุณก็จะต้องอดนอนเช่นกันจนกว่าคุณจะแก้ปัญหานี้ได้ โนบิตะอาศัยอยู่ในอาคาร B ซึ่งอาคารนี้มีทั้งหมด n หน้าต่าง, โคมไฟจะแขวนอยู่ที่กำแพงที่ตำแหน่งต่ำสุดของอาคารนี้, ในฝั่งตรงข้ามกับอาคาร B จะเป็นอาคาร C ที่ตั้งห่างออกไป 10 เมตรพอดี, แนวกำแพงของอาคาร C จะเป็นระบาบที่ขนานกันกับแนวกำแพง (แนวระนาบ) ของอาคาร B โดยอาคาร C มีหน้าต่างทั้งหมด m บาน โคมไฟจะส่องแสงดังที่คุณคาดการณ์ไว้ คือ จะส่องแสงเป็นแส้นตรงออกจากโคมไฟ และเมื่อแสงโคมไฟกระทบกับหน้าต่าง, แสงจะสะท้อนออกตามกฎการสะท้อนคือมุมตกกระทบเท่ากับมุมสะท้อน เราขอกำหนดระบบแกนคู่ลำดับ (coordinate system) แบบใหม่ขึ้นเพื่อความสะดวก คือ แต่ละกำแพงจะมีระบบแกนคู่ลำดับเป็นของตัวเอง สำหรับแนวกำแพงของทั้งสองอาคารนั้น แนวแกน X จะหมายถึงแนวนอนและแนวแกน Y จะหมายถึงแนวตั้งและแกนของทั้งสองอาคารจะมีขนาดความยาวเท่ากัน จุด (0,0) ของทั้งสองอาคารจะอยู่ตรงกัน (มีระยะห่าง 10 เมตรพอดี), ขอบของหน้าต่างทุกบานของทั้งสองอาคารจะวางตัวในแนว X-Yนี้, แสงจะถูกสะท้อนได้ถ้าแสงตกกระทบกับพื้นที่ภายในหน้าต่าง และจะถูกดูดซับไว้ (ไม่สะท้อน) ที่ขอบของหน้าต่าง, ไม่มีพื้นที่ภายในของหน้าต่างคู่ใดๆ ในอาคารเดียวกันที่ซ้อนทับกัน, โคมไฟตั้งอยู่ที่ตำแหน่ ง(0,0) ของอาคาร B ซึ่งจะไม่เป็นขอบหรืออยู่ในภายในหน้าต่างบานหนึ่งบานใด
ข้อมูลนำเข้า
บรรทัดแรก รับจำนวนเต็มสองจำนวน n และ m (1 ≤ n, m ≤ 600) คั่นด้วยช่องว่าง ที่แสดงถึงจำนวนของหน้าต่างของอาคาร B และอาคาร C ตามลำดับ ต่อมาอีก n บรรทัด จะรับตำแหน่งของหน้าต่างแต่ละบานของอาคาร B โดยในบรรทัดที่ i+1 จะหมายถึงหน้าต่างบานที่ i ของอาคาร B ซึ่งประกอบด้วยจำนวนเต็ม 4 จำนวนคือ x1i, y1i, x2i, y2i คั่นด้วยช่องว่าง (1 ≤ x1i < x2i ≤ 1000; 1 ≤ y1i < y2i ≤ 1000) โดยตำแหน่งล่างซ้าย และ บนขวา ของหน้าต่างในหน่วยเมตรคือ (x1i,y1i) และ (x2i, y2i) ตามลำดับ ต่อมาอีก m บรรทัด จะรับตำแหน่งของหน้าต่างแต่ละบานของอาคาร C ในทำนองเดียวกัน

ข้อมูลส่งออก
บรรทัดแรก ให้แสดงจำนวนหน้าต่างของอาคาร B ที่มีแสงส่องถึง (โจทย์การันตีว่าจะมีอย่างน้อยหนึ่งหน้าต่างที่ถูกแสงส่องถึงเสมอ ซึ่งคือหน้าต่างของโนบิตะนั่นเอง) บรรทัดที่สอง ให้แสดงหมายเลขหน้าต่าง (เริ่มนับจาก 1) ทั้งหมดของอาคาร B ที่ถูกแสงส่องถึง ในลำดับเพิ่ม คั่นด้วยช่องว่าง
ตัวอย่าง
ข้อมูลนำเข้า
-1 2 1 4
-1 5 1 7
-3 8 -2 20
-1 1 1 2
-1 4 1 5
-1 7 1 10
ข้อมูลส่งออก
2
1 2

คำอธิบาย แสงจะเริ่มส่องจากตำแหน่ง (0,0) และเข้าไปในหน้าต่างบานแรกของอาคาร B เมื่อสะท้อนจากหน้าต่างบานแรกของอาคาร C ที่ตำแหน่ง (0,1.5) ในแกนคู่ลำดับของอาคาร C (แนวกำแพง C) และกลับไปที่อาคาร B ที่ตำแหน่ง (0,3) ของแนวกำแพง B
แสงจะเข้าไปหน้าต่างที่สองของ B ภายหลังจากการสะท้อน 3 ครั้งโดยการสะท้อนครั้งที่ 3 คือสะท้อนที่แนวกำแพง C ที่ตำแหน่ง (0,4.5) และกลับมาที่อาคาร B ที่ตำแหน่ง (0,6) และไม่มีแสงส่องไปถึงหน้าต่างบานที่ 3 ของอาคาร B, ในกรณีนี้หน้าต่างทั้งสามบานของอาคาร C ถูกแสงส่องถึงทั้งหมด

---

เจ้ากบน้อย (Frog)

หน่วยความจำ 128 MB

ในห้วยที่ยาวและตรงแห่งหนึ่ง มีก้อนหินจำนวน n ก้อนวางโผล่ขึ้นก่อนน้ำปริ่มๆ วางตัวเรียงเป็นแนวเส้นตรงยาวแนวหนึ่งเริ่มต้นจากบ่อน้ำพุ ระยะหว่างระหว่างก้อนหินแต่ละก้อนกับบ่อน้ำพุคือ p1 < p2 < … < pn ตามลำดับ เจ้ากบน้อยตัวหนึ่งที่นั่งอยู่บนหินก้อนหนึ่งต้องการฝึกกระโดด โดยแต่ละครั้งเจ้ากบน้อยต้องการกระโดดไปยังหินก้อนที่ k ที่ใกล้ที่สุดจากก้อนที่ตนอยู่ กล่าวคือ ถ้ากบน้อยอยู่บนก้อนหินที่ตำแหน่ง pi แล้วบน้อยจะกระโดดไปยังหินก้อนที่ pj ที่
ถ้า pj เป็นไปได้หลายค่า, กบน้อยจะเลือกโดดไปยังหินก้อนที่อยู่ใกล้กับบ่อน้ำพุมากที่สุด, สังเกตได้ว่าตำแหน่งที่กบจะนั่งอยู่เมื่อกระโดดต่อเนื่อง m ครั้งนั้น ขึ้นอยู่กับตำแหน่งของหินก้อนแรกที่เจ้ากบน้อยนั่งอยู่นั่นเอง
ข้อมูลนำเข้า
บรรทัดแรก รับจำนวนเต็มสามจำนวน n, k และ m (1 ≤ k < n ≤ 1,000,000; 1 ≤ m ≤ 1018) คั่นด้วยช่องว่าง ที่แสดงถึงจำนวนของก้อนหินทั้งหมด, k ที่ใกล้ที่สุดที่ต้องการกระโดด, และจำนวนครั้งในการกระโดดต่อเนื่อง
บรรทัดที่สอง รับจำนวนเต็มทั้งหมด n จำนวนที่แสดงระยะของก้อนหินแต่ละก้อนที่ห่างจากบ่อน้ำพุ โดย pj ใด (1 ≤ p1 < p2 < … < pn ≤ 1018) คั่นด้วยช่องว่าง
ข้อมูลส่งออก
ให้แสดงคำตอบด้วยข้อมูลหนึ่งบรรทัด ที่ประกอบด้วยจำนวนเต็ม n จำนวน r1, r2, …, rn คั่นด้วยช่องว่าง โดยแต่ละค่าเป็นค่าในช่วง [1,n] เมื่อ ri แสดงถึงก้อนหินที่เจ้ากบน้อยอยู่ภายหลังจากการกระโดดต่อเนื่อง m ครั้งเมื่อเริ่มต้นเจ้าบน้อยนั่งอยู่บนหินก้อนที่ i
ตัวอย่าง
ข้อมูลนำเข้า
5 2 4
1 2 4 7 10

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

รูป(พิจารณาจากเว็บหลัก)แสดงวิธีการกระโดดหนึ่งครั้ง จากหินก้อนต่างๆ ไปยังก้อนหินที่ 2 ที่ใกล้ที่สุด

---

POI 17th - Stage III - Day 1

The Minima Game http://theory.cpe.ku.ac.th/wiki/images/POI17_III_MinimaGame_Th.pdf

Lamp http://theory.cpe.ku.ac.th/wiki/images/POI17_III_Lamp.pdf

Frog http://theory.cpe.ku.ac.th/wiki/images/POI17_III_Frog_Th.pdf

---