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
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})
