1075 : หนอน (worm)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 128 megabyte(s)

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

            แต่แล้วปัญหาก็เกิดขึ้นอีกแล้ว เมื่อคุณพบว่า ในการยิงหนอนแต่ละตัวนั้น ต้องใช้ค่าไฟมากยิ่งขึ้นไปอีก เหล่สายตาไปมองตัวเลขบนบิลค่าไฟที่อยู่ข้าง ตัว นั่นทำให้คุณตกที่นั่งลำบากอีกเสียแล้ว

            คุณมีหนอนอยู่ทั้งหมด N ตัว แต่ละตัวมีค่าไฟในการยิงและจำนวนข้อมูลที่สามารถทำลายได้แตกต่างกันไป การคิดค่าไฟในการยิงหนึ่งครั้ง จะคิดโดยคิดตามค่าไฟของหนอนตัวที่มีมูลค่ามากที่สุด ตัวอย่างเช่น ถ้ามีหนอน 5 ตัว มีจำนวนข้อมูลที่ทำลายได้และค่าไฟ ดังนี้

หนอนตัวที่

จำนวนข้อมูลที่ทำลายได้

ค่าไฟ

1

3

30

2

6

10

3

10

20

4

7

50

5

18

70

            ถ้าเลือกยิงหนอนตัวที่ 1, 3, 5 ซึ่งใช้ค่าไฟ 30, 20, 70 ตามลำดับ จะต้องเสียค่าไฟในการยิงทั้งหมด 70 หน่วย แต่ถ้าเลือกยิงหนอนตัวที่ 3, 4 ซึ่งใช้ค่าไฟ 20, 50 ตามลำดับ จะต้องเสียค่าไฟในการยิงทั้งหมด 50 หน่วย

            คุณสามารถนิยามอัตราส่วนความคุ้มค่าของการยิงหนอน ให้มีค่าเท่ากับ จำนวนข้อมูลที่ทำลายได้ทั้งหมด หารด้วย ค่าไฟที่ใช้ในการยิง ซึ่งแน่นอนว่า คุณไม่ต้องการจะเสียค่าไฟให้เยอะกว่าเดิมโดยเปล่าประโยชน์

งานของคุณ

เขียนโปรแกรมที่รับข้อมูลของหนอนทั้งหมด N ตัว และคำนวณหาอัตราส่วนความคุ้มค่าที่มากที่สุดที่เป็นไปได้

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

บรรทัดที่ 1 มีจำนวนเต็ม N (1 N 100,000) แทนจำนวนของหนอน

บรรทัดที่ 2 ถึง N + 1 ประกอบด้วยจำนวนเต็ม Di และ Ci (0 Di 50,000 และ 1 Ci800,000,000) แทนจำนวนข้อมูลที่ทำลายได้ และค่าไฟที่ใช้ในการยิงของหนอนตัวที่ i ตามลำดับ

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

บรรทัดที่ 1 แสดงจำนวนข้อมูลที่คุณสามารถทำลายได้ทั้งหมด และค่าไฟที่ใช้ในการยิง คั่นด้วยช่องว่าง 1 ช่อง ในวิธีที่มีอัตราส่วนความคุ้มค่าที่มากที่สุด

หมายเหตุ หากมีวิธีค่าส่งหลายวิธีให้ตอบวิธีที่ใช้ค่าไฟน้อยที่สุด

อธิบายตัวอย่างข้อมูลนำเข้าและส่งออกที่ 1

ถ้าเลือกยิงหนอนตัวที่ 2 และ 3 จะสามารถทำลายข้อมูลได้รวมเท่ากับ 16 และเสียค่าไฟ 20 หน่วย ซึ่งมีอัตราส่วนความคุ้มค่า = 0.80 ซึ่งเป็นค่าที่มากที่สุดในการยิงหนอนครั้งนี้

การให้คะแนน

30% ของชุดข้อมูลทดสอบมีค่า 1 ≤ N ≤ 20,000 สำหรับชุดข้อมูลทดสอบทั้งหมด N 100,000

 

โจทย์โดย: ศรัณย์ ไพศาลศรีสมสุข

ที่มา: TOI.C:01-2009


ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
5
3 30
6 10
10 20
7 50
18 70
16 20

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้

กำลังออนไลน์: 16 ผู้เยี่ยมชมและ 1 สมาชิก (3 บอท)