المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۴:سوال ۴

مدارهای منطقی

مدار منطقی گرافی جهت‌دار است که هر یک از رئوس آن با یکی ازنام‌های $NOT،OR،AND$ و یا $IN$ مشخص شده است. روی هر یک از یال‌های این گراف درهر لحظه ولتاژ ۱ ولت برقرار است. عملکرد هر یک از رئوس مدار به این صورت است:

  • راس $AND$ دو ورودی دارد. اگر هر دو ورودی در یک لحظه برابر یک باشند، تمام خروجی‌های آن در ۱ ثانیه بعد برابر با یک می‌شوند. درغیر این صورت تمام خروجی‌ها در یک ثانیه بعد برابر با صفر خواهند بود.
  • راس $OR$ نیز دو ورودی دارد. اگر ورودی‌های راس $OR$ هر دو در یک لحظه برابر صفر باشند، تمام خروجی‌های آن در ۱ ثانیه بعد برابر صفر و در غیر این صورت برابر یک می‌شوند.
  • راس $NOT$ یک ورودی دارد . اگر مقدار این ورودی در یک لحظه برابر با یک باشد، تمام خروجی‌های آن در ۱ ثانیه بعد برابر صفر و در غیر این صورت برابر یک خواهند بود.
  • راس $IN$ هیچ ورودی ندارد. این راس به عنوان ورودی مدار عمل می‌کند. مقدار ولتاژ تمامی خروجی‌های این راس برابر است و به عنوان ورودی به مدار داده می‌شود.

ولتاژ روی هر یال با عدد $b$ ($b$ صفر یا یک است) و دنباله‌ای صعودی مانند $t_2،t_1$، … و $t_k$ مشخص می‌شود. این دنباله بدین معنی است که ولتاژ این یال، قبل از زمان $t_1$، برابر $b$ بوده است، پس از لحظه‌ی $t_1$ ولتاژ آن معکوس شده است (یعنی از صفر به یک یا از یک به صفر تغییر یافته است)، پس از لحظه‌ی $t_2$، ولتاژ آن دوباره معکوس شده است (یعنی دوباره برابر $b$ شده است) و همین طور تا آخر.

برنامه‌ای بنویسید که با دریافت یک مدار منطقی و ولتاژ رئوس ورودی آن، ولتاژ خروجی یک راس مشخص از مدار را به‌دست آورد.

ورودي

در سطر اول فایل ورودی، $N$ (تعداد رئوس مدار) و در $N$ سطر بعد، در ابتدای هر سطر یکی از حروف $A$ (برای $AND$)، $O$ (برای $OR$)، $N$ (برای $NOT$) و $I$ (برای $IN$) و پس از آن، با یک فاصله، در مورد رئوس $OR،AND$ و $NOT$، شماره‌ی رئوسی که خروجی آن‌ها به ورودی این راس وصل شده است و در مورد رئوس $IN$ ابتدا عددهای $b$ و $k$ و سپس دنباله‌ی $t_2،t_1$، … و $t_k$ آمده است. فرض کنید که $k$ عددی طبیعی و کم‌تر یا مساوی با ۱۰۰ است و $t_i$ ها عددهایی صحیح هستند اگر مقدار $k$ صفر باشد یعنی مقدار ولتاژ تغییر نمی‌کند. در سطر آخر فایل نیز عددی نوشته شده است که نشان‌دهنده‌ی شماره‌ی راسی است که خروجی مدار از خروجی آن گرفته می‌شود. فرض کنید که تعداد رئوس گراف از ۲۰ بیش‌تر نیست. همچنین فرض کنید که گراف هیچ دوری ندارد.

خروجي

در فایل خروجی ولتاژ خروجی راس مورد نظر را با همان قالب ورودی بنویسید.

به مثال زیر توجه کنید. شکل زیر منحنی ولتاژ در رئوس ورودی «الف»، گراف ورودی «ب»، و منحنی ولتاژ خروجی «ج» را نشان می‌دهد.

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

ورودي نمونه خروجي نمونه
6
I 1 0
I 1 2 1 5
A 1 2
N 2
A 1 4
0 3 5
6
‎1 2 2 3‎

ابزار صفحه