المپدیا

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

ابزار کاربر

ابزار سایت


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

DNAمنو پس بدین

آیدین‎ باز هم جواب درست داد‎ رستم که به تنگ آمده بود با خودش گفت ‎«این بچه حکماً نابغه‌ست. حالا المپیادی نبوده که نبوده، مهم اینه که این همه بلده مسئله حل کنه. غلط نکنم باید DNA$‎$ این رو استخراج کنیم و ببینیم چی داره که این بچه این قدر باهوشه.»‎ با همین ذهنیت ناگهان یک گونی از جیبش در آورد و روی ‎آیدین‎ کشید و ‎آیدین‎‎ را روی کولش انداخت و به آزمایشگاه تحقیقاتی برد.

رستم ‎آیدین‎ به آزمایشگاه رفت و گونی حاوی ‎آیدین‎‎ را به انبار برد و در گوشه‌ای او را رها کرد. بعد از خروج رستم از انبار، ‎آیدین‎ با دندان‌های تیزش‎‎(آیدین‎‎ هر شب مسواک می‌زده‎‎) گونی را شکافت. و به جستجو در انبار پرداخت.

انبار از ‎۳۶‎ اتاقک مربع شکل به صورت شکل سمت چپ تشکیل شده بود. در تقاطع راهروها، یعنی ‎۲۵‎ تا چهارراه موجود در شکل هم تعدادی جنازه افتاده بود که معلوم بود این وسط‌ها (در چهارراهی ها) موجودات را می‌بندند و DNA$‎$ شان را تا قطره آخر از وجودشان می‌کشند بیرون.

‎آیدین‎ می‌داند که ‎DNA$‎$ از چهار پروتئین با حروف اختصاری ‎$A$‎ و $C‎$ و $‎$T‎ و $‎$G‎ تشکیل شده است و برای ساخت مجدد آن به این ‎۴‎ عنصر نیاز است. از همین رو، تصمیم می‌گیرد در هر کدام از ‎۳۶‎ اتاق یکی از این پروتئین‌ها را قرار دهد تا درصورتی که ‎$DNA$‎ش را کشیدند، بتوانند همانجا سر چهارراه، از هر یک از ‎۴‎ اتاقک یکی از پروتئین‌ها را برداشته و به هم بچسباند و خودش را احیا کند. به بیان دیگر، او می‌خواهد در هر یک از ‎۳۶‎ خانه‌ی جدول روبه‌رو حروف ‎$A$‎ یا $‎$C‎ یا ‎$T$‎ یا ‎G$‎$ را طوری بنویسد که در هر مربع ‎$2\times2$‎ هر ‎۴‎ حرف آمده باشند.

خوشبختانه یا متأسفانه در ‎۵‎ تا از اتاقک‌های این انبار پروتئین‌هایی از قبل قرار گرفته‌ند. در این شرایط آیدین می‌خواهد بداند به چند روش می‌تواند در ‎۳۱‎ خانه‌ی باقی‌مانده، پروتئین‌هایی قرار بدهد تا شرط خواسته شده ارضا بشود. اگر تعداد روش‌های انجام این‌کار ‎$C$‎ باشد، باقی‌مانده‌ی تقسیم ‎$C$‎ بر ‎$\Delta^2$ (دلتا به توان ‎۲) چند است؟

پاسخ‌ ارائه شده در این سوال با فرض $\Delta = 28813$ محاسبه شده است.

پاسخ

2


ابزار صفحه