سوال ۸ . «برنامه نویسی»
چهارشنبه, ۸ آذر ۱۳۹۱، ۱۰:۴۹ ب.ظ
مسیری به طول L وجود دارد . n نفر از ابتدای مسیر شروع کرده و با سرعتی به انتهای آن می روند. نفر i ام در زمان ti با سرعت vi شروع به حرکت کرده و به انتهای مسیر می رود. اگر دو نفر در طول مسیر لحظه ای کنار هم قرار بگیرند با هم دوست می شوند. بیشترین تعداد افراد دو به دو با هم دوست را پیدا کنید. N<= 103
راهنمایی در ادامه مطلب...
درخت دوستی افراد را طوری تشکیل میدهیم که اگر فرد i از فرد j دیرتر شروع به حرکت کند ولی زود تر از آن به پایان مسیر برسد راس i را با یال جهت دار به راس j وصل می کنیم. این درخت یک دگ است. حال بزرگترین خوشه را در آن بیابید.
- ۹۱/۰۹/۰۸