لینکهای مفید برای شرکت در مسابقه:
میتوانید سوالهای خود را از بخش «سوال بپرسید» مطرح کنید.
نمره دهی سوالات ۱ تا ۶ به صورت ۰ یا ۱۰۰ است.
نمرهدهی سوال ۷ «لامپها در جدول» برحسب تعداد تستهای درست دریافتی است.
یک گراف ساده و همبند راسی و یالی داریم. میخواهیم روی هر راس این گراف یک عدد از مجموعه بنویسیم.
اگر عدد نوشته شده روی راس را با و طول کوتاه ترین مسیر بین دو راس و را با نشان دهیم.
میخواهیم این عدد گذاری به گونهای انجام شود که برای هر دو راس از این گراف مثل و داشته باشیم.
از شما میخواهیم تعداد روشهای انجام این کار را مشخص کنید. از آنجایی که پاسخ مسئله میتواند خیلی بزرگ باشد باقیمانده پاسخ مسئله را بر را چاپ کنید.
خط اول ورودی به ترتیب سه عدد و و با فاصله از هم آمدهاند.
در خط بعدی و در هر خط دو عدد و با فاصله از هم آمدهاند که نشاندهندهی یالی بین دو رأس و هستند.
تضمین میشود گراف ورودی، گرافی ساده و همبند است.
اگر عدد نوشته شده روی راس شماره را با نشان دهیم؛ ۴ روش زیر برای این عدد گذاری وجود دارد.
در گراف بالا هیچ عدد گذاری قابل قبولی وجود ندارد، چون به ازای هر عددگذاری حداقل دو راس مجاور وجود دارد که عدد نوشته شده روی آنها یکسان خواهند داشت و این با خواسته سوال تناقض دارد.