Usaco2012

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

USACO 2011 November, Gold

Problem 1: Above the Median [Brian Dean]

Source: [1]

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

งานดังกล่าวมีเงื่อนไขแสนประหลาดในการส่งภาพถ่าย: ภาพถ่ายจะใช้ส่งประกวดได้เมื่อเป็นภาพถ่ายที่แสดงกลุ่มของวัวที่ความสูงมัธยฐานไม่น้อยกว่าค่าขอบเขต X ค่าหนึ่ง (1 <= X <= 1,000,000,000)

สำหรับโจทย์นี้ เรานิยามมัธยฐานของอาร์เรย A[0...K] ให้เป็น A[ceiling(K/2)] หลังจากที่ A ถูกจัดเรียงแล้ว เมื่อ ceiling(K/2) ให้ค่า K/2 ปัดขึ้นไปยังจำนวนเต็มที่ใกล้ที่สุด (หรือ K/2 เองถ้า K/2 นั้นเป็นจำนวนเต็มอยู่แล้ว) ตัวอย่างเช่น มัธยฐานของ {7,3,2,6} คือ 6 และ มัธยฐานของ {5,4,8} คือ 5

ช่วย ชจ. นับจำนวนลำดับย่อยที่ต่อเนื่องกันของวัวที่สามารถถ่ายเป็นรูปที่สามารถส่งประกวดได้

Problem 2: Binary Sudoku [Brian Dean]

Source: [2]

วัวของชาวนาจอห์นชอบเล่นเวอร์ชันหนึ่งของเกม "Sudoku" เวอร์ชันนี้มีตารางขนาด 9 x 9 ที่ประกอบไปด้วยกริดย่อยขนาด 3 x 3 เหมือน Sudoku ปกติ แต่ในเวอร์ชันของวัวจะเป็นเลขฐานสอง:

000 000 000 
001 000 100 
000 000 000 

000 110 000 
000 111 000 
000 000 000 

000 000 000 
000 000 000 
000 000 000 

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

000 000 000 
001 000 100 
001 000 100 

000 110 000 
000 110 000 
000 000 000 

000 000 000 
000 000 000 
000 000 000 

ให้สถานะตั้งต้นของ Sudoku ฐานสอน ให้หาจำนวนครั้งที่น้อยที่สุดที่ต้องสลับบิตเพื่อแก้ตาราง Sudoku นี้

Problem 3: Cow Steeplechase [Brian Dean]

Source: [3]

ชาวนาจอห์นมีไอเดียชั้นยอดสำหรับกีฬาที่ดึงดูดใจผู้ชม: การแข่งขี่วัวข้ามสิ่งกีดขวาง (Cow Steeplechase) อย่างที่หลาย ๆ คนทราบ การแข่งขี่ม้าข้ามสิ่งกีดขวาง (steeplechase) นั้นจะมีกลุ่มของม้าที่วิ่งไปมาบนสนามแข่งที่มีสิ่งกีดขวางที่ม้าจะต้องกระโดดข้ามให้ได้ ชจ.คิดว่าการแข่งขันรูปแบบเดียวกันจะใช้ได้สำหรับวัวที่ผ่านการฝึกมาอย่างดีแล้ว เมื่อสิ่งกีดขวางนั้นไม่สูงจนเกินไป

เพื่อที่จะออกแบบสนามแข่ง ชจ.ได้ตระเตรียมวาดแผนผังที่แสดงสิ่งกีดขวางที่เขาอาจจะสร้างได้ทั้งหมด N ชิ้น (1 <= N <= 250) แต่ละชิ้นแสดงเป็นส่วนของเส้นตรงในระนามสองมิติ ขนานกับแกน x หรือแกน y สิ่งกีดขวางที่ i จะมีจุดปลายสองจุดที่แตกต่างกัน (X1_i, Y1_i) และ (X2_i, Y2_i) (1 <= X1_i, Y1_i, X2_i, Y2_i <= 1,000,000,000) ตัวอย่างแสดงดังด้านล่าง:

ชจ.ต้องการที่สร้างสิ่งกีดขวางนี้ให้มากที่สุด แต่ต้องไม่ให้สิ่งกีดขวางคู่ใด ๆ ตัดกัน (intersect) จากแผนผังด้านบน ชจ. สามารถสร้างสิ่งกีดขวางได้ 7 ชิ้น:

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

ช่วย ชจ. หาว่าจำนวนสิ่งกีดขวางที่มากที่สุดที่เขาสามารถสร้างได้ เป็นเท่าใด

USACO 2011 December, Gold

Problem 1: Cow Photography [Brian Dean, 2011]

Source: usaco

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

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

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

Problem 2: Simplifying the Farm [Nathan Pinsker, 2011]

Source: usaco

ชาวนาจอห์นได้ไปเรียนวิชาอัลกอริทึมภาคค่ำที่มหาวิทยาลัยแถวฟาร์มของเขา เขาเพิ่งได้เรียนเกี่ยวกับ minimum spanning tree ซึ่งทำให้เขาได้ตระหนักว่า การออกแบบฟาร์มของเขานั้นมันไม่มีประสิทธิภาพอย่างที่ควรจะเป็น เขาต้องการจะทำให้แผนผัง (layout) ของฟาร์มง่ายขึ้น

ฟาร์มปัจจุบันนั้นมีลักษณะเป็นกราฟ ที่มีจุดยอดแทนสนาม และเส้นเชื่อม แทนทางเดินระหว่างสนามเหล่านี้ ทางเดินทุกเส้นมีความยาวระบุอยู่ ชาวนาจอห์นสังเกตว่าสำหรับความยาวค่าใด ๆ จะมีทางเดินไม่เกินสามทางที่มีค่าความยาวนี้ ชจ.ต้องการลบทางเดินในฟาร์มทิ้งเพื่อให้แผนผังกลายเป็นต้นไม้ (tree) นั่นคือ สำหรับสนามคู่ใด ๆ จะมีเส้นทางเดินเพียงเส้นทางเดียวเท่านั้น กล่าวคือ ชาวนาจอห์นต้องการให้ฟาร์มของเขาเป็น minimum spanning tree (ต้นไม้ที่มีผลรวมของความยาวเส้นเชื่อมน้อยที่สุด)

ช่วยชาวนาจอห์นหาความยาวของ minimum spanning tree พร้อมกับคำนวณว่าจำนวนของ minimum spanning tree ที่เป็นไปได้ทั้งหมด มีกี่แบบ

Problem 3: Grass Planting [Travis Hance, 2011]

Source: usaco

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

แต่ละขั้น มีเหตุการณ์เกิดขึ้นได้สองแบบ:

• ชจ. จะเลือกทุ่งหญ้าสองแห่ง จากนั้นจะปลูกหญ้าหนึ่งผืนในถนนทุก ๆ เส้นระหว่างทุ่งหญ้าทั้งสองนั้น

• เบซซีจะเลือกถนนมาหนึ่งเส้น และถาม ชจ. ว่ามีหญ้ากี่ผืนในถนนเส้นนั้น

ชาวนาจอห์นความจำไม่ค่อยจะดี — ช่วยเขาตอบคำถามของเบซซี่ด้วย!

USACO 2012 Jan, Gold

Problem 1: Video Game Combos [Neal Wu, 2012]

Source: USACO

เบซซี่กำลังเล่นวิดีโอเกม ในเกมนี้ ตัวอักษร ‘A’, ‘B’, และ ‘C’ เป็นปุ่มที่กดได้เท่านั้น เบซซี่สามารถกดปุ่มเหล่านี้ในลำดับใด ๆ ก็ได้ที่เธอชอบ อย่างไรก็ตาม จะมีรูปแบบคอมโบที่เป็นไปได้แตกต่งกันทั้งสิ้น N รูปแบบ (1 <= N <= 20) คอมโบที่ i จะแสดงด้วยสตริง S_i ที่มีความยาวระหว่าง 1 ถึง 15 ที่ประกอบด้วยตัวอักษร ‘A’, ‘B’ หรือ ‘C’

เมื่อใดที่เบซซี่กดปุ่มแล้วได้รูปแบบตรงกับคอมโบ เธอจะได้รับคะแนนหนึ่งแต้มสำหรับคอมโบนั้น คอมโบสามารถซ้อนทับกันได้ หรือกระทั่งกดเสร็จได้พร้อมกัน ยกตัวอย่างเช่น ถ้า N = 3 และคอมโบที่เป็นไปได้คือ “ABA”, “CB”, และ “ABACB” ถ้าเบซซี่กด “ABACB” เธอจะได้คะแนน 3 แต้ม เบซซี่สามารถได้คะแนนจากบางคอมโบได้มากกว่าหนึ่งครั้ง

แน่นอนที่เบซซี่ต้องการจะได้คะแนนให้ได้เร็วที่สุดเท่าที่จะทำได้ ถ้าเธอกดปุ่ม K ปุ่ม (1 <= K <= 1,000) คะแนนมากที่สุดที่เธอทำได้เป็นเท่าใด?

Problem 2: Cow Run [Mark Gordon, 2011]

Source: USACO

ชาวนาจอห์นและเบซซี่ได้คิดค้นเกมสำหรับออกกำลังกายแบบใหม่สำหรับวัว เหล่าวัวจะวิ่งบนลู่วิ่งวงกลมความยาว M (2 <= M <= 1,000,000,000) โดยเริ่มจากจุดเริ่มต้นเดียวกัน เกมจะดำเนินไป N รอบ (1 <= N <= 14) และใช้สำรับไพ่ขนาด 8N ใบ ที่แต่ละใบมีหมายเลข X_i (0 <= X_i < M) เขียนอยู่

ในแต่ละรอบ ชจ. จะแยกไพ่ด้านบนสุด 8 ใบไปยังกองไพ่ใหม่ จากนั้นจะเลือกไพ่ 4 ใบด้านบน หรือ 4 ใบด้านล่างให้เบซซี่นำไปเล่น เบซซี่จะเลือกไพ่ด้านบน 2 ใบ หรือด้านล่าง 2 ใบจากไพ่ 4 ใบที่ ชจ. เลือก หลังจากนั้น ชจ. จะอ่านจำนวน X_top บนไพ่ใบบน และเหล่าวัวจะวิ่งไปเป็นระยะทาง R*X_top, โดยที่ R คือระยะทางที่วัววิ่งมาแล้ว. เบซซี่ก็จะอ่านจำนวน X_bottom ที่อยู่ที่ไพ่ใบล่าง และเหล่าวัวก็จะวิ่งไปอีกเป็นระยะทาง X_bottom

ชจ. เป็นห่วงว่าหลังจากการออกกำลังกาย เหล่าวัวจะเหนื่อยเกินไปที่จะกลับไปที่จุดเริ่มต้นของลู่วิ่งถ้าพวกมันไปหยุดที่จุดที่ห่างไกลเกินไป เขาเชื่อว่าถ้าวัวไปหยุดที่ระยะทางมากกว่า K (0 <= K <= floor(M/2)) จากจุดเริ่มต้น พวกมันจะไม่สามารถกลับบ้านได้

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

Problem 3: Bovine Alliance [Mark Gordon, 2011]

Source: USACO

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

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

USACO 2012 Feb, Gold

Problem 1: Cow Coupons [Neal Wu and Mark Gordon, 2012]

Source: USACO

ชาวนาจอห์นต้องการวัวเพิ่ม! มีวัว N ตัวที่พร้อมจะขาย (1 <= N <= 50,000), และ ชจ. จะต้องใช้เงินไม่เกิน M หน่วย (1 <= M <= 10^14) วัวตัวที่ i มีราคา P_i หน่วย (1 <= P_i <= 10^9) แต่ ชจ. มีคูปอง K ใบ (1 <= K <= N), เมื่อใช้คูปองแล้ว วัวตัวที่ i จะมีราคาเหลือ C_i แทนที่จะเป็น P_i (1 <= C_i <= P_i) ชจ สามารถใช้คูปองหนึ่งใบกับวัวหนึ่งตัวเท่านั้น

ชจ.จะสามารถซื้อวัวมาได้ทั้งหมดมากที่สุดกี่ตัว

Problem 2: Symmetry [Brian Dean, 2012]

Source: USACO

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

ช่วย ชจ. หาคำตอบนี้ด้วย

Problem 3: Nearby Cows [Neal Wu and Eric Price, 2011]

Source: USACO

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

กล่าวคือ ฟาร์มของชจ. มีสนามรวมทั้งสิ้น N สนาม (1 <= N <= 100,000) ที่บางคู่ของสนามจะเชื่อมต่อกันด้วยทางเดินที่เดินได้สองทิศทาง (จำนวน N-1 เส้น) ชจ. ได้ออกแบบฟาร์มโดยรับประกันว่าระหว่างสองสนาม i และ j ใด ๆ จะมีเส้นทางที่ประกอบด้วยลำดับของทางเดินเชื่อมระหว่าง i และ j หนึ่งเส้นทาง สนาม i เป็นบ้านของวัวจำนวน C(i) ตัวแต่บางครั้งวัวก็อาจจะเดินไปยังสนามอื่น ๆ โดยเดินผ่านทางเดินจำนวน K เส้น (1 <= K <= 20)

ชจ.ต้องการปลูกหญ้าที่สนามที่ i ให้มากพอที่จะรองรับจำนวนวัวที่มากที่สุด M(i) ที่สามารถเดินมาในสนามนี้ได้ ให้โครงสร้างของสนามของชจ. และค่า C(i) ของทุก ๆ สนาม i, ช่วย ชจ. คำนวณค่า M(i) สำหรับทุกสนาม i ด้วย

USACO 2012 Mar, Gold

Problem 1: Large Banner [Nathan Pinsker, 2010]

Source: USACO

เบซซี่กลับมาจากการท่องเที่ยวอันยาวนานที่ Isle of Guernsey ชาวนาจอห์นต้องการจะขึ้นป้าย "ยินดีต้อนรับกลับบ้าน" ให้กับเธอ สนามของชาวนาจอห์นมีขนาดเป็นจำนวนเต็ม M x N (1 <= M, N <= 100,000) และเขาได้ปักเสาไว้ที่ทุก ๆ จุดในสนามที่มีพิกัดเป็นจำนวนเต็ม (ถ้าเรากำหนดพิกัดให้กับสนามโดยที่มุมล่างขวาคือจุด (0,0) และ มุมบนซ้ายคือจุด (M,N)) จากบรรดาจุด (M+1)*(N+1) จุดเหล่านี้ ชาวนาจอห์นต้องเลือกจุดสองจุดเพื่อให้เป็นจุดปลายของป้ายประกาศ

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

Problem 2: Haybale Restacking [Brian Dean, 2012]

Source: USACO

ชาวนาจอห์นเพิ่งจะสั่งหญ้าแห้งมาหลายห่อ เขาต้องการจะจัดวางหญ้าแห้งเหล่านี้เป็นกอง จำนวน N กอง (1 <= N <= 100,000) เรียงตัวเป็นวงกลม โดยที่กองที่ i จะมีหญ้าแห้งจำนวน B_i ห่อ อย่างไรก็ตาม คนขับรถที่นำหญ้ามาส่งนั้นไม่ได้ฟังที่ชาวนาจอห์นสั่งให้ดี เขาเลยทำแค่วางหญ้าแห้งเป็นกองจำนวน N กอง เรียงเป็นวงกลมเท่านั้น หลังจากที่หญ้ามาส่งเรียบร้อย ชาวนาจอห์นได้สังเกตว่า กองที่ i มีหญ้าแห้งจำนวน A_i ห่อ แน่นอนว่าผลรวมของค่า A_i ทั้งหมดเท่ากับผลรวมของ B_i ทั้งหมด

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

Problem 3: Cows in a Skyscraper [Mark Gordon, Neal Wu, Fatih Gelgi, 2012]

Source: USACO

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

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

USACO Open 2012: Gold

Problem 1. Tied Down

Source: [4]

โจทย์โดย: Brian Dean, 2012

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

มีรูปตัวอย่างดูได้จากโจทยภาษาอังกฤษตามลิงก์นี้: [5]

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

พิกัด (x,y) ทั้งหมด (ตำแหน่งเสา ตำแหน่ง Bessie และจุดปลายของส่วนของเส้นตรง) อยู่ในขอบเขต 0..10,000 เสาทุก ๆ ต้นมีพิกัด x เท่ากัน และ bx จะมีค่ามากกว่าค่าเหล่านี้

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

• บรรทัด 1: จำนวนเต็มสี่จำนวน N, M, bx, by
• บรรทัด 2..1+N: บรรทัดที่ i+1 มีจำนวนเต็มสองจำนวน ระบุพิกัด x และ y ของเสาที่ i
• บรรทัด 2+N..2+N+M: แต่ละบรรทัดระบุตำแหน่งของจุดบนเส้นเชือก เรียงตามลำดับ จุดแรกและจุดสุดท้ายจะเท่ากับตำแหน่งของ Bessie (นั่นคือเท่ากับ bx, by)

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

2 10 6 1 
2 3 
2 1 
6 1 
2 4 
1 1 
2 0 
3 1 
1 3 
5 4 
3 0 
0 1 
3 2 
6 1

คำอธิบายตัวอย่าง: มีเสาสองเสาที่ตำแหน่ง (2,3) และ (2,1) Bessie อยู่ที่ตำแหน่ง (6,1) เชือกเริ่มจากจุด (6,1), ไปยัง (2,4) ไปยัง (1,1) และต่อไปจนสิ้นสุดที่ (6,1) ลักษณะของเชือกดูได้จากรูปประกอบ

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

• บรรทัด 1: จำนวนเสาที่น้อยที่สุดที่ต้องตัดทิ้ง เพื่อให้ Bessie หนีไปได้โดยวิ่งไปทางขวา

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

1

คำอธิบายตัวอย่าง: ตัดเสาที่ 1 หรือเสาที่ 2 ออก จะทำให้ Bessie สามารถหนีได้

Problem 2. Bookshelf

Source: [6]

โจทย์โดย: Neal Wu / Traditional, 2012

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

หนังสือเล่มที่ i มีความหนา W(i) และสูง H(i) ในการนำหนังสือใส่ชั้นนั้นจะต้องใล่ไปตามลำดับ ยกตัวอย่างเช่น ชั้นแรกจะต้องมีหนังสือเล่มที่ 1...k สำหรับบางค่า k ชั้นที่สองจะเริ่มที่หนังสือเล่มที่ k+1 ไปตามลำดับ ชั้นแต่ละชั้นจะมีความกว้างเท่ากับความหนารวมของหนังสือ ซึ่งจะต้องไม่เกิน L (1 <= L <= 1,000,000,000) ความสูงของชั้นหนึ่ง ๆ จะเท่ากับความสูงที่มากที่สุดของหนังสือในชั้นนั้น ความสูงรวมของชั้นหนังสือทุกชั้นจะเท่ากับผลรวมของความสูงของแต่ละชั้นใส่หนังสือ (เนื่องจากชั้นจะวางซ้อน ๆ กันไป) ให้คุณช่วยชาวนาจอห์นหาความสูงที่น้อยที่สุดของชุดของชั้นหนังสือที่เขาจะสร้าง

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

• บรรทัด 1: ระบุจำนวนเต็ม N และ L
• บรรทัด 2..1+N: บรรทัดที่ i+1 ระบุ H(i) และ W(i) (1 <= H(i) <= 1,000,000; 1 <= W(i) <= L)

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

5 10 
5 7 
9 2 
8 5 
13 2 
3 8 

คำอธิบายข้อมูลนำเข้า: มีหนังสือ 5 เล่ม แต่ละชั้นจะกว้างได้ไม่เกิน 10

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

• บรรทัด 1: ระบุความสูงรวมที่น้อยที่สุดของชุดของชั้นหนังสือ

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

21

คำอธิบายข้อมูลส่งออก: มีสามชั้น ชั้นแรกมีแค่หนังสือเล่มที่ 1 (สูง 5 กว้าง 7), ชั้นที่สองมีหนังสือเล่มที่ 2..4 (สูง 13 กว้าง 9), ชั้นที่สามมีหนังสือเล่มที่ 5 (สูง 3 กว้าง 8)

Problem 3. Balanced Cow Subsets

Source: [7]

โจทย์โดย: Neal Wu, 2012

ชาวนาจอห์น (FJ) มีวัว N ตัว (2 <= N <= 20), วัวตัวที่ i ให้นม M(i) หน่วยต่อวัน (1 <= M(i) <= 100,000,000) FJ ต้องการจะพัฒนาระบบการรีดนมในแต่ละวันให้รวดเร็วยิ่งขึ้น เขาจึงได้ติดตั้งเครื่องรีดนมใหม่ในโรงนา โชคไม่ดีเสียเลยที่เครื่องรีดนมนั้นช่างอ่อนไหวต่อความผิดพลาดมาก กล่าวคือ เครื่องรีดนมจะทำงานได้ถ้าจำนวนนมรวมที่วัวที่อยู่ด้านซ้ายของโรงนา เท่ากับจำนวนนมรวมของวัวที่อยู่ในด้านขวาเท่านั้น

เรียกสับเซตของวัวว่า "สมดุลย์" (balanced) ถ้าสับเซตดังกล่าวสามารถแบ่งออกเป็นกลุ่มที่มีจำนวนนมรวมเท่ากัน เนื่องจากในการรีดนมนั้น จะต้องใช้สับเซตของวัวที่สมดุลย์เท่านั้น FJ จึงสงสัยว่ามีสับเซตของวัวกี่สับเซตที่สมดุลย์ ช่วยเขาคำนวณค่านี้ด้วย

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

• บรรทัด 1: จำนวนเต็ม N
• บรรทัด 2..1+N: บรรทัดที่ i+1 ระบุ M(i)

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

4 
1 
2 
3 
4

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

• บรรทัดที่ 1: จำนวนของสับเซตที่สมดุลย์

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

3

คำอธิบายข้อมูลส่งออก: มี 3 สับเซตที่สมดุลย์คือ {1,2,3} (แบ่งเป็น {1,2} กับ {3}), {1,3,4} (แบ่งเป็น {1,3} กับ {4}), และ {1,2,3,4} (แบ่งเป็น {1,4} กับ {2,3})