المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۵:سوال ۱۴

War

در جنگی که بین الف‌ها و اورک‌ها درگرفته، الف‌ها دارند شکست می‌خوردند. در همین زمان به الف‌ها خبر رسید که نیروهای کمکی‌شان در راهند. برای همین الف‌ها استراتژی جدیدی را برای طولانی کردن مبارزات در پیش گرفتند که نبردهای تن‌به‌تن است. در هر مبارزه دو الف با یک اورک می‌جنگند.

هر اورک و هر الف قدرتی دارند که با یک عدد طبیعی مشخص می‌شود.

طبق قوانین مبارزات تن‌به‌تن، قدرت هر دو الف نمی‌تواند بیش‌تر از اورک باشد یا یکی از الف‌ها قوی‌تر از اورک و الف دیگر هم قدرت اورک باشد. و از طرفی اگر هر دو الف ضعیف‌تر یا هم‌قدرت اورک باشند، به سرعت شکست می‌خورند.

تنها حالت باقی‌مانده این است که یکی از الف‌ها قوی‌تر از اورک و الف دیگر ضعیف‌تر از اورک باشد. در ضمن هر الف و هر اورک حداکثر در یک مبارزه‌ی تن‌به‌تن می‌توانند شرکت کنند.

شما باید برای الف‌ها برنامه‌ای بنویسید که بیشینه‌ی تعداد نبرد‌های تن‌به‌تن را به‌دست آورد.

برنامه‌ای بنویسید که:

  • تعداد الف‌ها و اورک‌ها و قدرت هر کدام از آن‌ها را از ورودی بخواند.
  • پاسخی بیشینه برای طولانی شدن جنگ به‌دست آورد.
  • پاسخ را در خروجی بنویسید.

ورودی

در سطر نخست ورودی تعداد اورک‌ها و الف‌ها آمده؛ در سطر دوم، قدرت اورک‌ها آمده و در سطر سوم، قدرت الف‌ها.

تمام اعداد ورودی در متغیر‌های ۳۲ بیتی علامت‌دار جای می‌گیرند. تعداد اورک‌ها و هم‌چنین تعداد الف‌ها حداکثر $10^5$ می‌باشد.

خروجی

در سطر اول خروجی، بیشینه‌ی تعداد نبرد‌های تن‌به‌تن را بنویسید و سپس در هر سطر دیگر شرکت‌کننده‌های یک نبرد را. یعنی ابتدا شماره‌ی اورک و سپس شماره‌ی دو الف را بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۶۴ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
4 6
2 3 4 5
1 3 2 2 5 2
2
1 1 2
3 4 5

ابزار صفحه