بررسی آزمون عملی ۲

ببخشید یک کم دیر شد سرمون شلوغ بود و وقت نداشتیم.

خب بریم سر آزمون:

سوال 1: اگر همه خونه هایی که عدد های اول با هم تقاطع دارن رو در نظر بگیریم و برای هر کدومشون یه عدد خاص بنویسیم،مسئله خیلی راحت تر می شه.مثلاً اگر تو جدول دوم رقم 4 تا خونه گوشه مربع رو فیکس کنیم.بعدش کافیه حساب کنیم چند تا عدد اول هستند که با یک رقم خاص شروع و با یک رقم خاص دیگه تموم می شن.و این اعداد رو در هم ضرب کنیم.می تونیم با یه پیش پردازش همه این حالت ها رو به دست بیاریم.بعدش کافیه که همه حالت های 4 خونه گوشه مربع رو بررسی کنیم که این تعداد هم زیاد نیست.تو جدول سوم هم دقیقاً با این روش می شه جواب رو به دست اورد.

سوال 2: این سوال با استفاده از الگوریتم داینمایک حل می شه. و داینامیکتون رو باید به این شکل تعریف کنید. d_i,j: کمترین هزینه برای رسیدن به مربع i ام به طوری که با پرش به طول j به آن برسیم.

 برای کسب اطلاعات بیشتر در مورد داینامیک بهویکی شاازززیامراجه کنید. 

سوال 3: می دانیم گوشه n ام این جدول برابر است با n/2+1) * (n/2 + mod 2) +1) و از این طریق می توان A های خواسته شده را به دست آورد.

حال یک گراف وزن دار می سازیم که راس های آن 1 و n و همه ی A و B ها است و به ازای هر AوB یک یال به وزن یک می گذاریم. حال همه ی راس ها را به صورت مرتب شده در یک آرایه نگه می داریم و راس i ام این آرایه را s_iمی گیریم و بین s_iو s_i+1یال به وزن s_{i+1 -} s_i+1 می گذاریم. حال با استفاده از الگوریتمdijkstra طول کوتاهترین مسیر بین راس 1 و n را به دست می آوریم.

صورت سوالات ، تست کیس ها و کد سوالات رو می تونید از اینجادانلودکنید.

این هفته به دلیل برگزاری مسابقه izocup آزمون شاززز نخواهیم داشت.

در کل تعداد شرکت کنندگان در آزمون های عملی خیلی کمه و اگه همینجوری پیش بره آزمون های کمتری برگزار خواهیم کرد (مثلا 1 یا 2 ماه در میان) پس به دوستاتون بگید که شرکت کنن.

جاج این آرمون هم تا این جمعه باز است.

موفق باشید :)

-----------------------------

پ.ن: لینک ها درویکی شاازززیاآپدیت شد و مسائل داینامیک و سوالات المپیاد روسیه به آن اضافه شد.