Usaco2012

USACO Open 2012: Gold

Problem 1. Tied Down

Source: [1]

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

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

เพื่อน ๆ วัวต้องการช่วย 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: [3]

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

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

Problem 3. Balanced Cow Subsets

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

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