USACO Feb 2012

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 Jan 2012

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 Dec 2011

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 Nov 2011

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) ตัวอย่างแสดงดังด้านล่าง:

steeple-fig1

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

steeple-fig2

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

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