المپدیا

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

ابزار کاربر

ابزار سایت


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

سربازها

$N$ سرباز از ایران زمین به طور تصادفی در سرتاسر زمین پراکنده شده‌اند.

هر مکانی با یک دوتایی $(x,y)$ از اعداد صحیح مشخص خواهد شد. یک سرباز در یک حرکت می‌تواند به اندازه‌ی ۱ واحد بالا یا پایین یا چپ یا راست برود (در واقع می‌تواند یکی از $x$‌ یا $y$ خود را به اندازه‌ی ۱ واحد تغییر دهد.)

سربازها می‌خواهند طوری حرکت کنند که سرانجام روی یک خط افقی پشت سر یک‌دیگر بایستند. (در واقع مکان‌های نهایی به صورت $(x,y),(x+1,y),...,(x+N-1,y)$ هستند.) دقت کنید که اعداد صحیح $x$ و $y$ و ترتیب نهایی سربازها روی خط دل‌خواه هستند.

هدف ما این است که تعداد حرکات لازم برای رسیدن به چنین آرایشی را کمینه کنیم.

در ضمن هیچ‌گاه دو سرباز نمی‌توانند یک مکان را اشغال کنند.

ورودی

در سطر اول فایل ورودی ابتدا $N$ تعداد سرباز‌ها آمده سپس در $N$ سطر در هر کدام مکان اولیه‌ یک سرباز به صورت دو عدد صحیح $x$ و $y$ داده شده است. دقت کنید $1\leq N \leq 10^4$ و $-10^4 \leq x,y \leq 10^4$

خروجی

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

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۶۰۰ کیلوبایت

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

ورودي نمونه خروجي نمونه
3
1 0
2 4
3 2
4
5
1 2
2 2
1 3
3 -2
3 3
8

ابزار صفحه