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]

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