المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله‌ی سوم:دوره‌ی ۲۱:سوال ۳

شجره‌نامه

پس از آن‌که آیدین عجب را گفت، روح خبیس احساس کرد که سؤالش زیادی آسان بوده‎!‎ برای همین سؤال بعدی را مطرح کرد. روح خبیس گفت: ‎

گوش کن ‎آیدین‎ جان، دوست من یعنی روح پلید، در خاندانشان یک شجره‌نامه دارد که تنها افراد مذکر در آن درج شده‌اند. از آن‌جا هم که‌هر روح حداکثر دو فرزند دارد، این‌ شجره‌نامه شکل یک درخت دودویی را گرفته است‎.» روح ادامه داد ‎«به بیان دقیق‌تر در آن خاندان ‎$\Delta$‎ تا روح با شماره‌های ‎۱‎ تا ‎$\Delta$‎ وجود دارد. روح شماره یک ریشه درخت است و پدری ندارد، اما به ازای هر روح با شماره ‎$2 \leq k \leq \Delta$‎، پدر رأس ‎(روح)‎ شماره ‎$k$‎، دقیقاً روح ‎$\lfloor \frac{k}{2} \rfloor$‎ است.

به ازای هر دو رأس ‎$X$‎ و ‎$Y$‎ در این شجره‌نامه، فاصله‌ی فامیلی بین این دو (که آن را با ‎$D(X,Y)$‎ نشان می‌دهیم) برابر با کم‌ترین تعداد یال لازم در کوتاه‌ترین مسیر بین ‎$X$‎ و ‎$Y$‎ است.

روح اعظم اعتقاد داشته که روح‌هایی که شماره‌شان عددی اوّل‌ست، از جادوانگی بالایی برخوردارند و ‎»‎روح جاویدان‎«‎ هستند.

دوست من می‌خواهد حاصل‌ضرب تمام ‎$D(V_1,V_2)$‎ هایی را در این شجره نامه پیدا کند که:‎

  • ‎ اولاً ‎$V_1 < V_2$‎ باشد. ‎
  • ثانیاً ‎$V_1$‎ و ‎$V_2$‎ هر دو جاویدان ‎(اوّل)‎ باشند.
  • ‎ ثالثاً ‎$V_1‎ + ‎V_2‎ + ‎1$‎ نیز جاویدان ‎(اوّل)‎ باشد.

اگر حاصل‌ضرب تمام ‎$D(V_1,V_2)$‎ های دارای ‎۳‎ شرط فوق را ‎$M$‎ بنامیم. ای ‎آیدین‎ عزیز، باقی‌مانده‌ی این ‎$M$‎ بر ‎$\Delta$‎ چند‌ است؟


ابزار صفحه