المپدیا

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

ابزار کاربر

ابزار سایت


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

Tasks

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

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

برنامه‌ای بنویسید که:

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

ورودی

سطر اول ورودی تنها شامل عدد صحیح $n$ است که تعداد مرحله‌هاست ($1\leq n \leq 100$). در هر یک از $n$ سطر بعد، تعدادی عدد صحیح آمده است که یک مرحله را توضیح می‌دهند. اگر مراحل را به دل‌خواه از ۱ تا $n$ شماره‌گذاری کنیم، در سطر $i+1$ام توضیحات مرحله‌ی $i$ام آمده است. اگر اولین عدد این سطر، ۰ باشد یعنی در مرحله‌ی شماره‌ی $i$، نجاری انجام می‌شود و اگر ۱ باشد یعنی آهنگری. عدد دوم $m_i$‌ است که تعداد مراحلی را مشخص می‌کند که باید پیش از شروع مرحله‌ی $i$ انجام شوند. و سپس $m_i$ عدد مختلف می‌آید که شماره‌ی پیش‌نیازهای مرحله‌ی $i$ است. این $m_i$ عدد بزرگ‌تر از ۱ و کوچک‌تر از $i$ هستند.

خروجی

در سطر اول خروجی کم‌ترین تعداد تغییر کاربری کارگاه که برای انجام کارها لازم است را بنویسید. در سطر دوم یک جایگشت از اعداد ۱ تا $n$ بنویسید که نمایانگر ترتیب بهینه‌ی انجام مراحل است. اگر چندین جواب وجود داشت، به دل‌خواه یکی را در خروجی بنویسید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3
1 0
0 0
1 2 1 2
1
2 1 3

ابزار صفحه