หลังกลับจากต่างจังหวัด เพื่อนของคุณได้ซื้อขนมมาฝากคุณ 2 ถุงใหญ่ แต่เนื่องจากเพื่อนของคุณเป็นนักคณิตศาสตร์ จะซื้อขนมมาให้ใครฟรีๆ ก็กระไรอยู่ เขาจึงท้าให้คุณเล่นเกมย้ายขนมให้ชนะเสียก่อน จึงจะได้รับขนมทั้งหมดเป็นของฝาก
เกมนี้มีกติกาว่า ในตอนเริ่มต้น จะมีถุงอยู่ 2 ใบ แต่ละใบบรรจุขนมที่มีราคาต่างๆ อยู่จำนวนมาก คุณสามารถย้ายขนม 1 ชิ้น จากถุงใบหนึ่งไปยังอีกใบหนึ่ง ให้สอดคล้องเงื่อนไขต่อไปนี้
การย้ายขนมแต่ละครั้งสามารถย้ายจากถุงใบไหนไปใบไหนก็ได้ แต่สามารถย้ายได้ครั้งละ 1 ชิ้นเท่านั้น คุณต้องย้ายขนมให้ได้มากครั้งที่สุดเท่าที่จะทำได้ โดยที่การย้ายขนมทุกครั้งจะต้องสอดคล้องตามเงื่อนไขเสมอ
ตัวอย่างเช่น หากในตอนเริ่มต้น ถุงใบแรกมีขนมราคา 4, 6, 10, 15 และ 20 บาท ซึ่งมีค่าเฉลี่ยเป็น 11 บาท ส่วนถุงใบที่สองมีขนมราคา 3 และ 5 บาท ซึ่งมีค่าเฉลี่ยเป็น 4 บาท คุณสามารถย้ายขนมราคา 10 บาท จากถุงใบแรกไปยังใบที่สองได้ ซึ่งจะทำให้ค่าเฉลี่ยของราคาขนมในถุงใบแรกเพิ่มเป็น 11.25 บาท และใบที่สองเพิ่มเป็น 6 บาท แต่หลังจากนั้น คุณจะไม่สามารถย้ายขนมชิ้นใดๆ ให้สอดคล้องตามเงื่อนไขได้อีกแล้ว ดังนั้น คุณจึงย้ายขนมได้เพียงครั้งเดียว
แต่วิธีดังกล่าวยังไม่ใช่วิธีที่ดีที่สุด หากคุณเริ่มต้นด้วยการย้ายขนมราคา 6 บาท จากถุงใบแรกไปยังใบที่สอง ค่าเฉลี่ยของราคาขนมในถุงใบแรกจะเพิ่มเป็น 12.25 บาท และใบที่สองจะเพิ่มเป็น 4.67 บาท จากนั้น คุณจึงย้ายขนมราคา 10 บาท จากถุงใบแรกไปยังใบที่สอง ทำให้ค่าเฉลี่ยของราคาขนมในถุงใบแรกเพิ่มเป็น 13 บาท และใบที่สองเพิ่มเป็น 6 บาท คุณจึงย้ายขนมได้ทั้งหมด 2 ครั้ง ซึ่งวิธีนี้เป็นวิธีที่ทำให้ย้ายขนมตามเงื่อนไขได้มากครั้งที่สุดแล้ว
งานของคุณ
จงเขียนโปรแกรมเพื่อรับราคาของขนมในแต่ละถุงตอนเริ่มต้น แล้วคำนวณหาจำนวนครั้งในการย้ายขนมตามเงื่อนไขที่มากที่สุดที่เป็นไปได้
ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม A และ B (1 ≤ A,B ≤ 1,000,000) แทนจำนวนขนมตอนเริ่มต้นในถุงใบแรกและใบที่สอง
บรรทัดต่อมาระบุจำนวนเต็มบวก A ตัว แทนราคาของขนมแต่ละชิ้นในถุงใบแรก โดยเรียงจากน้อยไปหามาก
บรรทัดต่อมาระบุจำนวนเต็มบวก B ตัว แทนราคาของขนมแต่ละชิ้นในถุงใบที่สอง โดยเรียงจากน้อยไปหามาก
ขนมแต่ละชิ้นจะมีราคาไม่เกิน 1,000,000 บาท และขนมแต่ละชิ้นอาจมีราคาเท่ากันได้
ข้อมูลส่งออก
มีบรรทัดเดียว แทนจำนวนครั้งในการย้ายขนมตามเงื่อนไขที่มากที่สุดที่เป็นไปได้
การให้คะแนน
20% ของข้อมูลทดสอบ จะมี A,B ≤ 10
40% ของข้อมูลทดสอบ จะมี A,B ≤ 1,000
60% ของข้อมูลทดสอบ จะมี A,B ≤ 100,000
ที่มา
โจทย์โดย: สุธี เรืองวิเศษ
ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
5 2 4 6 10 15 20 3 5 | 2 |
4 3 4 6 15 20 3 5 10 | 0 |