V0RTEX
شنبه 11 دی 1389, 22:02 عصر
Surroundedمحدودیت زمان پردازش: 1000 میلیثانیه
محدودیت حافظه: 1024 کیلوبایت
محاصره
چند روز پیش به حاکم کپکآباد خبر رسید که همسایهی جنوبی قصد حمله دارد. کپکآبادیها به دستور او دیوار بلند و مرتفعی در ضلع جنوبی شهر ساختند و نیروهای خودی در نقاط مختلف شهر مستقر شدند. آنها امروز متوجه شدند که تانکهای دشمن به پشت دیوار رسیده و از آنجا که قصد نفوذ دارند باید هر چه سریعتر نابودشان کرد.
http://ispc.schoolnet.ir/sites/ispc/files/u12/problem8-fig1.png
نخبگان کپکی یک موشک زمین به زمین طراحی کردهاند که شعاع انفجار آن با تعیین میزان مواد منفجره، به هر اندازه قابل تنظیم است. آنها میخواهند با پرتاب فقط یک موشک وبدون آسیب رساندن به نیروهای خودی بیشترین تانک دشمن را نابود کنند. تعداد این تانکها را به دست آورید.
در نظر داشته باشید که به علت بلندی دیوار قادر به نشانه گرفتن بعد از دیوار نیستند.
تانکها و دیوار شهر قطر ندارند. همچنین دیوار شهر مماس بر تانکهای دشمن است. اگر موشک مماس بر تانکهای خودی هم شود باز هم منهدم میشوند. ساختار ورودی:
در خط اول دو عدد N (تعداد تانکهای دشمن) و سپس M (تعداد تانکهای خودی) داده میشود. (۱≤N,M≤۱۰۰۰)
در خط دوم N عدد XBi داده میشود که مختصات مکان تانکهای دشمن است. تانکهای دشمن روی محور X قرار دارد. پس مؤلفهی Y همگی آنها صفر خواهد بود.
در خط سوم و چهارم در هر خط به ترتیب XRj و YRj داده میشود که مختصات مکان نیرو های خودی است.
(-۱۰۸≤XBi, XRj≤۱۰۸, ۰<YRj≤۱۰۸, ۱≤i≤N, ۱≤j≤M) ساختار خروجی:
یک عدد K که بیشترین تعداد ممکن تانک منهدم شده است را در بنویسید.
ورودی نمونه:
7 3
5 17 -5 -4 1 -1 8
7 -2 10
3 1 5
خروجی نمونه:
4
این مسئله مسابقات دانش آموزی بخش پیش رفته بود که تموم شد
http://algorithms.ir/arbiter
حالا می تونید بگید جوابش چی میشه؟
آقای مدیر می بینی که برای کار دانشگاهی و این جور چیز ها نیست پس حذفش نکن بزار یک چیزی یاد بگیرم
محدودیت حافظه: 1024 کیلوبایت
محاصره
چند روز پیش به حاکم کپکآباد خبر رسید که همسایهی جنوبی قصد حمله دارد. کپکآبادیها به دستور او دیوار بلند و مرتفعی در ضلع جنوبی شهر ساختند و نیروهای خودی در نقاط مختلف شهر مستقر شدند. آنها امروز متوجه شدند که تانکهای دشمن به پشت دیوار رسیده و از آنجا که قصد نفوذ دارند باید هر چه سریعتر نابودشان کرد.
http://ispc.schoolnet.ir/sites/ispc/files/u12/problem8-fig1.png
نخبگان کپکی یک موشک زمین به زمین طراحی کردهاند که شعاع انفجار آن با تعیین میزان مواد منفجره، به هر اندازه قابل تنظیم است. آنها میخواهند با پرتاب فقط یک موشک وبدون آسیب رساندن به نیروهای خودی بیشترین تانک دشمن را نابود کنند. تعداد این تانکها را به دست آورید.
در نظر داشته باشید که به علت بلندی دیوار قادر به نشانه گرفتن بعد از دیوار نیستند.
تانکها و دیوار شهر قطر ندارند. همچنین دیوار شهر مماس بر تانکهای دشمن است. اگر موشک مماس بر تانکهای خودی هم شود باز هم منهدم میشوند. ساختار ورودی:
در خط اول دو عدد N (تعداد تانکهای دشمن) و سپس M (تعداد تانکهای خودی) داده میشود. (۱≤N,M≤۱۰۰۰)
در خط دوم N عدد XBi داده میشود که مختصات مکان تانکهای دشمن است. تانکهای دشمن روی محور X قرار دارد. پس مؤلفهی Y همگی آنها صفر خواهد بود.
در خط سوم و چهارم در هر خط به ترتیب XRj و YRj داده میشود که مختصات مکان نیرو های خودی است.
(-۱۰۸≤XBi, XRj≤۱۰۸, ۰<YRj≤۱۰۸, ۱≤i≤N, ۱≤j≤M) ساختار خروجی:
یک عدد K که بیشترین تعداد ممکن تانک منهدم شده است را در بنویسید.
ورودی نمونه:
7 3
5 17 -5 -4 1 -1 8
7 -2 10
3 1 5
خروجی نمونه:
4
این مسئله مسابقات دانش آموزی بخش پیش رفته بود که تموم شد
http://algorithms.ir/arbiter
حالا می تونید بگید جوابش چی میشه؟
آقای مدیر می بینی که برای کار دانشگاهی و این جور چیز ها نیست پس حذفش نکن بزار یک چیزی یاد بگیرم