Usaco2013

โจทย์แปล USACO 2012-2013

USACO 2013 January Contest, Gold

Problem 1: Cow Lineup [Brian Dean and Daniel Dara, 2012]

Source: ต้นฉบับและหน้าเว็บสำหรับส่ง

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

ชจ.คิดว่าแถวของวัวจะดูน่าตื่นตาตื่นใจถ้าจะมีช่วงในแถวที่ต่อเนื่องกันที่มีวัวที่มีหมายเลขพันธุ์เดียวกัน ในการสร้างช่วงดังกล่าว ชจ.จะเลือกหมายเลขพันธุ์ของวัวไม่เกิน K หมายเลข และนำวัวที่มีหมายเลขพันธุ์ดังกล่าวออกจากแถวทั้งหมด ช่วย ชจ. หาว่าช่วงในแถวที่ยาวที่สุดที่มีวัวสายพันธุ์เดียวกันในแถวที่เขาสามารถสร้างได้ โดยดำเนินการตามวิธีข้างต้น

Problem 2: Island Travels [Neal Wu, 2007]

Source: ต้นฉบับและหน้าเว็บสำหรับส่ง

ชาวนาจอห์นได้พาเหล่าวัวไปท่องเที่ยวกลางทะเล! บรรดาวัวไปฮาเฮอยู่บนเกาะ จำนวน N เกาะ (1 <= N <= 15) ที่อยู่บน R x C กริด (1 <= R, C <= 50) เกาะแต่ละเกาะจะเป็นกลุ่มของช่องบนกริดที่ติดกันที่ครอบคลุมช่องต่าง ๆ มากที่สุด (maximal connected group of squares) ที่ถูกระบุเป็น 'X' โดยที่ 'X' สองอันจะติดกัน ถ้ามีการใช้ขอบร่วมกัน (นั่นคือ 'X' สองอันที่ใช้มุมร่วมกันจะไม่จำเป็นว่าจะต้องอยู่บนเกาะเดียวกัน)

เบซซี่นั้นมาสายดังนั้นเธอจึงจะมาทางเฮลิคอปเตอร์กับ ชจ. ดังนั้นเธอสามารถจะไปลงที่เกาะใดก็ได้ที่เธอเลือก เธอต้องการที่จะไปเยี่ยมเพื่อนของเธอทุกตัวอย่างน้อยหนึ่งครั้ง เธอเลยจะเดินทางไปตามเกาะต่าง ๆ จนกระทั่งเธอได้ไปแวะที่ทุก ๆ เกาะอย่างน้อยเกาะละหนึ่งครั้ง

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

ให้หาระยะทางน้อยที่สุดที่เบซซี่ต้องว่ายน้ำเพื่อที่จะไปเยี่ยมเยือนทุกเกาะ (ระยะทางที่เธอต้องว่ายจะเท่ากับจำนวนครั้งที่แตกต่างกันที่เธอต้องอยู่บนช่องที่ระบุว่า 'S') เบซซี่รู้ว่าการเยี่ยมเยือนทุกเกาะนี้เป็นไปได้

Problem 3: Seating [Travis Hance, 2012]

Source: ต้นฉบับและหน้าเว็บสำหรับส่ง

เพื่อหารายได้พิเศษ เหล่าวัวได้เปิดร้านอาหารในโรงนาที่เน้นการขายมิลค์เชค ร้านอาหารมีที่นั่ง N ที่ (1 <= N <= 500,000) เรียงเป็นแถว เมื่อเริ่มต้น ที่นั่งเหล่านี้ว่าง

ตลอดวัน จะมีเหตุการณ์เกิดขึ้น M ครั้งตามลำดับ (1 <= M <= 300,000) เหตุการณ์ที่เกิดขึ้ันมีได้สองแบบดังนี้:

1. กลุ่มลูกค้าจำนวน p มาถึง (1 <= p <= N) เบซซี่ต้องการจัดที่นั่งให้กับลูกค้ากลุ่มนี้ที่ที่นั่ง p ที่ ที่ว่างอยู่ที่อยู่ติดกัน ถ้าเป็นไปได้ เธอจะจัดที่นั่งให้ในตำแหน่งที่มีหมายเลขน้อยที่สุดในรายการของที่นั่ง ถ้าเป็นไปไม่ได้ ลูกค้ากลุ่มนี้ก็จะออกจากร้านไปโดยไม่ซื้ออะไร

2. ให้ขอบเขต [a, b] (1 <= a <= b <= N) และทุกคนในขอบเขตดังกล่าวออกจากร้านไป

ช่วยเบซซี่หาจำนวนกลุ่มลูกค้าที่ออกจากร้านไปโดยไม่ซื้ออะไร

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

USACO 2013 March Contest, Gold

Problem 1: The Cow Run [Chris Tzamos, 2006]

Source: ต้นฉบับโจทย์และหน้าเว็บสำหรับส่ง

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

โชคดีที่เหล่าวัวนั้นอยู่ที่ตำแหน่งที่แตกต่างกันบนถนนเส้นตรงด้านนอกฟาร์ม ชจ.ทราบตำแหน่ง P_i ของวัวตัวที่ i (-500,000 <= P_i <= 500,000; P_i != 0) โดยคิดสัมพันธ์กับตำแหน่งของประตูที่อยู่ที่ตำแหน่ง 0 ซึ่งจะเป็นตำแหน่งที่ ชจ. เริ่มออกทำการ

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

Problem 2: Hill Walk [Travis Hance, 2013]

Source: ต้นฉบับโจทย์และหน้าเว็บสำหรับส่ง

มีเนินเขา N แห่ง (1 <= N <= 100,000) แต่ละเนินเขามีลักษณะเป็นส่วนของเส้นตรง (x1, y1) ไปยัง (x2, y2) โดยที่ x1 < x2 และ y1 < y2 ส่วนของเส้นตรงเหล่านี้ไม่ตัดกันหรือสัมผัสกัน แม้จะเป็นที่จุดปลาย (นั่นคือที่จุดปลายของส่วนของเส้นตรงก็ไม่ซ้ำกัน ไม่อยู่บนส่วนของเส้นตรงอื่น) และยิ่งกว่านั้น ที่เนินเขาแรก (x1, y1) = (0,0)

วัวเบซซี่เริ่มที่ (0,0) ที่เนินเขาแรก เมื่อใดก็ตามที่เบซซี่อยู่ที่เนินเขา เธอจะปีนมันไปเรื่อย ๆ จนกระทั่งถึงปลาย จากนั้นเธอก็จะกระโดดจากเนินนั้น ถ้าเธอร่วงไปบนเนินเขาอื่น เธอก็จะเดินต่อไป ถ้าไม่เช่นนั้นเธอก็จะร่วงหล่นไปเรื่อย ๆ จนถึงจุดที่ y = -infinity สำหรับเนินเขา (x1, y1) -> (x2, y2) เราจะนับว่ามีจุด (x1, y1) แต่ไม่รวมถึงจุด (x2, y2) ดังนั้นเบซซี่จะถือว่าร่วงไปบนเนินเขานี้ถ้าเธอร่วงจากจุดด้านบนที่มี x = x1 แต่เราจะไม่นับว่าเธอร่วงบนเนินเขานี้ถ้าเธอร่วงจากจุดด้านบนที่ x = x2

ให้นับจำนวนเนินเขาที่เบซซี่สัมผัสตลอดการเดินทางของเธอ

Problem 3: Necklace [Yan Gu, 2013]

Source: ต้นฉบับโจทย์และหน้าเว็บสำหรับส่ง

วัวเบซซี่ได้เรียงก้อนหิน N ก้อนเป็นสาย (หินแต่ละก้อนมีตัวอักขระอยู่หนึ่งตัว) เธอต้องการสร้างสร้อยคอแฟชั่นนำสมัยจากหินเหล่านี้

เนื่องจากเบซซี่เป็นวัวที่หวงข้าวของมาก เธอจึงไม่ต้องการจะแบ่งสร้อยคอนี้กับวัวตัวอื่น ๆ วัวตัวอื่น ๆ นั้นมีชื่อที่เป็นสตริงความยาว M ตัวอักษร และเบซซี่ต้องการแน่ใจว่าสตริงความยาว M ตัวอักษรนี้ จะไม่ไปปรากฏเป็นสตริงย่อยที่ต่อเนื่องกันภายในสตริงที่เธอจะสร้างเป็นสร้อยคอนี้ (เพราะว่าวัวตัวอื่นอาจจะพลาดมาหยิบเอาสร้อยของเธอไปได้) เบซซี่ต้องการจะเอาหินบางก้อนออกจากสร้อยคอของเธอเพื่อไม่ให้มีชื่อของวัวตัวอื่นบนสร้อยคอนี้ ช่วยเบซซี่หาจำนวนหินที่น้อยที่สุดที่เธอต้องเอาออกจากสร้อยคอด้วย

หมายเหตุ: ไม่ต้องคิดกรณีที่สตริงย่อยเริ่มที่ปลายของของสร้อยแล้วไปใช้หินที่อีกปลายด้านหนึ่งของสร้อย เช่น เราจะไม่นับว่า ba อยู่บนสร้อยที่สร้างจากสตริง aaab