تئوری سوم

به نام خدا!

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

________________________________________________________________________________________________________________________________________________________________

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

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

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

________________________________________________________________________________________________________________________________________________________________

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

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

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

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

________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

________________________________________________________________________________________________________________________________________________________________

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

خوش باشید!