Usaco2013

USACO 2013 February Contest, Gold

Problem 1: Partitioning the Farm [Brian Dean, 2013]

Source: [1]

ฟาร์มของชาวนาจอห์นแบ่งเป็นช่องตารางกริดขนาด N x N (2 <= N <= 15) ตอนนี้ที่ฟาร์มมีแค่รั้วล้อมภายนอกฟาร์ม แต่วัวสามารถเดินไปมาระหว่างช่องในฟาร์มได้

ชาวนาจอห์นตัดสินใจว่าจะสร้างรั้วเพื่อแบ่งวัวออกเป็นกลุ่ม ๆ เนื่องจากกฎหมายการแบ่งโซน รั้วที่สร้างจะต้องเป็นรั้วในแนวตั้งหรือแนวนอน และมีความยาวจากขอบฟาร์มด้านหนึ่งไปยังขอบอีกด้านหนึ่ง และรั้วจะไม่สามารถสร้างผ่านช่องของตารางกริด ชาวนาจอห์นมีเงินมากพอที่จะสร้างรั้วได้แค่ K รั้วเท่านั้น (1 <= K <= 2N-2)

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

ข้อมูลนำเข้า

• บรรทัด 1: จำนวนเต็มสองจำนวน N และ K
• บรรทัด 2..1+N: แต่ละบรรทัดมีจำนวนเต็ม N จำนวน แทนจำนวนวัวในแต่ละช่องในแถวหนึ่ง ๆ ของฟาร์ม (จำนวนวัวจะมีค่าไม่น้อยกว่า 0 และไม่เกิน 1 000 ตัว ในแต่ละช่อง

ตัวอย่าง input

3 2
1 1 2
1 1 2
2 2 4

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

มีบรรทัดเดียว เป็นขนาดของกลุ่มวัวที่ใหญ่ที่สุด ที่น้อยที่สุดที่เป็นไปได้

ตัวอย่าง

4

คำอธิบาย

ชาวนาจอห์นควรจะสร้างรั้วระหว่างคอลัมน์ 2 และ 3, และระหว่างแถวที่ 2 และ 3 ซึ่งจะทำให้มีกลุ่มวัว 4 กลุ่ม กลุ่มละ 4 ตัว

Problem 2: Taxi [Mark Gordon, Richard Peng, 2013]

Source: [2]

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

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

เบสซี่เริ่มที่จะซ้ายสุดของรั้ว นั่นคือที่ตำแหน่ง 0 และจะต้องจบการเดินทางที่ตำแหน่งขวาสุดของรั้ว นั้่นคือตำแหน่ง M