Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

دروغگو

n نفر x2،x1،… و xn به عنوان متهم قتل‌های زنجیره‌ای در کشور اوشانگولولو دستگیر شده‌اند. از آقای A‌ به عنوان متهم اصل پرونده سوالاتی به این صورت پرسیده شده است که آیا او از افراد xi تا xj تعداد فردی را می‌شناسد یا تعداد زوجی را. پاسخ او یکی از جواب‌های odd یا even بوده است. با توجه به این‌که اصولا متهمین آدم‌های راستگویی نیستند، این امکان وجود دارد که شخص A‌جواب دروغ هم بگوید. در مجموع m‌ سوال از شخص A پرسیده‌ایم. فرض کنید m و n از ۱۵۰ بیش‌تر نیستند.

ورودي

در سطر اول پرونده‌ی ورودی، عدد n، در سطر بعدی عدد m و در m‌ سطر بعدی در هر سطر دو عدد i و j و یک پیغام odd یا even‌ آمده است.

خروجي

می‌خواهیم کوچک‌ترین عدد i را پیدا کنیم به طوری که پس از شنیدن جواب i سوال اول، بتوانیم نتیجه بگیریم که A حتما در یکی از این سوال‌ها دروغ گفته است. در صورت عدم وجود چنین عددی، i را برابر m+1 بگیرید. در پرونده‌ی خروجی عدد i‌را بنویسید.

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

ورودي نمونه خروجي نمونه
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
4
10
5
1 2 even
1 4 odd
2 4 even
1 10 even
3 10 even
6

ابزار صفحه