Balkan2011

BOI 2011 Day 2: Trapezoid

Source: http://www.boi2011.ro/resurse/tasks/trapezoid.pdf

(หน่วยความจำ 64 MB, เวลาทำงาน 0.5 sec, คะแนนเต็ม 100 คะแนน)

เมื่อพิจารณาเส้นตรงในแนวนอนสองเส้นใดๆ สี่เหลี่ยมคางหมู Ti สามารถสร้างขึ้นระหว่างเส้นทั้งสองนี้ โดยจะประกอบด้วยเส้นแนวตั้งที่เชื่อมจุดสองจุดบนเเส้นแนวนอนด้านบนและสองจุดจากเส้นด้านล่าง (ดูรูปประกอบ) เราจะตั้งชื่อจุดเหล่านี้ว่า ai, bi, ci, และ di ที่หมายถึงจุดบนซ้าย, บนขวา, ล่างซ้าย, และล่างขวา ตามลำดับ ซึ่งเป็นเป็นจุดยอดของสี่เหลี่ยมคางหมู Ti ซับเซต S ของสี่เหลี่ยมคางหมูจะเรียกว่าอิสระต่อกันเมื่อไม่มีสองสี่เหลี่ยมคางหมูใดใน S ที่ซ้อนทับกัน

หน้าที่ของคุณ

ให้หาว่าขนาด (cardinality) ของซับเซตของสี่เหลี่ยมคางหมูที่อิสระต่อกันที่ใหญ่ที่สุด (ขนาดใหญ่ที่สุดหมายถึงมีจำนวนสมาชิกมากที่สุด) และให้หาด้วยว่ามีซับเซตของสี่เหลี่ยมคางหมูที่อิสระต่อกันทั้งหมดกี่ซับเซตที่มีขนาดใหญ่ที่สุดเท่ากัน ให้ตอบจำนวนที่สองโดยใช้เศษจากการหาร (modulo) ด้วย 30013

ข้อมูลนำเข้า

บรรทัดที่ 1 ประกอบด้วย จำนวนเต็มหนึ่งจำนวน N ที่แสดงถึงจำนวนสี่เหลี่ยมคางหมูทั้งหมด ต่อมาอีก N บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มสี่จำนวน ai, bi, ci, และ di ทั้งนี้ไม่มีสี่เหลี่ยมคางหมูใดๆ ที่มีจุดยอด (จุดมุม) เดียวกัน

ข้อมูลส่งออก

ให้แสดงคำตอบบรรทัดเดียวโดยประกอบไปด้วยจำนวนสองจำนวน คั่นด้วยช่องกลาง

จำนวนแรก คือ ขนาดของเซตของสี่เหลี่ยมคางหมูที่อิสระต่อกันที่ใหญ่ที่สุด

จำนวนที่สอง คือ จำนวนเซตที่อิสระต่อกัน ที่แตกต่างกันทั้งหมดที่เป็นไปได้ หารเอาเศษด้วย 30013

เงื่อนไข

1 <= N <= 100,000

1 <= ai, bi, ci, di <= 1,000,000,000

ถ้าตอบถูกเฉพาะจำนวนแรกในข้อมูลส่งออก จะได้คะแนน 40% ของข้อมูลทดสอบนั้นๆ

40% ของข้อมูลทดสอบทั้งหมดจะมี N <= 5,000

ตัวอย่าง

ควรดูรูปในโจทย์ประกอบครับ

BOI 2011 Day 2: TimeIsMoney

Source: http://www.boi2011.ro/resurse/tasks/timeismoney.pdf

(หน่วยความจำ 64 MB, เวลาทำงาน 2 sec, คะแนนเต็ม 100 คะแนน)

บริษัทเน็ตไลน์ต้องการติดตั้งเครือข่ายอินเทอร์เน็ตเพื่อเชือมโยง N เมืองเข้าด้วยกัน ในการนี้บริษัทจะต้อเชื่อมโยงเครือข่ายโดยใช้ลิงค์ทั้งหมด N-1 เส้นที่เชื่อมต่อระหว่างเมือสองเมือง ดังนั้นเมื่อเชื่อมต่อสำเร็จข้อความจะสามารถส่งผ่านจากเมืองหนึ่งไปยังเมืองอื่นๆทั้งหมดได้ ทั้งนี้บริษัทเน็ตไลน์ได้ระบุคู่ของเมืองทีั้งหมดที่สามารถจะสร้างลิงค์เชื่อมถึงกันได้ และในแต่ละลิงค์นั้นทางบริษัทได้คำนวณค่าใช้จ่ายและเวลาที่ต้องใช้ในการสร้างลิงค์เป็นที่เรีบบร้อยแล้วอีกด้วย

บริษัทสนใจที่จะหาค่าที่น้อยที่สุดของทั้งระยะเวลาในการสร้าง (สามารถสร้างได้เวลาละหนึ่งลิงค์) และจำนวนเงินที่ต้องใช้ในการสร้างลิงค์ทั้งหมดในเครือข่าย เนื่องจากพวกเขาไม่สามารถตัดสินใจที่จะเลือกระหว่างสองเงื่อนไขนี้พวกเขาจึงจะใช้สูตรในการคำนวนโดย:

SumTime = ผลรวมเวลาทั้งหมดที่ใช้ในการสร้างลิงค์ทั้งหมดที่เลือก

SumMoney = ผลรวมของจำนวนเงินทั้งหมดที่ต้องใช้ในการสร้างลิงค์ทั้งหมดที่เลือก

V = SumTime * SumMoney

งานของคุณ

ให้หารายการของ N-1 ลิงค์ที่จะสร้างและทำให้ค่า V ต่ำที่สุด

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วยจำนวนเต็มสองจำนวน: N แทยจำนวนเมืองและ M แทนจำนวนลิงค์ที่สามารถสร้างขึ้นโดยเชื่อมระหว่างเมืองสองเมืองเข้าด้วยกัน

ต่อมาอีก M บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็ม 4 จำนวน คือ x, y, t, และ c โดยหมายถึง เมือง x สามารถเชื่อมต่อไปยังเมือง y ได้ โดยใช้เวลาในการสร้าง t และค่าใช้จ่าย c

ข้อมูลส่งออก

บรรทัดแรกให้แสดงจำนวนสองจำนวน คือ เวลาทั้งหมด (SumTime) และจำนวนเงินทั้งหมด (SumMoney) ที่ใช้ในคำตอบที่ดีที่สุด (optimal solution ซึ่งเป็นคำตอบให้ค่า V น้อยที่สุด) โดยให้คั่นด้วยช่องว่างหนึ่งช่อง

ต่อมาอีก N-1 บรรทัด ให้แสดงลิงค์ที่จะสร้าง โดยในแต่ละบรรทัดให้ระบุตัวเลขสองจำนวนที่แสดงเมืองที่ต้องการเชื่อมต่อเข้าด้วยกัน (โดยลิงค์ที่ระบุจะต้องเป็นลิงค์ที่สามารถสร้างขึ้นได้) ตัวเลขแสดงคู่ของเมืองนี้สามารถแสดงในลำดับใดก็ได้

ถ้ามีคำตอบมากกว่าหนึ่งคำตอบ คุณสามารถตอบคำตอบใดก็ได้

เงื่อนไข

1 <= N <= 200

1 <= M <= 10,000

0 <= x,y <= N-1

1 <= t,c <= 255

มีหนึ่งชุดทดสอบที่ M = N-1

40% ของชุดทดสอบจะมีค่า t = c สำหรับทุกลิงค์ตั้งต้นที่กำหนดให้

ตัวอย่าง

input

5 7

0 1 161 79

0 2 161 15

0 3 13 153

1 4 142 183

2 4 236 80

3 4 40 241

2 1 65 92

output

279 501

2 1

0 3

0 2

3 4

BOI 2011 Day 2: Cmp

Source (โจทย์และไฟล์ที่จำเป็น): http://www.boi2011.ro/resurse/tasks/cmp.zip

(หน่วยความจำ 64 MB, เวลาทำงาน 2 sec, คะแนนเต็ม 100 คะแนน)

คุณต้องการออกแบบอัลกอริทึมสำหรับเครื่องคอมพิวเตอร์รุ่นดึกดำบรรพ์ที่มีหน่วยความจำเพียง 10240 บิต เริ่มต้นหน่วยควมจำทั้งหมดมีค่าเป็น 0 และหลังจากนั้นคุณสามารถเขียนหรืออ่านได้ครั้งละหนึ่งบิต

โดยคุณจะต้องเขียนสองการทำงานด้านล่างนี้ลงบนคอมพิวเตอร์:

remember(a): เมื่อ a แทนจำนวนเต็มมีค่าตั้งแต่ 0 ถึง 4095

การเขียนฟังก์ชันนี้สามารถเรียกใช้คำสั่ง:

bit_set(address): เมื่อ address แทนตัวเลขจำนวนเต็มตั้งแต่ 1 ถึง 10240

โดยที่หน่วยความจำหนึ่งบิตที่ตำแหน่ง address จะถูกเขียนค่าให้เป็น 1

compare(b): เมื่อ b แทนจำนวนเต็มตั้งแต่ 0 ถึง 4095

ถ้า b < a, ให้คืนค่า -1

ถ้า b = a, ให้คืนค่า 0

ถ้า b > a, ให้คืนค่า 1

การเขียนฟังก์ชันนี้สามารถเรียกใช้คำสั่ง:

bit_get(address) ที่ทำหน้าที่คืนค่าหน่วยความจำหนึ่งบิตที่ตำแหน่ง address โดยจะมีค่าเป็น 1 ถ้าหน่วยความจำบิตนี้เคยถูกให้ค่าโดยคำสั่ง remember(a) มาก่อน, นอกจากนั้นจะมีค่ืนค่า 0

งานของคุณ

ให้เขียนฟังกํชัน remember() และ compare() โดยเป้าหมายคือให้มีการเรียกใช้คำสั่งการเข้าถึงหน่วยความจำให้น้อยที่สุด (bit_set() และ bit_get()) ซึ่งคิดจากกรณีแย่สุดสำหรับทุกค่า a และ b ที่เป็นไปได้

โปรแกรมของคุณจะมีการทำงานและเกณฑ์การให้คะแนนในรายละเอียดดังนี้ (ควรดาวน์โหลด code เพื่อดูประกอบครับ):

กำหนดให้ AllMemory = array[0..4095][1..10240] เป็นอาร์เรย์สองมิติของบิต

ให้ค่าทุกช่องใน AllMemory เป็น 0

for a = 0..4095

remember(a) ซึ่งจะมีการกำหนด bit_set(address) (สำหรับ address บางค่าที่ต้องการ) และจะเปลี่ยนค่า AllMemory[a][address] ให้เป็น 1

ให้ maxA คือ จำนวนครั้งที่มากที่สุดที่เรียกใช้คำสั่ง bit_set() สำหรับค่า a ใดๆ

for (a,b) in {0..4095}x{0..4095} ในลำดับสุ่ม (ทุกคู่ a,b จะถูกพิจารณา)

answer = compare(b)

ในคำสั่ง compare(b) จะมีการเรียกใช้คำสั่ง bit_get(address) ซึ่งจะคืนค่า AllMemory[a][address]

ถ้า answer ในการเปรียบเทียบค่า a และ b ไม่ถูกต้องจะได้คะแนนทั้งหมด 0 และจบโปรแกรม

ให้ maxB คือ จำนวนครั้งที่มากที่สุดที่เรียกใช้คำสั่ง bit_get() สำหรับคู่ a,b ใดๆ

T = maxA + maxB

ถ้า (T>20), คุณจะได้คะแนน 0 และจบโปรแกรม

นอกจากนั้น, คุณจะได้คะแนน 1+9*(21-T) และจบโปรแกรม

รายละเอียดเพิ่มเติมให้อ่านในโจทย์ต้นฉบับ คำแนะนำ: ให้อ่าน code ที่โจทย์แนบมาให้ครับ จะเข้าใจความสัมพันธ์ระหว่าง a และ b มากขึ้น เช่น ถ้าเขียนน้อยครั้ง ก็ อาจจะต้องอ่านหลายครั้ง เป็นต้น