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

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

• บรรทัดที่ 1: จำนวนเต็ม N และ M
• บรรทัดที่ 2..1+N: บรรทัดที่ (i+1) ระบุจำนวนเต็มสองจำนวน s_i และ t_i (0 <= s_i, t_i <= M) ที่ระบุตำแหน่งเริ่มต้นและตำแหน่งปลายทางของวัวตัวที่ i

ตัวอย่างข้อมูลนำเข้า

2 10
0 9
6 5

รายละเอียดตัวอย่าง

มีวัวสองตัวรออยู่ที่รั้วความยาว 10 วัวตัวแรกต้องการจะไปจากตำแหน่ง 0 (ที่เบสซี่เริ่ม) ไปยังตำแหน่ง 9 วัวตัวที่สองต้องการไปจากตำแหน่ง 6 ไปตำแหน่ง 5

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

มีหนึ่งบรรทัด ระบุระยะทางที่สั้นที่สุดที่เบสซี่ต้องใช้ สังเกตว่าคำตอบอาจจะไม่สามารถเก็บในจำนวนเต็ม 32 บิตได้

ตัวอย่างข้อมูลส่งออก

12

คำอธิบาย

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

Problem 3: Route Designing [Yan Gu, 2013]

Source: [3]

หลังจากได้หนีออกมาจากฟาร์ม เบสซี่ได้ตกลงว่าจะตั้งบริษัทท่องเที่ยวที่แม่น้ำ Amoozon ที่แม่น้ำดังกล่าว มีสถานที่ท่องเที่ยวอยู่ทั้งสองฝากของแม่น้ำ โดยทุกสถานที่ท่องเที่ยวจะมีค่าความน่าสนใจระบุไว้เป็นจำนวนเต็ม

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

อย่างไรก็ตาม เบสซี่อาจจะเปิดทัวร์หลาย ๆ กลุ่มพร้อม ๆ กัน ดังนั้น จึงจำเป็นว่าไม่มีเส้นทางใด ๆ ที่อยู่ในทัวร์นั้นตัดกัน เส้นทางที่เชื่อม a <-> x และเส้นทางที่เชื่อม b <-> y จะตัดกันก็ต่อเมื่อ (a < b และ y < x) หรือ (b < a และ x < y) หรือ (a = b และ x = y)

ช่วยเบสซี่หาทัวร์ที่ดีที่สุดสำหรับบริษัทท่องเที่ยวของเธอด้วย เบสซี่จะเริ่มและเลิกทัวร์ที่ฝั่งใดของแม่น้ำ Amoozon ก็ได้

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

• บรรทัด 1: ระบุจำนวนเต็มสามจำนวน N (1 <= N <= 40,000), M (1 <= M <= 40,000), และ R (0 <= R <= 100,000) แทนจำนวนสถานที่ท่องเที่ยวในด้านซ้ายของฝั่งแม่น้ำ, จำนวนสถานที่ท่องเที่ยวฝั่งขวาของแม่น้ำ, และจำนวนเส้นทาง

• บรรทัด 2..N+1: บรรทัดที่ (i+1) ระบุจำนวนเต็มหนึ่งจำนวน L_i (0 <= L_i <= 40,000) แทนค่าความน่าสนใจของสถานที่ท่องเที่ยวที่ i ในด้านฝั่งซ้ายของแม่น้ำ

• บรรทัด N+2..N+M+1: บรรทัดที่ (i+N+1) ระบุจำนวนเต็มหนึ่งจำนวน R_i (0 <= R_i <= 40,000) แทนค่าความน่าสนใจของสถานที่ท่องเที่ยวที่ i ในด้านฝั่งขวาของแม่น้ำ

• บรรทัด N+M+2..N+M+R+1: แต่ละบรรทัดระบุจำนวนเต็มสองจำนวน I (1 <= I <= N) และ J (1 <= J <= M) ระบุว่ามีเส้นทาง (สองทิศทาง) ระหว่างสถานที่ท่องเที่ยวที่ I ที่ฝั่งซ้ายของแม่น้ำ และสถานที่ท่องเที่ยวที่ J ที่ฝั่งขวาของแม่น้ำ

ตัวอย่าง

3 2 4
1
1
5
2
2
1 1
2 1
3 1
2 2

รายละเอียด

มีสถานที่ท่องเที่ยวฝั่งซ้ายของแม่น้ำสามที่ โดยมีค่าความน่าสนใจเท่ากับ 1 1 และ 5, มีสถานที่ท่องเที่ยวที่ฝั่งขวาของแม่น้ำ สองที่ ที่ีมีค่าความน่าสนใจเท่ากับ 2 และ 2 มีเส้นทาง 4 เส้นเชื่อมระหว่างสถานที่ท่องเที่ยวเหล่านี้

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

มีหนึ่งบรรทัด ระบุค่าความน่าสนใจสูงที่สุดที่ทัวร์สามารถเป็นไปได้

ตัวอย่าง

8

รายละเอียด

ทัวร์ที่ดีที่สุด เริ่มจากสถานที่ท่องเที่ยวที่ 1 ฝั่งซ้าย ไปสถานที่ท่องเที่ยวที่ 1 ฝั่งขวา และไปสิ้นสุดที่สถานที่ท่องเที่ยว 3 ที่ฝั่งซ้าย โดยมีค่าความน่าสนใจคือ 1, 2, และ 5 ทำให้ได้ค่ารวมเท่ากับ 8