شاززز

شما در حال مشاهده بلاگ قدیمی شاززز هستین! سایت جدید به آدرس shaazzz.ir در دسترسه.
شاززز

اینجا وبسایت آزاد المپیاد کامپیوتره! ;)
واسه ی همه ی سطوح از تازه کارها تا طلای جهانی!

طبقه بندی موضوعی
بایگانی

۲ مطلب در دی ۱۳۹۱ ثبت شده است

۰۹
دی
سلام خدمت شما دوستان گرامی. خوش‌حالم از این که در خدمت شما هستم. :)

برای چند‌تا از سوال‌های سری ۱ و ۲ تمرین‌ها یه خرده راهنمایی‌ای آماده کردیم. تا اگه با حل کردن سوالا مشکل داشتید کمکتون کنه.

راه حل‌هایی که سبحان آماده کرده

راه حل‌هایی که دانیال آماده کرده

و این هم من آماده کردم D:

تعداد مثبتی از سوال‌ها هم بدون راهنمایی موندن که اگه فرصت شد اونا رو هم اضافه می‌کنیم.

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

خوب دیگه، من برم بخوابم D:

شاد باشید :)

  • شااززز منگولیا
۰۲
دی
به نام خدا!

سلام! خوبین؟ دیدین دنیا نابود نشد؟ :-| ! ببخشین که یکم دیر شد. خب این دفه هم 3 تا سوال قراره بهتون بدیم که به ترتیب سختی اند. سوال دو و سه هم الگوریتمی هستش. سوال 3 هم از یک سوال codeforces طرح شده و عملا همون سوال هست :دی !!!  سوالا رو لطفا کامل بخونین.

________________________________________________________________________________________________________________________________________________________________

سوال اول : تطابق

 افشینیک گراف 2n راسی و n2+1  یالی رابه علی می دهد. پس از یک ماه بررسی علی به افشین می گوید که این گراف دقیقا یک تطابق (مچینگ) کامل دارد . ثابت کنیدعلیدروغ گفته است.

(یک تطابق کامل از گراف یک زیرگراف از گراف اصلی با تمام راس ها است که در آن درجه همه رئوس 1 باشد . )

________________________________________________________________________________________________________________________________________________________________

سوال دوم : فرار رویایی

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

دزد پس از سرقت بانک متوجه می شود که k پلیس درتعدادی تقاطع قرار گرفتهاندو قصد دستگیری او را دارند (دزد از موقعیت پلیس ها مطلع است). h تقاطع از n تقاطع شهر به اتوبان راه دارد که دزد پس از رسیدن به آن جا می تواند از دستپلیس ها بگریزد . دزد می خواهد کمترین سرعت (سرعت ماشین عددی صحیح مثبت است  و کمتر یا مساوی 2k) را برای ماشین خود تعیین کند که بتواند از دست پلیس ها بگریزد . (اگر در یک لحظه دزد با یکی از پلیس ها در یک تقاطع یا در یک نقطه از خیابان قرار بگیرد دستگیر می شود)

الگوریتمیازاردرn2kبدهید که کمترین سرعت ممکن را بدست آورد یا اعلام کنید که فرار ممکن نیست.


________________________________________________________________________________________________________________________________________________________________

سوال سوم: آقای ایکسو گراف خود خواه

آقای ایکس یک گرافباnراس دارد.آقایزد دوست آقای ایکس است. او برای گراف آقای ایکس n یالبا خود آوردهاست و این یال ها را به ترتیب به آقای ایکس میدهد.میدانیم اگر آقای ایکس یال شمارهی i ام را نخواهدبایدBiریالهزینه بدهدو همچنین اگر یال شماره ی i را خواست بایدAi ریال هزینه متقبل شود.همچنین میدانیم که k تا از یال ها وضعیتشان معلوم شده استو آقای ایکس حق انتخاب در خریدن یا نخریدن آن یال ها راندارد.

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

هدف آقای ایکس این است که با کمترین هزینه کاری کند که گرافش نابود نشودو اگر راهی برای نابود نشدن گراف وجود ندارد آقای ایکس اظهار ناتوانی کند.

الگوریتمی از اردر n lg nبدهید که هدف آقای ایکس را برآوردهکند.

گراف متناظر :گراف متشکل از یال هایانتخاب نشده را گراف متناظر مینامیم.


________________________________________________________________________________________________________________________________________________________________

سینه خواهم شرحه شرحه از فراق    تا بگویمشرحدرد اشتیاق

خوش باشید!

  • شااززز منگولیا