المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۶:عملی:سوال ۴

شَفَق

کابوس(($doom$):‎ حکم فَنا؛ که آخرین روشنی روز به‌هنگام غروب است‎(.‎ درس نظریه‌ی زبان‌ها و ماشین‌ها از محدوده‌ی خوابتان تجاوز کرده و تراوشات آن به این امتحان عملی نیز رسیده است.

در یک گرامر مستقل از متن، یک متغیر را ‎«سازنده»‎ می‌نامیم، اگر با قرار دادن آن به‌عنوان متغیر شروع،بتوان به حداقل یک رشته‌ی نهایی (تنها شامل ترمینال‌ها) رسید. مثلاً در گرامر زیر، تنها متغیرهای ‎$D$‎ و ‎$E$‎ سازنده‌اند:

حالا مسئله چیست؟

یک مسئله‌ی بسیار ساده ‎)‎مانند خیلی دیگر از مسائل نظریه‌ی زبان‌ها و ماشین‌ها!) برنامه‌ای بنویسید که با گرفتن یک گرامر مستقل از متن، متغیرهای سازنده‌ی آن را خروجی دهد.

در گرامر ورودی این مسئله، الفبا (مجموعه‌ی ترمینال‌ها) شامل اعداد صحیح منفی بزرگ‌‌تر از ‎-1000‎ است.

مجموعه‌ی متغیرها نیز با اعداد صحیح مثبت کوچک‌تر از ‎1000‎ نمایش داده می‌شود.

ورودی‎

  • در سطر اوّل، ‎$n$‎، تعداد قاعده‌های گرامر آمده است.
  • در هر یک از ‎$n$‎ سطر بعد، اطلاعات مربوط به یک قاعده آمده است.هر یک از این سطرها با شماره‌ی متغیر سمت چپ قاعده آغاز می‌شوند و در ادامه، شماره‌ی ترمینال‌ها و متغیرهای رشته‌ی سمت راست قاعده نوشته شده‌اند. هر سطر با یک $0$‎ پایان می‌یابد و اعداد این سطرها با یک فاصله از هم جدا شده‌اند.
  • ‎ $1 \leq n \leq 500$‎ و هر سطر شامل حداکثر ‎۲۰۰‎ عدد خواهد بود.

خروجی‎

در تنها سطر خروجی، شماره‌ی متغیرهای سازنده‌ی گرامر را با یک فاصله از هم بنویسید.

محدودیت‌ها

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

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

ورودي نمونه خروجي نمونه
8
1 2 0
1 3 4 0
2 2 -2 1 0
3 1 2 0
4 0
4 5 0
5 -2 4 0
5 1 0
4 5

ابزار صفحه