المپدیا

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

ابزار کاربر

ابزار سایت


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

فهرست مندرجات

گاوصندوق

گاوصندوق باشگاه یک عدد رمز $N$ بیتی دارد. برای هر بیت از آن یک کیلید روی در گاوصندوق وجود دارد. شماره‌ی این کلیدها $1...N$ است. برای زدن رمز می‌بایستی بیت‌های ۱ کلیدشان بالا باشد پس شما اگر بخواهید رمز را بزنید باید این کلید‌ها را بالا ببرید. دقت کنید شما نمی‌توانید یک کلید بالا رفته را به پایین برگردانید. خوشبختانه گاوصندوق یک کلید شماره ۰ هم دارد این کلید هروقت زده شود همه‌ی $N$ کلید دیگر در وضعیت پایین قرار می‌گیرند.

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

ورودی

شما باید خروجی را برای $N$ از ۱ تا ۱۵ به‌دست آورید. دقت کنید متن کد شما اهمیتی ندارد در پایان کار شما فقط باید خروجی خود را تحویل دهید.

خروجی

در سطر اول خروجی برای یک عدد $N$، $M$ کم‌ترین تعداد کلید زدن را بنویسید. در سطر دوم $character M$ بنویسید که شماره‌ی کلیدها زده شده را به ترتیب نشان می‌دهد. برای کلید $i$ ام اگر $0\leq i \leq 9$ از $character$ های $0...9$ استفاده کنید وگرنه از حروف $A...F$ استفاده کنید. $A$ برای ۱۰، $B$ برای ۱۱ و …


ابزار صفحه