Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۴

Language Recognition

هر Deterministic Final-State Automation (بطورخلاصه DFA) یک گراف جهت‌دار است که هر راس آن یک ‎state‎ نامیده می‌شود و روی هر یال آن یک حرف الفبا نوشته شده است. هم‌چنین به ازای هر راس ‎s‎ حرف روی یال‌هایی که از آن خارج می‌شود متفاوت است. دقت کنید که امکان دارد تعدادی یال با حرف یکسان به یک راس وارد شوند.

هر ‎DFA‎ یک ‎state‎ شروع و تعدادی ‎state‎ پایان دارد. یک ‎DFA‎ یک رشته را می‌پذیرد اگر و فقط اگر یک گشت از ‎state‎ شروع آن به یکی از ‎state‎های پایان آن وجود داشته باشد که اگر حروف نوشته شده روی یال‌های آن را به ترتیب کنار هم بچینیم برابر با رشته مورد نظر شود.

زبان یک ‎DFA‎ مجموعه‌ای از رشته‌هایی است که آن ‎DFA‎ می‌پذیرد. به شما تعدادی رشته داده شده است، برنامه‌ای بنویسید که کمترین ‎k‎ای را بیابد که یک ‎DFA‎ با k state وجود داشته باشد که زبان آن برابر با مجموعه رشته‌های ورودی باشد.

ورودی

  • در سطر اول ورودی ‎1n5000‎ نشانگر تعداد رشته‌های ورودی آمده است.
  • در ‎n‎ سطر بعد در هر سطر یک رشته آمده است.‎

خروجی

در تنها سطر خروجی جواب مسئله را چاپ نمایید.‎

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3‎
fix‎
foo‎
ox
5
4‎
a‎
ab‎
ac‎
ad
3

‎‎ ‎ ‎‎


ابزار صفحه