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
USACO 2012 Feb, Gold
USACO 2012 Mar, Gold
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})
