اولین باره که به کاهو میای؟ راهنمای سایت رو حتما بخون!

ورود ثبت‌نام راهنما درباره‌ی کاهو
پرسش‌ها برچسب‌ها کاربر‌ها سوال بپرسید!

آمار پرسش:

  • پرسیده شده: 2015-07-28 21:33:28 -0500
  • مشاهده شده: 303 بار
  • بروز شده: 2016-06-05 09:37:18 -0500

پرسش‌های مشابه:

یافتن کوچکترین پیچ و مهره با مقایسه آنها

آشپزباشی:‌ مرتب کردن پشته با برعکس کردن یک دنباله متوالی از ابتدای آن

دنباله و جادوگر - دوره ی 24 - مرحله ی 2

الگوریتمی برای کمینه کردن تعداد دفعات بازشدن کشوها

الگوریتم محاسبه لگاریتم-سوال مسابقه دانش آموزی صنعتی شریف

آیا گراف قویا همبند است؟

ادغام k آرایه‌ی مرتب شده با بهترین زمان اجرا

سوال آزمون آزمایشی دوره 23

پیدا کردن مولفه های قویا همبند گراف جهت دار

یافتن کوتاه ترین دور در گراف ساده

نکاتی در مورد نوشتن پاسخ:

در این قسمت می‌تونی به یک پرسش پاسخ بدی. اگه می‌خوای در مورد پرسش بحث و اظهار نظر کنی از قسمت «ثبت نظر» استفاده کن.
پاسخت رو دقیق و کامل بنویس، از عکس استفاده کن و اگه لازمه به منابع (کتاب یا سایت) ارجاع بده.
اگه پرسش یا پاسخ‌ها مفید هستند حتما بهشون رای بده تا پرسش‌ها و پاسخ‌های خوب مشخص بشن.

استفاده از ویرایشگر:

توی قسمت پیش‌نمایش می‌تونی ببینی متنی که نوشتی چجوری روی سایت دیده میشه.
خیلی مهم: برای اینکه به خط بعد بری باید دوتا Enter بزنی.
می‌تونی از تگ‌های معمولی و ساده‌ی html هم استفاده کنی.
با دکمه‌هایی که بالای ویرایش‌گر قرار دارند کلی کار می‌شه کرد. از عکس‌گذاشتن بگیر تا لیست شماره‌دار. حتما امتحان‌شون کن.

علائم ریاضی:

برای نوشتن علائم ریاضی می‌تونی از Mathjax استفاده کنی. راهنمای Mathjax رو از سایت math.stackexchange بخون.
برای نوشتن عبارت ریاضی وسط جمله، اون عبارت رو بین دوتا $ قرار بده.
برای نوشتن عبارت ریاضی تو یه خط جدید اون رو بین دوتا $$ قرار بده.

Binary Search سوال 2 : آنتن ها

10

به نام خدا

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

می دانیم که آنتن ها فقط می توانند بر روی خط y = ۰ قرار داده شوند و همچنین شعاع سرویس دهی تمامی آنتن ها باید برابر با هم باشد. از آنجایی که می خواهیم هزینه کمی برای نصب آنتن ها پرداخت کنیم، می خواهیم کمترین R را پیدا کنیم که بتوان با قرار دادن k آنتن به شعاع سرویس دهی R بر روی خط y = ۰ همه مراکز اطلاعاتی را پوشش داد. شما باید برنامه ای بنویسید که با گرفتن اطلاعات مربوط به سوال مقدار کمینه R را به دست آورد.

ورودی

در سطر اول ورودی دو عدد n و k(هر دو کوچکتر مساوی $2*10^5$) به ترتیب نشان دهنده تعداد مراکز اطلاعاتی و تعداد آنتن ها آمده است. در n سطر بعدی در هر سطر دو عدد $x_i$ و $y_i$ (قدر مطلق هردو کوچکتر مساوی 106) به ترتیب آمده است که مختصات مراکز اطلاعاتی را مشخص می کنند. تمام اعداد ورودی صحیح می باشند.

خروجی

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

مثال:

ورودی:

1 2

1 1-

1 1

خر.جی

1.414

ورودی:

2 2

1 1-

1 1

خروجی:

1.000

منبع:دوره انتخاب تیم، دوره 21، روز دوم، سوال 1

Binary_Search الگوریتم دوره-۲۱ دوره-انتخاب-تیم
2015-07-28 21:33:28 -0500
مهدی غ 785 ● 8 ● 13 ● 22
پاک‌کردن   ویرایش سوال
نظرات

وقتی یه همچین سوالایی می بینم که می دونم نه سطح سوالا به من می خوره , نه هیچ ایده ی برای حل سوالا دارم ... و فعلا بهتره بیخیال حل سوال شم , خیلی خوشحال می شم :D

2015-07-28 21:54:28 -0500 تهی نام

سوالی را که نتوان حل کرد، باید +1 داد و بیخیال گشت...!

2015-07-29 04:07:38 -0500 سی پلاس پلاس

اصن مشکل اینجاس که چجوری k تارو بچینیم :|

2015-07-29 14:39:39 -0500 هویج

@هویج جدی !؟؟!!!

2015-07-29 15:55:36 -0500 تهی نام

@تهی نام ، بعله :|

2015-07-31 13:42:41 -0500 هویج

1 پاسخ

1

می آییم روی R باینری سرچ میزنیم.

به ازای یک R خاص میتونیم با (O(nlogn بفهمیم چند نقطه روی خط نیاز داریم. اگر از k کمتر بود با اون R میشه اینکار را کرد.

روش اش اینه که به ازای هر مرکز اطلاعاتی میبینیم چه بازه ای روی خط قابل قبول است.«برای پوشش دادن». سپس این بازه ها رو بر اساس نقطه آغاز سرت میکنیم و از سمت چپ شروع میکنیم , هر بازه ای که تا حالا توش نقطه نذاشتیم ته اون بازه یک نقطه میذاریم .

با این روش چون تعداد بازه ها n است پس اردر ما میشه ((O(nlog(n)log(RMax. اگه جاج داشت کدش رو هم میزدم میذاشتم.

2016-06-05 09:37:18 -0500
یاسین 99 ● 3 ● 7
پاک‌کردن   ویرایش پاسخ

پاسخ شما

فقط در صورتی که پاسخی برای این پرسش دارید، آن را اینجا بنویسید و برای بحث کردن از قسمت «ثبت‌ نظر» استفاده کنید. شما می‌توانید قبل از وارد شدن به سایت پاسخ خود را بنویسید. این پاسخ ذخیره می‌شود و زمانی که شما وارد سایت شدید یا ثبت‌نام کردید منتشر می‌شود.

پیش‌نمایش:

کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر است.