سوال 1:
تو این سوال می دونیم که عدد نهایی تو int جا میشه ولی ممکنه وسطش overflow بشه برای این که بتونیم این عدد گنده رو ذخیره کنیم استفاده از bignum مناسب نیست چون اگر برای هر رقم یک بایت هم فضا اشغال بشه حدود 4 ترابایت فضا نیازه!!!
راه حلی که می خواستیم شما بهش برسید این بود که تجزیه این عدد به عوامل اولش رو نگه دارید که خب خیلی هاتون هم بهش رسیدید.ولی نکته اصلیش این بود که پیدا کردن عوامل عدد رو با رادیکال گرفتن از عدد و ... پیاده سازی نکنید.به جای این کار می تونید از الگوریتم
غربال اراتستن استفاده کنید که زمان خیلی کمتری مصرف می کنه.خیلی از افراد همینطوری پیاده سازی کردن واسه همین دیگه کد غربال رو نمی ذاریم می تونید از تو scoreboard کد های مختلف رو نگاه کنید.
راه حل دوم:اگر x رو جواب نهایی فرض کنیم می دونیمx>0 و x<10^9 پس می تونیم بگیم:
x%(1000000009)=x
خب حالا می تونیم همه عملیات هامون رو mod این عدد انجام بدیم.از اونجایی که این عدد اول هستش و همه اعداد ورودی ازش کوچیکترن موقع تقسیم می تونیم از
قضیه کوچک فرما استفاده کنیم که تو پست های قبلی توضیح داده بودیم در موردش.
این راه حل از غربال خیلی سریعتر بود!
در مورد تست ها:
تست 1:اگر با همون ترتیب ورودی ضرب و تقسیم عادی انجام میدادید کار می کرد!
تست 2:مثل تست 1 فقط باید تو long long جواب رو ضرب و تقسیم می کردید
تست 3:اگر رادیکالی تجزیه می کردید نمره اش رو می گرفتید
تست 4:یه خورده باید همون رادیکالتون رو بهینه سازی می کردید
تست 5:می تونستید یه جوری ضرب و تقسیم کنید که overflow نشه.مثلاً اگه ضرب جواب فعلی در هر عددی باعث overflow بشه حتماً یه عددی وجود داره که می شه بهش تقسیم بشه و دوباره جوابمون کوچیکتر بشه.
تست 6-10:از اینجا دیگه تست ها سخت می شد و کد هایی رادیکالی به سختی accept می شدن.
سوال 2:
ایده مشترک دو قسمت سوال این بود که پاره خط ها رو بر حسب ارتفاع یه سمت ثابت مرتب کنید.پس از این بعد فرض می کنیم پاره خط i ام ارتفاع سمت چپش از پاره خط j ام بیشتره اگر و تنها اگر i>j. همچین [h[i رو ارتفاع سمت راست پاره خط i ام فرض می کنیم.
قسمت اول:شرط لازم و کافی برای این که پاره خط iوj با هم تقاطع داشته باشن با فرض این که j>i هستش اینه که [h[j کوچکتر از [h[i باشه.
قسمت دوم:یه مجموعه که خاصیت گفته شده رو داره در نظر بگیرید.پاره خطی که سمت چپش از همه پایین تره سمت راستش باید از همه بالاتر باشه در غیر اینصورت با همه پاره خط های دیگه تقاطع نداره.با استفاده از همین ایده می تونید ثابت کنید که جواب بزرگترین زیردنباله نزولی تو آرایه h هستش.بزرگترین زیر دنباله نزولی یا صعودی یه مسئله خیلی معروف هستش که راه حلش رو می تونید از
اینجا ببینید.
سوال 3:
در این سوال یک گراف به ما داده شده است و می خواهیم کمترین تعداد یال را حذف کنیم تا راس های 1 تا k در هیچ دوری نباشند.
ابتدا همه ی یال های گراف مثل v-u که u>k , v>k را در نظر می گیریم (می شه به راحتی اثبات کرد که این یال ها در یکی از جواب های مسئله وجود دارند). هر مولفه ی گراف درست شده را یک راس بگیریم یال های باقی مانده (یال هایی که حداقل یکسرشان از این k راس است) باید یک جنگل تشکیل دهند در غیر این صورت یکی از این k راس در یک دور می افتد. به هر صورتی که این یال ها را انتخاب کنیم تا گراف جنگل بماند به یک جواب بهینه می رسیم. برای این کار هم می توان از الگوریتم dsu استفاده کرد.
پیاده سازی ای سوال رو هم می تونید از اینجا دانلود کنید.
اینجا وبلاگ آزاد المپیاد کامپیوتره! ;)