پاسخ - SGU 158

متن اصلی سوال : http://acm.sgu.ru/problem.php?contest=0&problem=158

ترجمه :

در یک کشور ، دولت تصمیم گرفته تا سیستم قطار های شهری را هوشمند بکند ، صرف نظر از همه ی ویژگی ها ، این سیستم باید قطار ها را در ایستگاه متوقف بکند . در هر قطار یک کامپیوتر متصل به یک رادار وجود دارد که موقعیت مسافران در ایستگاه را پیدا می کند کامپیوتر باید محل توقف قطار در ایستگاه را مشخص کند به طوری که مجموع فاصله مسافران از نزدیک ترین در ه قطار به آنها بیشینه باشد .
وظیفه ی شما این است که با گرفتن اطلاعات ایستگاه و محل قرار گیری مسافران بهترین مکان برای توقف قطار در ایستگاه را مشخص کند .

ایستگاه قطار طولی به اندازه ی L دارد ( ) ، در ایستگاه M مسافر حضور دارند  (  ) ، مسافر i ام در موقعیت قرار دارد (  ) ، قطار N در ورودی دارد (  ) ، در ورودی i در موقعیت قرار دارد (  ) در واقع این مقدار برابر با فاصله آن در با در ورودی اول قطار است . فاصله ی مسافر i ام تا در ورودی j ام برابر است با : به طوری که S موقعیت قطار نامیده می شود و برابر است با فاصله ی در ورودی شماره یک قطار و ابتدای ایستگاه قطار . به خاطر داشته باشید قطار فقط می تواند در موقعیت هایی توقف کند که همه ی در های ورودی اش در ایستگاه باشند .

ورودی :

در خط اول ورودی عدد L
در خط دوم ورودی عدد M
در خط سوم
در خط چهارم عدد N
و در خط پنجم

خروجی :

شما باید در خروجی دو عدد چاپ کنید - اول عدد S که موقعیت قطار در ایستگاه است به طوری که مجموع فاصله های کمینه ی مسافرین از قطار بیشینه شود ، دوم مقدار بیشنه ی مجموع کمترین فاصله ی مسافران از قطار.

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

ورودی نمونه :

6
2
0 4
2
4

خروجی نمونه :

2 4

 

---

کد ++C