خب تو این پست قصد داریم که سوالات امتحان عملی کات برنز اول دوره 24 رو راه حل سوالاتش رو بگیم اگر که
رو سوالات فکر نکردید یا ندیدید سوالات رو اصلا وارد این مطلب نشید
خب لینک سوالات که تو کوئرا هست ایناس :
1- چک برگشتی
ظاهرا امتحان اولشون امتحان گراف بوده و همه سوالا هم همونطور که میبینید گراف بوده.
1- این سوال از معدود سوالات المپیادِ که راه حل سوال تایم بدی داره ولی با تف میتونید اکسپتش کنید راه حل اینه که شما باید به ازای هر کدام از شهر ها در هر روز از t روز یکبار الگوریتم دایسترا (dijkestra) رو اجرا کنید که اردر جالبی نمیده ولی میتونید یه تف خوب بزنید که سوال اکسپت شه اونم اینه که در طول دایسترا زدن موقعی که دارید فاصله یه راس رو آپدیت میکنید اگر فاصلش کمتر مساوی k شد حتما از جوابتون یکی کم کنید. چون که قبل مرحله اول جواب برابر تعداد راس های گرافه و بعدش هی کمتر میشه کد راه سوال هم میتونید از لینک پایین دانلود کنید.
دریافت2- توی این سوال باید اول با چنتا مثال به یه فکتی برسید که در نوبه خودش جالبه اونم اینه که گراف مهندسی ساز میشه اگر و تنها اگر یه دور وجود داشته باشه توی گراف که همه یال های اون یه وزن نداشته باشن و در غیر این صورت هم مهندسی ساز نیست(بازم اثباتش به خودتون واگذار میشه :دی کاری نداره نگران نباشید) پس تا یه جایی گراف مهندسی ساز نیست و از اون به بعد مهندسی سازه پس میتونیم روی جواب باینری سرچ بزنیم و اولین جایی که گراف دارای دور با وزن نابرابر شده رو پیدا کنیم و از قبل اون رو 0 بدیم و بعدش رو هم 1 بدیم و اینجوری مسئله حله.لینک کد همین پایینه:
3-این سوال یه مورد جالبه که واقعا نیازه که یاد بگیرید نکتش واقعا زیباس. باید به این توجه کنید که چرا k تا 5^10ئه. چون که وزن هر یال حداقل 1ئه و فاصله هر دو راسی هم حداقل یه یال هست پس حداقل فاصله دو به دوی رئوس برابر 
هست پس n حتما باید از 500 کمتر باشه!! وگرنه جواب برای n های بزرگتر از 500 قطعا 0ئه خب حالا dp میزنیم دی پی نپ سک میزنیم که احتمالا براتون آشناس که تعریف [dp[i][j میشه اینکه میخوایم از iتا یال اول مقدار هایی برداریم که مجموع یال فاصله دو به دویی رئوس دقیقا j بشه آپدیت dp هم توی کد هست فقط موردی که وجود داره اینه که هر یال رو میتونیم در بیاریم که تو چنتا فاصله دو به دویی هست اونم به این صورت که چون گراف درخته اگه ریشه دارش بکنیم تعداد بار هایی که تو فاصله بین دو راس این یال به کار گرفته شده میشه (اگه سایز زیردرختش رو t بگیریم) برابر با (t * (n-t هست به این ترتیب میشه Dp رو آپدیت کرد. کد هم که موجوده :
