آلیس و باب یک بازی دو نفره ابداع کرده‌اند. در ابتدا، آلیس یک عدد صحیح مثبت $k$ بین ۱ و $n$‌ (که ثابت در نظر گرفته می‌شود) انتخاب می‌کند. سپس باب سوالاتی از نوع «آیا $k$ بر $m$ بخش‌پذیر است؟» می‌پرسد که در آن $m$ یک عدد صحیح مثبت می‌باشد. آلیس نیز هر سوال را به صورت «بلی» یا «خیر» پاسخ می‌دهد. باب می‌خواهد که عدد آلیس را با کم‌ترین تعداد پرسش بیابد. شما باید برنامه ای بنویسید که در نقش باب بازی را انجام دهد.

با فرض ثابت بودن $n$ کم‌ترین تعداد پرسش‌ مورد نیاز برای یافتن $k$(بدون توجه به $k$) را با $d(n)$ نشان می‌دهیم. اگر برنامه‌ی شما با حداکثر $d(n)$ پرسش بتواند $k$ را به درستی تعیین کند، نمره‌ی آن مورد را می‌گیرد.

برنامه‌ای بنویسید که:

• حد بالای عدد مخفی آلیس را از کتاب‌خانه‌ی پیوندی بخواند.
• تعدادی پرسش از نوعی که در بالا آمد، را از کتاب‌خانه پیوندی انجام دهد.
• عدد مخفی را به کتاب‌خانه‌ی پیوندی اعلام کند.

کتاب‌خانه

برنامه‌ی شما باید با کتاب‌خانه‌ی تهیه شده بازی کند. توابع زیر در کتاب‌خانه یافت می‌شود:

()int get-n این تابع باید دقیقا یک بار و پیش از هرگونه تعاملی با کتاب‌خانه فراخوانده شود. این تابع عدد $n$، حد بالای عدد در نظر گرفته شده توسط آلیس، را باز می‌گرداند؛ می‌دانیم که $1\leq n \leq 10^6$ است و در نیمی از موارد $1\leq n \leq 10^4$ برقرار است.

(int is-divisible-by(int m برنامه‌ی شما با استفاده از این تابع می‌تواند پرسش‌های خود را مطرح کند. اگر $n$ بر $m$ بخش‌پذیر باشد، ۱ و در غیر این صورت ۰ بازگردانده می‌شود. ورودی تابع یعنی $m$ باید در شرط $1\leq m\leq n$ صدق کند. برنامه‌ی شما باید کم‌ترین تعداد پرسش را بپرسد.

(void guess(int k در نهایت برنامه‌ی شما باید با استفاده از این تابع مقدار $k$ که آلیس انتخاب کرده را معرفی نماید. دقت کنید که $1\leq k \leq n$ باید برقرار باشد. این تابع به برنامه‌ی شما باز نمی‌گردد و پس از فراخوانی‌اش برنامه‌ی شما پایان می‌یابد.

اگر تابعی را با پارمتر‌های نامناسب فراخوانی کنید، برنامه‌ی شما متوقف می‌شود.

برنامه‌ی شما نباید با هیچ فایلی کار کرده، از ورودی بخواند یا به خروجی بنویسید. در ضمن برنامه‌ی شما نباید سعی کند که به فضایی خارج از برنامه دست‌رسی داشته باشد. بدیهی است که نقض هر یک از این حدود می‌تواند منجر به حذف شدن از گردونه‌ی رقابت‌ها گردد.

دو فایل alice.h و alice.c به شما داده شده است. بالای برنامه‌یتان باید عبارت include alice.h# را قرار دهید. برای هم‌گردانی برنامه‌یتان فایل‌ها‌ی فوق‌الذکر را پیش برنامه‌یتان کپی کرده و از دستور

استفاده کنید. فایل sdiv.c نیز به شما داده شده، یک نمونه از کار کردن با این کتاب‌خانه است. توجه به دو نکته ضروری است:

1. برنامه‌ی نمونه‌ی داده شده، یعنی sdiv.c کار مفیدی انجام نمی‌دهد و تنها برای نمایش نحوه‌ی کار کردن با کتاب‌خانه فراهم شده است.
2. در هنگام ارزیابی برنامه‌ها از کتاب‌خانه‌ی دیگری استفاده خواهد شد که توابع و تعاریف درون alice.h را حمایت می‌کند.

در سطر نخست ورودی باید $n$ را بنویسید. در سطر بعدی نیز باید عدد $k$ وجود داشته باشد.

شما آزادید برنامه‌هایی که در اختیارتان قرار داده شده را تغییر دهید ولی توصیه می‌شود که فایل alice.h را تغییر ندهید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۳۲ مگابایت

• سوال قبل