آزمون شاز تشریحی 2 المپیاد کامپیوتر سال 1391

از shaazzz
پرش به ناوبری پرش به جستجو

سوالات[ویرایش]

سوال ۱[ویرایش]

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

سوال ۲[ویرایش]

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

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

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

سوال ۳[ویرایش]

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

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

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

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

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