المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۹:سوال ۵

Mahjong

آقای غول‌شناس دانشجوی کارشناسی رشته‌ی باستان‌شناسی است. غول‌شناس‌ها جد اندر جد در زمینه‌ی غول‌شناسی در ایران باستان تحقیق می‌کرده‌اند و از همین جهت مامور ثبت احوال این نام‌خانوادگی را برایشان انتخاب کرده بود. غول‌شناس اطلاعات زیادی در مورد غول‌های ایران باستان دارد. اما در مورد زمانی که هر کدام از غول‌ها در ایران زندگی می‌کرده‌اند اطلاعی در دست ندارد. تنها منبع اطلاعاتی او طومارهایی است به زبانی بسیار عجیب که احتمالا توسط خانواده‌ی اجداد غول‌شناس نوشته‌ شده است. هر عضوی از خانواده یک طومار درست کرده است. در هر طومار فرد غول‌شناسی که طومار را می‌نوشته، به ترتیب نام غول‌هایی که به دنیا می‌آمده بودند و او از آن‌ها خوشش می‌آمده را می‌نوشته. در صورتی که چند غول هم‌زمان به دنیا می‌آمدند، هر غول‌شناس به هر ترتیبی ممکن بود نام آن‌ها را ثبت کند.

آقای غول‌شناس به عنوان پایان‌نامه می‌خواهد کاری بسیار شگرف و بر اساس منابع خانوادگی خود انجام دهد. او می‌خواهد تعدادی غول را پیدا کند که هم‌زمان به دنیا آمده‌اند. بدین ترتیب او می‌تواند تحول بزرگی در غول‌شناسی و تاریخ ایران ایجاد کند زیرا که نشان داده است که تعداد غول‌های ایران باستان به مراتب بیش از آن‌چیزی است که تا به حال تصور می‌شده.‎

آقای غول‌شناس برای اینکه تحول مورد نظر خود را در علم ایجاد کند می‌خواهد روابطی را در طومارها پیدا کند. او فهمیده است که وقتی نام یک غول مثل ‎«خول»‎ بعد از نام غول دیگری مانند ‎«بختک»‎ در یکی از طومارها بیاید یعنی خول یا بعد و یا هم‌زمان با بختک به دنیا آمده‌است. از آن‌جایی که نام هیچ دو غولی در تاریخ مشابه نیست، تنها کافی است او یک دور در این طومارها پیدا کند، یعنی یک سری غول در طومارهای مختلف پیدا کند که هر کدام بعد یا هم‌زمان با دیگری به دنیا آمده باشند، و غول آخری همان غول اولی باشد. از آن‌جایی که پایان‌نامه‌اش باید ساده باشد، نمی‌تواند به یک طومار بیش از یک بار استناد کند، یعنی باید از تعدادی طومار یک زیررشته‌ی متوالی انتخاب کند به صورتی که آخرین غول رشته‌ی هر طومار با اولین غول رشته‌ی طومار بعدی برابر باشد و آخرین غول رشته‌ی آخرین طومار با اولین غول رشته‌ی اولین طومار نیز برابر باشد.

فرض کنید آقای غول‌شناس ‎$n$‎ طومار دارد و ‎$j$‎امین غول در ‎$i$‎امین طومار را با ‎$g_i[j]$‎ نشان بدهیم. او می‌خواهد تعدادی سه‌تایی به شکل ‎$(l_k‎, ‎a_k‎, ‎b_k)$‎ پیدا کند که از طومار ‎$l_k$‎ غول ‎$b_k$‎ام هم‌نام با غول ‎$a_{k+1}$‎ام از طومار ‎$l_{k+1}$‎ام می‌باشد (البته به‌جز برای آخرین سه‌تایی). هم‌چنین اگر این سه‌تایی‌ها ‎$m$‎ تا باشند غول ‎$b_m$‎ از طومار ‎$l_m$‎ با غول ‎$a_1$‎ از طومار ‎$l_1$‎ هم‌نام باشند. توجه کنید که ‎$a_k$‎ باید از ‎$b_k$‎ کوچک‌تر باشند.

شما باید با داشتن طومارها، سه‌تایی‌های مورد نظر آقای غول‌شناس را پیدا کنید و در خروجی چاپ کنید.

ورودی

  • سطر اول ورودی شامل یک عدد ‎$n$‎ می‌باشد.
  • در هر یک از ‎$n$‎ سطر بعدی مشخصات یک طومار آمده است، در سطر ‎$i$‎ام نخست طول طومار ‎$i$‎ام و سپس نام غول‌های نوشته شده در طومار ‎$i$‎ام که با یک فاصله از هم جدا شده‌اند، آمده‌است.
  • تعداد طومارها حداکثربرابر با ‎$1000$‎ می‌باشد. ‎($1\leq n\leq 1,000$)‎
  • تعداد مجموع نام غول‌هایی که در طومارها آمده حداکثر برابر با ‎$200,000$‎ می‌باشد.
  • نام هر غول به صورت رشته‌ای از حروف کوچک الفبای انگلیسی و به طول حداکثر ‎۵‎ برای شما ترجمه شده است.
  • فرض کنید طومارهای خانوادگی آقای غول‌شناس به صورتی هست که می‌تواند حتما سه‌تایی‌های مدنظرش را پیدا کرد.
  • چون قرار بود پایان‌نامه‌ی آقای غول‌شناس ساده باشد، نباید در خروجی ‎$l_i$‎ها تکراری باشند.

خروجی

  • شما در خروجی نخست عدد ‎$m$ (تعداد سه‌تایی‌هایی که یافته‌اید) را در یک سطر بنویسید.
  • سپس در ‎$m$‎ سطر بعدی مقدار سه تایی‌ها را با یک فاصله چاپ کنید.
  • در صورتی که مسئله چند جواب داشت هر کدام را می‌توانید بنویسید.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
4‎
3 ghul xul takhr‎
3 khul bakh ghil‎
4 xul ghzd bakh ghil‎
‎3 khul bakh ghul
3‎
1 1 2‎
3 1 3‎
‎4 2 3

‎ ‎‎


ابزار صفحه