====== مدار ======


در این مسئله با تعدادی گیت سر و کار داریم. هر گیت یک یا چند ورودی و یک خروجی دارد. ورودی و خروجی یک گیت فقط مقادیر ۰ و ۱ است. سه نوع گیت $or،not$ و $and$ در اختیار داریم.

  * گیت $and$ دو ورودی و یک خروجی دارد. خروجی آن ۱ است اگر و تنها اگر هر دو ورودی آن ۱ باشند.
  * گیت $or$ دو ورودی و یک خروجی دارد. خروجی آن ۰ است اگر و تنها اگر هر دو ورودی آن ۰ باشد.
  * گیت $not$ یک ورودی و یک خروجی دارد. اگر ورودی‌ آن ۱ باشد، خروجی آن ۰ و اگر ورودی آن ۰ باشد خروجی آن ۱ است.
  * یک مدار شامل تعدادی گیت است که ورودی‌ها و خروجی‌های آن‌ها به هم متصل شده است!

مثلا شکل زیر یک مدار است.


{{ :سوالات_المپیاد:دوره‌ی_تابستان:دوره‌ی_۱۰:الگوریتم‌ها:2.png |}}

  - در یک جعبه اندازه‌ی کافی گیت $and$ داریم. می‌دانیم حداکثر $k$‌ تا از این گیت‌ها خراب شده‌اند و مثل گیت $or$ عمل می‌کنند ($k$ یک عدد ثابت است). مداری طراحی کنید که کار گیت $and$ را انجام دهد. مدار شما باید دارای ۲ ورودی و ۱ خروجی باشد. به جز این دو ورودی هیچ مقدار دیگری در اختیار نداریم مگر اینکه با گیت‌های موجود در جعبه ساخته شود.
  - در یک جعبه به اندازه‌ی کافی گیت از هر سه نوع داریم. هر گیت برچسب مخصوص به خود را دارد. یعنی گیت‌ها ازهم متمایزند. حداکثر $k$ تا ا ز گیت‌ها خراب هستند و خروجی آن‌ها یکی از ورودی‌های آن‌ها به دل‌خواه است. مداری طراحی کنید که کار گیت $not$ را انجام دهد. توجه کنید که در هر دو قسمت این مسئله نمی‌دانیم کدام گیت‌ها خراب هستند!

  * [[سوال ۸|سوال بعد]]
  * [[سوال ۶|سوال قبل]]