Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۳۵

Segment

روی محور اعداد ‎n‎ بازه ی بسته به شما داده شده است. یک رنگ‌آمیزی از بازه‌ها معتبر است اگر هیچ دو بازه‌ی هم‌رنگی اشتراک نداشته باشند‎ (دو بازه اشتراک دارند اگر در حداقل یک نقطه مشترک باشند). یک عدد ‎x‎ به شما داده می شود. شما بایستی ‎x‎ تا از این ‎n‎ بازه را انتخاب کنید طوری که بتوان با کم‌ترین تعداد رنگ، یک رنگ‌آمیزی معتبر برای آن‌ها ارائه کرد.‎

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

  • اعداد ‎n‎ و ‎x‎ و مشخصات بازه‌ها را از ورودی بخواند.
  • کم‌ترین تعداد رنگ برای رنگ کردن بازه‌ها و نحوه‌ی رنگ کردن آن‌ها با این تعداد رنگ را بیابد و در خروجی بنویسید.

ورودی

  • در سطر نخست ورودی دو عدد صحیح ‎n‎ و ‎x‎ به ترتیب نوشته شده‌اند.
  • در ‎n‎ سطر بعد، مشخصات ‎n‎ بازه آمده است. در سط ‎i+1‎ام دو عدد نوشته شده است که به ترتیب ابتدا و انتهای بازه‌ی ‎i‎ام را مشخص می کنند.‎
  • 1n100000 (در ‎40‎ درصد تست‌ها ‎n300‎ می باشد).
  • 1xn.

خروجی

  • در سطر نخست خروجی، کم‌ترین تعداد رنگ لازم برای رنگ‌آمیزی معتبر ‎x‎ بازه‌ی انتخابی را بنویسید.‎
  • در سطر دوم ‎x‎ عدد بنویسید که شماره‌ی بازه‌های انتخابی را مشخص می‌کند. شما باید شماره‌ی بازه‌ها را به ترتیب صعودی بنویسید. در ضمن این شماره‌ها با فاصله از هم جدا کنید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3 2‎
-‎1 1‎
2 3‎
-‎1 3
1
1 2
2 2‎
0 2‎
2 3
2
1 2

ابزار صفحه