المپدیا

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

ابزار کاربر

ابزار سایت


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

مدار خفن

شما باید یک مدار الکترونیکی طراحی کنید که همبندی دو راس را در یک گراف چک کند. در واقع ۳ عدد $n$، $v$ و $u$ به شما داده می‌شود. برنامه‌ی شما باید یک مدار با $n^2$ ترمینال ورودی $(1,1),(1,2),...,(n,n)$ و یک ترمینال خروجی تولید کند. کارکرد مدار به این صورت است: ما می‌خواهیم چک کنیم که آیا در یک گراف $n$ راسی دل‌خواه ساده‌ی $G$، دو راس $v$ و $u$ در یک مولفه‌ی همبندی قرار دارند یا نه. ما به هر ورودی $(i,j)$ از مدار سیگنال الکتریکی ۱ می‌دهیم اگر در $G$، $i$ به $j$ یال داشته باشد؛ در غیر این صورت به این ورودی سیگنال ۰ می‌دهیم. بالطبع به همه‌ی ورودی‌های $(i,j)$ سیگنال ۰ داده می‌شود. اگر در $G$ $u$ به $v$‌ مسیر داشت، خروجی مدار ۱ و در غیر این صورت ۰ می‌شود. ترمینال‌های ورودی به ترتیب با شماره‌های ۱ تا $n^2$ شماره‌گذاری شده‌اند (ترمینال $(i-1)\times n +j$ مربوط به یال بین $i$ و $j$ است) و ترمینال خروجی، شماره‌ی ۰ دارد.

مدار از ۲ قطعه‌ی الکترونیکی $and$ و $or$ تشکیل شده است. هر یک از این قطعات دو پایه‌ی ورودی و یک پایه‌ی خروجی دارد. پایه‌ی خروجی یک قطعه‌ی $and$ تنها در صورتی که هر دو پایه‌ی ورودی آن ۱ باشند ۱ است و خروجی قطعه‌ی $or$ تنها در صورتی ۰ است که هر دو ورودی آن مقدار ۰ داشته باشند.

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

ووردی

در سطر اول فایل ورودی سه عدد $n$، $v$ و $u$ ($v\neq u$) آمده است. ($n\leq 100$)

خروجی

شما باید در سطر اول فایل خروجی تعداد قطعات الکترونیکی که استفاده می‌کنید را بنویسید. سپس به ازای هر قطعه در یک سطر ابتدا نوع آن قطعه $(and,or)$، سپس شماره‌ی دو ترمینال ورودی و بعد شماره‌ی ترمینال خروجی آن قطعه را بنویسید.

محدودیت‌ها

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

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

ورودي نمونه خروجي نمونه
3 1 22
and 2 6 10
or 3 10 0

ابزار صفحه