ماراتن SGU , USACO
پاسخ : ماراتن sgu , usaco
سوال 108 sgu :
برای هر عدد d(n) ، n برابر مجموع ارقام n بعلاوه ی n هست . اگر دو عدد x,y داشته باشیم که d(x)=y اونو قت x یک سازنده ( generator ) برای y هست . به یه عدد میگیم self-number اگه هیچ سازنده ای نداشته باشه .
ورودی :
اعداد N,K و بعدش اعداد s1,s2,...,sk رو میدن . (N<=10[SUP]7[/SUP], 1<=K<=5000)
خروجی :
باید تو خط اول تعداد اعداد self-number از 1 تا n رو چاپ کنید ودر خط بعدی به ازای هر si ، si امین عدد self-number رو چاپ کنید .
_ من خودم این سوال رو اکسپت نکردم !!!!
_ خواهشا اول الگوریتمتون رو بگید !!!!!!!
سوال 108 sgu :
برای هر عدد d(n) ، n برابر مجموع ارقام n بعلاوه ی n هست . اگر دو عدد x,y داشته باشیم که d(x)=y اونو قت x یک سازنده ( generator ) برای y هست . به یه عدد میگیم self-number اگه هیچ سازنده ای نداشته باشه .
ورودی :
اعداد N,K و بعدش اعداد s1,s2,...,sk رو میدن . (N<=10[SUP]7[/SUP], 1<=K<=5000)
خروجی :
باید تو خط اول تعداد اعداد self-number از 1 تا n رو چاپ کنید ودر خط بعدی به ازای هر si ، si امین عدد self-number رو چاپ کنید .
_ من خودم این سوال رو اکسپت نکردم !!!!
_ خواهشا اول الگوریتمتون رو بگید !!!!!!!
پاسخ : ماراتن sgu , usaco
خوب به دلیل مشکوک بودن سوال 108 ، سوال بعدی رو میزارم !!!!!
سوال 259 SGU :
یه مغازه ای (agency !!!!!!!
) داریم که باید N تا نامه پرینت کنه و فقط یه دونه پرینتر دارن !!! زمانی که طول میکشه تا نامه ی i-ام پرینت شه Ti دقیقه طول میکشه و به محض اینکه هر نامه ای پرینت شد ، پیک اون رو به مقصدش میرسونه که برای نامه ی i-ام Li دقیقه طول میکشه (تعداد پیکها نامحدود هستن !) حالا شما باید کمترین زمانی که نیاز هست تا همه ی نامه ها چاپ شن و به مقصدشون برسن رو بگید .
ورودی :
اول N رو میده بعدش تو خط دوم N تا عدد میده که i مین عدد Ti هست و تو خط سوم هم N تا عدد میده که Li ها هستند . (N<=100 , Ti ,Li <=1000)
خروجی :
کمترین زمان لازم برای چاپ همه ی نامه ها و به مقصد رسوندنشون !!!!!!
خوب به دلیل مشکوک بودن سوال 108 ، سوال بعدی رو میزارم !!!!!
سوال 259 SGU :
یه مغازه ای (agency !!!!!!!
) داریم که باید N تا نامه پرینت کنه و فقط یه دونه پرینتر دارن !!! زمانی که طول میکشه تا نامه ی i-ام پرینت شه Ti دقیقه طول میکشه و به محض اینکه هر نامه ای پرینت شد ، پیک اون رو به مقصدش میرسونه که برای نامه ی i-ام Li دقیقه طول میکشه (تعداد پیکها نامحدود هستن !) حالا شما باید کمترین زمانی که نیاز هست تا همه ی نامه ها چاپ شن و به مقصدشون برسن رو بگید .ورودی :
اول N رو میده بعدش تو خط دوم N تا عدد میده که i مین عدد Ti هست و تو خط سوم هم N تا عدد میده که Li ها هستند . (N<=100 , Ti ,Li <=1000)
خروجی :
کمترین زمان لازم برای چاپ همه ی نامه ها و به مقصد رسوندنشون !!!!!!
پاسخ : ماراتن sgu , usaco
کد سوال قبل رو فعلا نزدم !!!! حالا برای اینکه ماراتن عقب نمونه یه سوال میذارم که خودم قبلا اکسپت کردم تا سوال قبلی رو کدش رو اکسپت کنم :167:
سوال 149 SGU :
یه مدرسه ای ابتدای سال ، یه کامپیوتر میخره ! در طول سال n-1 کامپیوتر دیگه میخره که هر کدوم ، با یه کابل به دقیقا یکی از کامپوترهای قبلی وصل هستن . حالا میخوایم برای هر کامپیوتر دورترین کامپیوتر نسبت بهش رو پیدا کنیم . ( یه درخت وزندار میده و برای هر راس ، اندازه ی بلندترین مسیری که از این راس خارج میشه رو میخواد !!!!!!!!!!!! )
ورودی :
اول N رو میده و بعد در N-1 خط بعدی برای کامپیوتر های 2 تا n ام اول شماره ی کامپیوتری که بهش وصل هست رو میگه و بعد طول کابل بین دو تا کامپیوتر ( n<=10000 و مجموع طول کابلها <= 10[SUP]9[/SUP])
خروجی :
در سطر i-ام طول بلندترین مسیری که از راس i-ام شروع میشود
کد سوال قبل رو فعلا نزدم !!!! حالا برای اینکه ماراتن عقب نمونه یه سوال میذارم که خودم قبلا اکسپت کردم تا سوال قبلی رو کدش رو اکسپت کنم
:167: سوال 149 SGU :
یه مدرسه ای ابتدای سال ، یه کامپیوتر میخره ! در طول سال n-1 کامپیوتر دیگه میخره که هر کدوم ، با یه کابل به دقیقا یکی از کامپوترهای قبلی وصل هستن . حالا میخوایم برای هر کامپیوتر دورترین کامپیوتر نسبت بهش رو پیدا کنیم . ( یه درخت وزندار میده و برای هر راس ، اندازه ی بلندترین مسیری که از این راس خارج میشه رو میخواد !!!!!!!!!!!! )
ورودی :
اول N رو میده و بعد در N-1 خط بعدی برای کامپیوتر های 2 تا n ام اول شماره ی کامپیوتری که بهش وصل هست رو میگه و بعد طول کابل بین دو تا کامپیوتر ( n<=10000 و مجموع طول کابلها <= 10[SUP]9[/SUP])
خروجی :
در سطر i-ام طول بلندترین مسیری که از راس i-ام شروع میشود
پاسخ : ماراتن sgu , usaco
خوب به دلیل مشکوک بودن سوال 108 ، سوال بعدی رو میزارم !!!!!
سوال 259 SGU :
یه مغازه ای (agency !!!!!!!) داریم که باید N تا نامه پرینت کنه و فقط یه دونه پرینتر دارن !!! زمانی که طول میکشه تا نامه ی i-ام پرینت شه Ti دقیقه طول میکشه و به محض اینکه هر نامه ای پرینت شد ، پیک اون رو به مقصدش میرسونه که برای نامه ی i-ام Li دقیقه طول میکشه (تعداد پیکها نامحدود هستن !) حالا شما باید کمترین زمانی که نیاز هست تا همه ی نامه ها چاپ شن و به مقصدشون برسن رو بگید .
ورودی :
اول N رو میده بعدش تو خط دوم N تا عدد میده که i مین عدد Ti هست و تو خط سوم هم N تا عدد میده که Li ها هستند . (N<=100 , Ti ,Li <=1000)
خروجی :
کمترین زمان لازم برای چاپ همه ی نامه ها و به مقصد رسوندنشون !!!!!!
خوب منم سوال 259 رو اکسپت کردم !!!! .......... اینم کدم ..... بقیه هم کدهاشون رو بزارن !!! :212:
خوب سوال بعدی هم همون سوال 149 ه !!!!
خوب به دلیل مشکوک بودن سوال 108 ، سوال بعدی رو میزارم !!!!!
سوال 259 SGU :
یه مغازه ای (agency !!!!!!!
) داریم که باید N تا نامه پرینت کنه و فقط یه دونه پرینتر دارن !!! زمانی که طول میکشه تا نامه ی i-ام پرینت شه Ti دقیقه طول میکشه و به محض اینکه هر نامه ای پرینت شد ، پیک اون رو به مقصدش میرسونه که برای نامه ی i-ام Li دقیقه طول میکشه (تعداد پیکها نامحدود هستن !) حالا شما باید کمترین زمانی که نیاز هست تا همه ی نامه ها چاپ شن و به مقصدشون برسن رو بگید .ورودی :
اول N رو میده بعدش تو خط دوم N تا عدد میده که i مین عدد Ti هست و تو خط سوم هم N تا عدد میده که Li ها هستند . (N<=100 , Ti ,Li <=1000)
خروجی :
کمترین زمان لازم برای چاپ همه ی نامه ها و به مقصد رسوندنشون !!!!!!
خوب سوال بعدی هم همون سوال 149 ه !!!!
آخرین ویرایش توسط مدیر
پاسخ : ماراتن sgu , usaco
کسی نظری راجع به این سوال نداره ؟!؟! خوباول سعی کنید الگوریتمش رو پیدا کنید بعد کدش رو بزنید !!!!!!!!
یه راهنمایی :
.
.
.
.
.
.
.
به دو سر قطر(بلندترین مسیر گراف) (که در اینجا گرافمون درخت هست!!!) توجه کنید ! :26::26:
کد سوال قبل رو فعلا نزدم !!!! حالا برای اینکه ماراتن عقب نمونه یه سوال میذارم که خودم قبلا اکسپت کردم تا سوال قبلی رو کدش رو اکسپت کنم :167:
سوال 149 SGU :
یه مدرسه ای ابتدای سال ، یه کامپیوتر میخره ! در طول سال n-1 کامپیوتر دیگه میخره که هر کدوم ، با یه کابل به دقیقا یکی از کامپوترهای قبلی وصل هستن . حالا میخوایم برای هر کامپیوتر دورترین کامپیوتر نسبت بهش رو پیدا کنیم . ( یه درخت وزندار میده و برای هر راس ، اندازه ی بلندترین مسیری که از این راس خارج میشه رو میخواد !!!!!!!!!!!! )
ورودی :
اول N رو میده و بعد در N-1 خط بعدی برای کامپیوتر های 2 تا n ام اول شماره ی کامپیوتری که بهش وصل هست رو میگه و بعد طول کابل بین دو تا کامپیوتر ( n<=10000 و مجموع طول کابلها <= 10[SUP]9[/SUP])
خروجی :
در سطر i-ام طول بلندترین مسیری که از راس i-ام شروع میشود
:167: سوال 149 SGU :
یه مدرسه ای ابتدای سال ، یه کامپیوتر میخره ! در طول سال n-1 کامپیوتر دیگه میخره که هر کدوم ، با یه کابل به دقیقا یکی از کامپوترهای قبلی وصل هستن . حالا میخوایم برای هر کامپیوتر دورترین کامپیوتر نسبت بهش رو پیدا کنیم . ( یه درخت وزندار میده و برای هر راس ، اندازه ی بلندترین مسیری که از این راس خارج میشه رو میخواد !!!!!!!!!!!! )
ورودی :
اول N رو میده و بعد در N-1 خط بعدی برای کامپیوتر های 2 تا n ام اول شماره ی کامپیوتری که بهش وصل هست رو میگه و بعد طول کابل بین دو تا کامپیوتر ( n<=10000 و مجموع طول کابلها <= 10[SUP]9[/SUP])
خروجی :
در سطر i-ام طول بلندترین مسیری که از راس i-ام شروع میشود
یه راهنمایی :
.
.
.
.
.
.
.
به دو سر قطر(بلندترین مسیر گراف) (که در اینجا گرافمون درخت هست!!!) توجه کنید ! :26::26:
آخرین ویرایش توسط مدیر
پاسخ : ماراتن sgu , usaco
راست میگی. خب این کارو می کنیم.
اوّل دو سر قطر رو در نظر می گیریم و خود قطر رو همراه با رووسش تو یه وکتور ذخیره می کنیم. و به هر راس در قطر فاصله اش تا دورترین سر قطر را نسبت می دیم.
بعد روی هر راس dfs می زنیم تا به یه راس توی قطر برسیم.
بعد بیشترین فاصله ی اون راس می شه فاصله اش تا راس v که توی قطر هست+ فاصله راس v تا دور ترین سر قطر که قبلا ذخیره کردیم[HR][/HR]
اگه درسته بگید بشینم کدشو بزنم
راست میگی. خب این کارو می کنیم.
اوّل دو سر قطر رو در نظر می گیریم و خود قطر رو همراه با رووسش تو یه وکتور ذخیره می کنیم. و به هر راس در قطر فاصله اش تا دورترین سر قطر را نسبت می دیم.
بعد روی هر راس dfs می زنیم تا به یه راس توی قطر برسیم.
بعد بیشترین فاصله ی اون راس می شه فاصله اش تا راس v که توی قطر هست+ فاصله راس v تا دور ترین سر قطر که قبلا ذخیره کردیم[HR][/HR]
اگه درسته بگید بشینم کدشو بزنم