Tutorial آزمون عمل اول

دراین پست قراره راه حل سوالای آزمون عملی جمعه رو بررسی کینم.

اِسپویلِر آلِرت ( فارسیش خطر لوث شدن ) : به کسانی که سوالای آزمون رو ندیدن توصیه می شه که سوالا رو نسوزونن و به صورت مجازی ( تا جمعه ) تو کانتست شرکت کنن!

سوال A :

لم 1 : تعداد پنج ها در تجزیه این عدد از تعداد دو ها کمتر است. پس کافیست تعداد پنج ها را بیابیم.

حال کافیست به ازای هر i از 1 تا n  ، تعداد پنج های !i را بیابیم. این مقدار نیز برابرست با :

i / 5 + i / 25 + i / 125 + ...

در تمامی تقسیم ها کف گرفته می شود. پیچیدگی زمانی : O(nlogn) a

این سوال یه راه با پیچیدگی زمانی O(logn) a هم دارد که برای گرفتن نمره 100 لازم نبود.

سوال B :

لم 1 : x ^ x = 0

لم 2 : a ^ (b ^ c) = (a ^ b) ^ c

با استفاده از این دو لم می توان دید که هر عددی که زوج بار آمده تاثیری بر ایکس اور ندارد و ایکس اور تمام اعداد آرایه برابر با عددی است که فرد بار آمده. پیچیدگی زمانی : O(n) a

سوال C :

ابتدا فرض کنید گشتمان باید بسته باشد. در اینصورت برای دیدن m راس ، 2m-2 حرکت لازم است.

حال که مجبور نیستیم گشت بسته ای طی کنیم ، زمانی که m راس را می بینیم کارمان تمام می شود ؛ بدین معنا که تعداد حرکات 2m-2-d است که d فاصله ی بین راس شروع و پایانی است. حال ما میخواهیم d را بیشینه کنیم ، پس دو سر قطر را به عنوان شروع و پایان گشت انتخاب میکنیم.

برای پیدا کردن قطر هم کافیست دورترین راس نسبت به دورترین راس نسبت به یه راس رو پیدا کنیم! پیچیدگی زمانی : O(n) a

سوال D :

درخت را از یک راس ریشه دار کنید. حال پایینترین مسیر به طول k را در نظر بگیرید (منظور از پایینترین ، مسیری است که راس با کمینه ارتفاع در آن ، بیشینه ارتفاع ممکن را داشته باشد). ادعا میکنیم که جواب بهینه ای وجود دارد که این مسیر را شامل می شود. چرا که در غیر اینضورت مسیری است که با این مسیر اشتراک دارد.

آن مسیر را حذف کرده و این مسیر را اضافه میکنیم. در نتیجه جوابمان همچنان بهینه می  ماند. پس کافیست از پایین به بالا هر گاه که میتوانستیم مسیر k تایی انتخاب کنیم. پیچیدگی زمانی : O(n) a

سوال E :

ابتدا فرض کنید جایگشت ورودی n n-1 n-2 ... 1 است. dp_i را جواب برای n = i میگداریم. حال جایگشت هایی را در نظر بگیرید که عدد j در اول آنهاست. در بین این جایگشت ها j ثابت است و سایر i-1 عدد دیگر جا به جا می شوند. پس عملا dp_i-1 حرکت لازم است. به راحتی نیز می توان دید تعداد حرکت لازم برای تیز کردن جایگشت j, i, i -1, i-2, ... 1 برابر با سقف i/2 است. پس : dp_i = dp_i-1 * i + (i - 1) * i/2.

حال برای حل حالت کلی : فیکس میکنیم که چه پیشوندی از جایگشت ورودی با جایگشت فعلی مان برابر است ( ابتدا جایگشتمان همانی است ). این مقدار را i می نامیم. حال برای اینکه i +1 امین عدد جایگشت ها هم برابر شود c * (dp_n-i-1 + (n-i)/2) a  حرکت لازم است (در تقسیم سقف گرفته می شود) که c برابر با تعداد اعداد کمتر از P_{i + 1} در میان n-i آعدد آخر جایگشت است. پیچیدگی زمانی : O(nlogn) a

نویسنده : کسری مظاهری