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 ด้วย

Advertisements

One thought on “USACO Feb 2012

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s