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 คะแนน)