فهرست مندرجات
سوالات ۲۱ و ۲۲ و ۲۳
در بین شهرهای یک کشور٬ راه‌های خاکی و آسفالت کشیده شده‌اند. همه‌ی راه‌ها یک طرفه‌اند و ممکن است یک راه که از یک شهر خارج می‌شود به شهر دیگری وارد شود٬ یا آن که راه به صورت یک حلقه باشد و به همان شهر مبدا وارد شود. می‌دانیم که از هر شهر دقیقا یک راه خاکی و یک راه آسفالت خارج می‌شود٬ هم‌چنین امکان دارد هر دو راه خاکی و آسفالت خارج شده از یک شهر٬ به یک شهر یکسان وارد شوند.
هر شهر یا استقلالی است یا پرسپولیسی. لیلی ساکن شهر پایتخت کشور است و می‌خواهد با گرفتن یک «مسیر» که به صورت رشته‌ای از حرف‌های «خ» (مخفف خاکی) و «آ» (مخفف آسفالت) مشخص می‌شود٬ با شروع از پایتخت به ترتیب راه‌های مشخص شده در مسیر را بپیماید و به مقصد برسد. مثلا اگر مسیر او «خ‌آ‌خ‌آ» باشد٬ ابتدا راه خاکی خارج شده از پایتخت را طی کرده به شهر بعدی می‌رود (اگر آن راه خاکی حلقه باشد مجددا به پایتخت می‌رسد)٬ سپس راه آسفالت خارج شده از شهر دوم را طی کرده به شهر سوم می‌رود و در ادامه با پیمودن یک راه خاکی و یک راه آسفالت به مقصد می‌رسد. براین اساس به سه سوال زیر پاسخ دهید. توجه کنید که مفروضات هر سوال متفاوت است٬ یعنی هر سوال کشور جداگانه‌ای را با شرایط ذکر شده توصیف می‌کند.
با توجه به توضیح بالا به سه سوال زیر پاسخ دهید:
سوال ۲۱
فرض کنید وضعیت راه‌های کشور طوری است که برای هر مسیر که تعداد «خ»های آن زوج است٬ مقصد لیلی یک شهر استقلالی٬ و در غیر این صورت مقصد وی پرسپولیسی باشد. مثلا مقصد مسیر «خ‌خ‌آ‌آآ» استقلالی و مقصد «خ‌آ‌خ‌آخ» پرسپولیسی است. این کشور حداقل چند شهر دارد؟
- ۲
- ۵
- ۴
- ۶
- ۳
پاسخ
گزینه‌ی (۱) درست است.
با یک شهر که ممکن نیست.
چون باید هم جاده‌ی خاکی و هم آسفالت به خود شهر برود که در این‌صورت شهر نه می‌تواند استقلالی باشد نه پرسپولیسی. ولی برای دو شهر به سادگی می‌توان یک مثال ساخت که شامل یک شهر استقلالی و یک شهر پرسپولیسی باشد. کافیست که مسیر خاکی شهر را تغییر دهد و مسیر آسفالت به همان شهر برگردد.
سوال ۲۲
فرض کنید مقصد مسیرهایی استقلالی است که تعداد «خ»های آن مضربی از ۱۳۸۹ باشد٬ و در غیر این صورت مقصد پرسپولیسی باشد. این کشور حداقل چند شهر دارد؟
- ۶۹۴
- ۱۳۸۹
- ۲۷۷۸
- ۱۳۸۸
- ۱۳۹۰
پاسخ
گزینه‌ی (۲) درست است.
جواب ۱۳۸۹ است.
- شرط لازم: در گراف، کوچک‌ترین دوری را بیابید که شامل حداقل یک (خ) باشد. می‌دانیم تعداد (خ)های دور حداقل ۱۳۸۹تا است در غیر این‌صورت با هر مضربی از آن عدد نیز می‌توان به شهر استقلالی رسید. از طرفی چون کوچک‌ترین دور را در نظر گرفتیم هیچ شهر تکراری نداریم، پس تعداد رئوس حداقل ۱۳۸۹ است.
- شرط کافی:۱۳۸۹ راس در نظر بگیرید که با جاده‌های خاکی یک دور کامل ساخته‌اند. مسیرهای آسفالت هر شهر به خودش ختم می‌شود. بدین ترتیب شهر پایتخت استقلالی است و بقیه‌ی شهرها پرسپولیسی خواهند بود.
سوال ۲۳
فرض کنید مقصد مسیر تنها و تنها وقتی استقلالی باشد که مسیر دقیقا ۲۰ راه خاکی متوالی (بدون راه آسفالت)٬ و یا دقیقا ۱۰ راه آسفالت متوالی (بدون راه خاکی) باشد. این کشور حداقل چند شهر دارد؟
- ۳۳
- ۳۱
- ۳۰
- ۳۲
- ۲۹
پاسخ
گزینه‌ی (۲) درست است.
وضعیت هر حالت باید در راسی که قرار دارد ذخیره شود در مجموع ۱۰ حالت برای راه آسفالت و ۲۰ حالت برای راه آسفالت وجود دارد. این دو حالت تنها در شهر مقصد با یک‌دیگر مشترک هستند. از طرفی یک حالت برای شروع وجود دارد (حالت صفر) و یک حالت هم باید وجود داشته باشد که در غیر حالات مورد نظر به آن‌ها برود و بین حالات قبلی تکرار نشود. پس در مجموع حداقل ۳۱ شهر مورد نیاز است.
مثال: شهر پایتخت به شهر استقلالی دو مسیر دارد. یکی به طول ۲۰ که با راه‌های خاکی هرکدام به بعدی متصل است و دیگری به طول ۱۰ که با راه‌های آسفالت پشت سرهم قرار دارند. مسیرهای اشتباه نیز به حالت غیرمجاز می‌رود که از قبل یک راس برای آن در نظر می‌گیریم.
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
