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

»    مسابقه‌ی برنامه‌نویسی CodeCup 2018

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسئله‌ی انتخابات

مسئله‌ی چراغ راهنمایی - الگوریتمستان
الگوریتمستان
1114.275.00
  »  

       

بررسی سوال مسابقات برنامه‌نویسی Turn for MEGA و راه حل آن

آنچه در این نوشته می‌خوانید:
   •  مسئله‌ی چراغ راهنمایی
       »  مسئله
       »  ورودی برنامه
       »  خروجی برنامه
       »  حل مسئله

مسئله

  [بازگشت به فهرست]

    یک چراغ راهنمایی در مسیر گردش از بزرگراه به یک مرکز فروش بزرگ تعبیه شده است. عملکرد این چراغ به گونه‌ای است که در هر دقیقه حداکثر k خودرو امکان گردش از بزرگراه به سمت مسیر مرکز را دارند. در پایان هفته شهروندان بیشتری برای خرید به این مرکز مراجعه می‌کنند که باعث بالا رفتن حجم ترافیک می‌شود. مدیران مرکز سفارش نصب دوربین ویژه‌ای در نزدیکی آن محل را داده‌اند که امکان شمارش تعداد خودروهای وارد شده از سمت شهر به محل گردش به مرکز فروش را دارد.

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

      

ورودی برنامه

  [بازگشت به فهرست]

خط اول شامل اعداد k و n است که حداکثر خودروهای قابل گذر از چراغ راهنمایی در هر دقیقه و میزان دقایق سپری شده از شروع به کار دوربین را مشخص می‌کنند. خط دوم شامل n عدد a3 ،a2 ،a1، ... و an است. منظور از ai تعداد خودروهای نزدیک شده به محل گردش در دقیقه iام است.

    دوربین نیز کار خود را از صبح آغاز می‌کند که عبور خودروها آغاز می‌شود.

5  3

6  7  2

  

خروجی برنامه

  [بازگشت به فهرست]

تعداد خودروهایی که در حال حاضر پشت چراغ متوقف هستند.

0

      

    منبع: وب سایت Timus Online Judge - مسئله‌ی Turn for MEGA

      

حل مسئله

  [بازگشت به فهرست]

ابتدا نمونه‌ی ارائه شده را بررسی می‌کنیم. در سطر اول ورودی اعداد k = 5 و n = 3 داده شده‌اند. یعنی در هر دقیقه حداکثر 5 خودرو امکان گردش به مسیر مرکز فروش را دارند و 3 دقیقه از زمان شروع مشاهده توسط دوربین می‌گذرد. در این دقایق به ترتیب 5، 7 و 2 خودرو به محل گردش نزدیک شده‌اند. تمامی 5 خودروی دقیقه اول در همان دقیقه از گذر عبور می‌کنند. 5 خودرو از 7 خودروی دقیقه‌ی دوم در دقیقه‌ی دوم گذر کرده و 2 خودرو پشت چراغ منتظر می‌مانند. این 2 خودرو در دقیقه‌ی سوم به همراه 2 خودروی جدید دیگر که به تازگی به آن محل آمده‌اند، به سمت مرکز فروش حرکت می‌کنند. بنابراین در پایان هیچ خودرویی در محل گردش نخواهد بود. به همین دلیل عدد صفر به عنوان خروجی چاپ شده است.

    اگر سطر دوم ورودی به ترتیب زیر باشد:

  

20  0  0

  

    در دقیقه‌ی اول 5 خودرو عبور کرده و 15 خودرو باقی می‌مانند. در دقیقه‌ی دوم 5 خودروی دیگر عبور کرده و 10 خودرو باقی می‌مانند. بالاخره در دقیقه‌ی سوم 5 خودروی دیگر حرکت کرده و تنها 5 خودرو باقی خواهند ماند. به این ترتیب خروجی عدد 5 خواهد بود.

    یک راه حل را می‌توان به این ترتیب مطرح کرد که در هر دقیقه k خودرو امکان عبور دارند. پس در n دقیقه nk خودرو امکان گردش به سمت مرکز فروش را خواهند داشت. اگر این عدد را از مجموع تمام خودروهای وارد شده به محل گذر کم کنیم، تعداد خودروهای باقیمانده مشخص می‌شود. در نمونه‌ی اول 14 خودرو در 3 دقیقه وارد شده‌اند که از مقدار nk = 15 کمتر است. یعنی تمامی خودروها امکان عبور دارند. در نمونه‌ی دوم 20 خودرو وارد گذر شده‌اند که در پایان 5 خودرو باقی می‌ماند. این عدد همان اختلاف 20 و حاصلضرب اعداد k و n است.

    اما مسئله به این سادگی نیست. بر اساس توضیحات بند قبلی، اگر ترتیب اعداد سطر دوم ورودی نمونه عکس شود، خروجی نباید تغییر کند. چرا که مقدار k، n و مجموع خودروهای وارد شده تغییری نکرده است.

  

5  3

2  7  5

  

    در دقیقه‌ی اول 2 خودرو وارد می‌شوند که بدون هیچ مشکلی از گذر عبور می‌کنند. در دقیقه‌ی دوم 7 خودرو وارد می‌شوند که 2 خودرو ناچار به توقف هستند. در دقیقه‌ی سوم این 2 خودرو با 3 خودروی دیگر از 5 خودروی تازه وارد شده از گذر عبور کرده و 2 خودرو در پشت چراغ باقی می‌مانند. پس در انتها عدد خروجی 2 خواهد بود.

    این تناقض از اینجا ناشی می‌شود که زمان ورود خودروها نیز بسیار اهمیت دارد. در حالی که راه حل اولیه تنها تعداد خودروها را مد نظر قرار می‌دهد. چاره‌ی کار ثبت تعداد خودروهای پشت چراغ در انتهای هر دقیقه است.

    اگر در انتهای دقیقه‌ی iام تعداد خودروهای پشت چراغ remi باشد، در دقیقه‌ی (i+1)ام تعداد ai+1 خودرو به آنها اضافه شده و k خودرو کم خواهد شد. پس در انتهای آن دقیقه remi + ai+1 - k خودرو پشت چراغ قرار دارند. این عدد همان remi+1 است. اگر این عدد منفی باشد، به معنی آن است که ظرفیت عبور بیش از تعداد خودروی موجود بوده است. پس هیچ خودرویی پشت چراغ باقی نمانده است. در این حالت هم باید عدد منفی را با صفر جایگزین کنیم. با پیش رفتن مراحل برای هر دقیقه، remn همان خروجی مسئله است. مقدار rem0 نیز همواره صفر است.

    به عنوان مثال در نمونه‌ی اولیه‌ی مسئله:

      

rem1 = rem0 + a1 - k = 0 + 5 - 5 = 0

rem2 = rem1 + a2 - k = 0 + 7 - 5 = 2

rem3 = rem2 + a3 - k = 2 + 2 - 5 = -1 < 0    ,    rem3 = 0

      

    در نمونه‌ی دوم:

      

rem1 = rem0 + a1 - k = 0 + 20 - 5 = 15

rem2 = rem1 + a2 - k = 15 + 0 - 5 = 10

rem3 = rem2 + a3 - k = 10 + 0 - 5 = 5

      

    و در مثال آخر:

      

rem1 = rem0 + a1 - k = 0 + 2 - 5 = -3 < 0    ,    rem1 = 0

rem2 = rem1 + a2 - k = 0 + 7 - 5 = 2

rem3 = rem2 + a3 - k = 2 + 5 - 5 = 2

  


این نوشته آخرین بار در تاریخ جمعه، ۱۱ فروردین ماه ۱۳۹۶ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
        ویدئوهای آموزشی دوره‌ی Algorithms: Design and Analysis دانشگاه استنفورد با زیرنویس انگلیسی
        متن فارسی مسئله‌ی Gholam's Simple Game از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2010‌ منطقه‌ای سایت تهران
        متن فارسی مسئله‌ی Jolly Jumpers از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        متن فارسی مسئله‌ی شماره‌ی 343 از UVa Online Judge، ار سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی
        متن فارسی مسئله‌ی The Trip از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        معرفی کتاب آموزش الکترونیکی رایگان «ساختمان داده‌ها» به زبان فارسی با قابلیت دانلود
        متن فارسی مسئله‌ی 3n+1 Problem (حدس کولاتز یا حدس 3n+1) از سوالات تمرینی کتاب‌های آمادگی مسابقات برنامه‌نویسی و وبسایت UVa Online Judge
        بررسی مسئله‌ی انتخابات، از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2016 سایت تهران
        متن فارسی مسئله‌ی Encrypted SMS از سوالات مسابقه‌ی برنامه‌نویسی ACM-ICPC 2007 منطقه‌ای سایت تهران
        بررسی مسئله‌ی اعداد اردوش (Erdos Numbers) یا فاصله‌ی همکاری اردوش از سوالات آمادگی مسابقات برنامه‌نویسی موجود در کتاب Programming Challenges و وبسایت UVa Online Judge
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» بیتا قانع

دوشنبه، ۲ آبان ماه ۱۳۹۰، ساعت ۲۱:۰۵
سلام خسته نباشید من سوالی داشتم به این مضمون
برای یک 6راه یک چراغ راهنمایی چند زمانه نصب کرده اند الگوریتمی (به روش حریصانه)بنویسیدکه سبز وقرمز بودن و رنگهای دیگر چراغها را طوری مدیریت کند که خطر تصادف حداقل باشد (به طوری که اگر مسیرها را a,b,c,d,e,f  بنامیم مسیرهای b, d,f  یک ظرفه بوده اما مسیر  b,f  به سمت تقاطع یکطرفه و مسیر d  به سمت خارج تقاطع یکطذفه می باشد)

» ارجمند

سه‌شنبه، ۱۲ مهر ماه ۱۳۹۰، ساعت ۱۴:۳۲
سلام خسته نباشید من سوالی داشتم به این مضمون
برای یک 5راه یک چراغ راهنمایی چند زمانه نصب کرده اند الگوریتمی بنویسیدکه سبز وقرمز بودن چراغها را طوری مدیریت کند که خطر تصادف حداقل باشد