شاززز

شاززز

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

بایگانی

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 است. dpi را جواب برای n = i میگداریم. حال جایگشت هایی را در نظر بگیرید که عدد j در اول آنهاست. در بین این جایگشت ها j ثابت است و سایر i-1 عدد دیگر جا به جا می شوند. پس عملا dpi-1 حرکت لازم است. به راحتی نیز می توان دید تعداد حرکت لازم برای تیز کردن جایگشت j, i, i -1, i-2, ... 1 برابر با سقف i/2 است. پس : dpi = dpi-1 * i + (i - 1) * i/2.
حال برای حل حالت کلی : فیکس میکنیم که چه پیشوندی از جایگشت ورودی با جایگشت فعلی مان برابر است ( ابتدا جایگشتمان همانی است ). این مقدار را i می نامیم. حال برای اینکه i +1 امین عدد جایگشت ها هم برابر شود c * (dpn-i-1 + (n-i)/2) حرکت لازم است (در تقسیم سقف گرفته می شود) که c برابر با تعداد اعداد کمتر از Pi + 1 در میان n-i آعدد آخر جایگشت است. پیچیدگی زمانی : O(nlogn) a

نویسنده : کسری مظاهری
  • ۹۷/۰۹/۱۹
  • طلاهای دوره ۲۸

نظرات  (۴)

kheili khob bood dametoon gaaaaarrrrrrmmmmm
Bazam bezarin
اایول. کوتاه و قابل فهم بود.
امتحان خیلی خوبی بود؛ شاز معمولا امتحان با سطح منطقی کم برگزار میکنه :|
اگه بتونید بازم ازمون عملی برامون بذارید خیلی خوب میشه
سلام چ, نمیشه صورت سوالا رو برای کسایی که نتونستن آزمونو بدن بزارین؟|
پاسخ:
هنوزم میتونین آزمونو بدین. تا جمعه قسمت غیر رسمیشو تمدید کردیم!
اما سوالا رو هم با جواب هاش اضافه کردم تو اخر قسمت امتحانات و سوالات. اونجا برین میتونین دانلودش کنین!
  • یه آدم خسته
  • سلام،
    جاداره اول تبریک بگم، این سرعت از آپلود جوابا تو شاززز بی سابقست :) 3> 3>
    آقا دمتون گرم بابت جوابا، دو تا نکته فقط:‌
    اول بگم که یه هم معنی (~بی معنی :) ) برای اسپویلر الرت تو ویکی پیدیا دیدم «خطر لوث شدن»‌،‌ که گویا فارسی همون اسپویلر الرته (حالا بماند که اصن ویکی پیدیا منبع درستی برای این نتیجه گیری من نیست) ولی اگه حال کردین از «خطر لوث شدن»‌ هم میشه استفاده کرد
    بعد نکته دوم اینکه در رابطه با سوال F میشه هینتی چیزی بزارین؟ واقعا حسش نیست اینقد روش فک کنم تا حل شه
    پاسخ:
    سلام. ممنون:)
    ۱. ادیت شد!
    ۲. میتونی فرض کنی به عنوان تکلیف خواستیم خودتون روش فک کنین:D

    ارسال نظر

    ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
    شما میتوانید از این تگهای html استفاده کنید:
    <b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
    تجدید کد امنیتی