Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۳:عملی نهایی اول:سوال ۲

اسپانسر

متاسفانه به دلیل رکود اقتصادی امسال استقبال از باشگاه‌های بدنسازی آقا داوود کم شده و اسپانسرهای آن‌ها به دلیل نداشتن توجیه اقتصادی تصمیم به تعطیلی بعضی از باشگاه‌ها گرفته‌اند. اما می‌دانیم اسپانسرها آنقدرها هم مادی نیستند و هر کدام از آن‌ها تصمیم دارند دقیقاً یکی از باشگاه‌های تحت حمایت خود را تعطیل کنند. شاگردان آقا داوود با شنیدن این خبر، تصمیم گرفته‌اند به محض تعطیل شدن باشگاه‌ها، به نشانه‌ی اعتراض از یکی از باشگاه‌های غیر تعطیل به باشگاه غیر تعطیل دیگری راهپیمایی کنند. اما چون آدم‌های تنبلی هستند قصد دارند آن دو باشگاه را طوری انتخاب کنند که کمترین فاصله ممکن بین باشگاه‌های غیرتعطیل را داشته باشند. خبر راهپیمایی به گوش اسپانسرها رسیده و حال آنها تصمیم دارند طوری باشگاه‌های خود را تعطیل کنند که شاگردان آقا داوود طولانی‌ترین راهپیمایی ممکن را انجام دهند. حال شما باید میزان راهپیمایی شاگردان آقا داوود را در صورتی که اسپانسرها به صورت هوشمندانه عمل کنند، در خروجی چاپ کنید. برای سادگی کار باشگاه‌ها را به صورت نقطه‌هایی در صفحه‌ی مختصات در نظر بگیرید. با توجه به این که صحبت درباره‌ی باشگاه‌های آقا داوود در منهتن نیویورک است، منظور از فاصله بین باشگاه‌ها، فاصله منهتنی بین آن‌ها است. فاصله منهتنی دو نقطه‌ی A=(Xa,Ya) و B=(Xb,Yb) مساوی است با |XaXb|+|YaYb|.

ورودی

  • سطر اول ورودی شامل دو عدد طبیعی، 3N1392، تعداد باشگاه‌های آقا داوود، و 1MN/2، تعداد اسپانسرها، است.
  • سطرهای دوم تا N+1-ام ورودی شامل مکان باشگاه‌های آقا داوود به صورت نقطه‌هایی در صفحه مختصات و اسپانسر آن‌ها هستند. به طوریکه خط i+1-ام ورودی شامل سه عدد صحیح، 106Xi,Yi106، مختصات باشگاه i-ام، و 1CiM، اسپانسر باشگاه i-ام است. Xi عرض باشگاه i-ام و Yi طول آن در صفحه مختصات را نشان می‌دهند.
  • تضمین می‌شود که در ورودی‌ها، مختصات باشگاه‌ها متمایز است و به ازای هر 1iM حداقل دو باشگاه وجود دارند که توسط اسپانسر شمارهی i حمایت شوند.
  • در 30 درصد از ورودی‌ها، 1N40 است

خروجی

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

محدودیت‌ها

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

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

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

ابزار صفحه