المپدیا

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

ابزار کاربر

ابزار سایت


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

Segment

روی محور اعداد $n$ بازه‌ی بسته به شما داده شده است. یک رنگ‌آمیزی از بازه‌ها معتبر است اگر هیچ دو بازه‌ی ﻫﻤﺮﻧﮕﯽ ﺍﺷﺘﺮﺍﮎ ﻧﺪﺍﺷﺘﻪ ﺑﺎﺷﻨﺪ (ﺩﻭ ﺑﺎﺯﻩ ﺍﺷﺘﺮﺍﮎ ﺩﺍﺭﻧﺪ ﺍﮔﺮ ﺩﺭ ﺣﺪﺍﻗﻞ ﯾﮏ ﻧﻘﻄﻪ ﻣﺸﺘﺮﮎ ﺑﺎﺷﻨﺪ). ﯾﮏ ﻋﺪﺩ $x$ ﺑﻪ ﺷﻤﺎ ﺩﺍﺩﻩ ﻣﯽﺷﻮﺩ، ﺷﻤﺎ ﺑﺎﯾﺴﺘﯽ $x$ ﺗﺎ ﺍﺯ ﺍﯾﻦ $n$ ﺑﺎﺯﻩ ﺭﺍ ﺍﻧﺘﺨﺎﺏ ﮐﻨﯿﺪ ﻃﻮﺭﯼ ﮐﻪ ﺑﺘﻮﺍﻥ ﺑﺎ ﮐﻤﺘﺮﯾﻦ ﺗﻌﺪﺍﺩ ﺭﻧﮓ، ﯾﮏ ﺭﻧﮓﺁﻣﯿﺰﯼ ﻣﻌﺘﺒﺮ ﺑﺮﺍﯼ ﺁﻧﻬﺎ ﺍﺭﺍﺋﻪ ﮐﺮﺩ.

ﺑﺮﻧﺎﻣﻪﺍﯼ ﺑﻨﻮﯾﺴﯿﺪ ﮐﻪ:

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

ورودی

ﺩﺭ ﺳﻄﺮ ﻧﺨﺴﺖ ﻭﺭﻭﺩﯼ ﺩﻭ ﻋﺪﺩ ﺻﺤﯿﺢ $n$ و $x$ به ترتیب نوشته شده‌اند.($1\leq n \leq 10^5$ و $1\leq x \leq n$)

در $n$ سطر بعد مشخصات $n$ بازه آمده است. در سطر $i+1$ام دو عدد نوشته شده است که به ترتیب ابتدا و انتهای بازه‌ی $i$ ام را مشخص می‌کنند.(تمام اعداد ورودی در بازه‌ی $[-2^{30},2^{30}]$ می‌باشند.

خروجی

ﺩﺭ ﺳ‰ﻄ‰ﺮ ﻧ‰ﺨ‰ﺴ‰ﺖ ﺧ‰ﺮﻭﺟ‰ﯽ کم‌ترین ﺗ‰ﻌ‰ﺪﺍﺩ ﺭﻧ‰ﮓ ﻻﺯﻡ ﺑ‰ﺮﺍﯼ ﺭﻧ‰ﮓ ﺁﻣ‰ﯿ‰ﺰﯼ ﻣ‰ﻌ‰ﺘ‰ﺒ‰ﺮ $x$ ﺑ‰ﺎﺯﻩﯼ ﺍﻧﺘﺨﺎﺑﯽ ﺭﺍ ﺑﻨﻮﯾﺴﯿﺪ.

ﺩﺭ ﺳﻄﺮ ﺩﻭﻡ $x$ ﻋﺪﺩ ﺑﻨﻮﯾﺴﯿﺪ ﮐﻪ ﺷﻤﺎﺭﻩﯼ ﺑﺎﺯﻩﻫﺎﯼ ﺍﻧﺘﺨﺎﺑﯽ ﺭﺍ مشخص ﻣﯽﮐﻨﺪ. ﺷﻤﺎ ﺑﺎﯾﺪ ﺷﻤﺎﺭﻩﯼ ﺑﺎﺯﻩﻫﺎ ﺭﺍ ﺑﻪ ﺗﺮﺗﯿﺐ ﺻﻌﻮﺩﯼ ﺑﻨﻮﯾﺴﯿﺪ. ﺩﺭ ﺿﻤﻦ ﺍﯾﻦ ﺷﻤﺎﺭﻩﻫﺎ ﺭﺍ ﺑﺎ ﻓﺎﺻﻠﻪ ﺍﺯ ﻫﻢ ﺟﺪﺍ ﮐﻨﯿﺪ.

محدودیت‌ها

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

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

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

ابزار صفحه