فهرست مندرجات
لیوان‌ها
پنتاگون تصمیم به گسترش یکی از مهم‌ترین بخش‌های خود گرفته است: آشپزخانه! در قدم اول در این راستا، برای آشپزخانه تعداد زیادی لیوان شیشه‌ای خریده است. در قدم بعد تصمیم دارد تعداد سالن‌های غذاخوری را هم افزایش دهد.
آقای ب.، رئیس کل امور تغذیه‌ی پنتاگون، خوب می‌داند که کیفیت بد غذاهای پنتاگون( که حتی با فراخ‌ترین گسترش‌ها هم خوب نخواهد شد) موجب خواهد شد کارکنان سازمان از فرط عصبانیت لیوان‌های جدید شیشه‌ای را از پنجره به بیرون پرتاب کنند. اگر لیوان‌ها از طبقات بالا پرتاب شوند می‌شکنند و موضوع تابلوتر از حد مجاز می‌شود. برای همین وی در نامه‌ای از پنتاگون خواست که به دلیل کمردردش سالن‌های غذاخوری جدید را در طبقات بالا قرار ندهند. آن‌‌چه وی در پاسخ به نامه‌اش دریافت کرد به شرح زیر است:
با سلام،
لطفا منظور خود را از عبارت «طبقات بالا» به صورت واضح‌تر بیان نمایید.
این‌جا بود که او تصمیم گرفت با انجام آزمایشی به تنهایی بفهمد پرتاب لیوان‌ها از چه طبقه‌ای به بالا موجب شکستن‌شان می‌شود. آزمایش او شامل حرکت (از طریق پله‌ها) بین طبقات مختلف پنتاگون و پرتاب بعضی از این لیوان‌ها از پنجره‌ی بعضی از طبقات ساختمان پنتاگون است. او از اندک لیوان‌هایی برای آزمایش خود استفاده می‌کند که بر اثر جوب‌های اداری شماره نشده بودند.
بر همگان واضح و مبرهن است که:
- همه‌ی لیوان‌ها کاملا یکسان‌اند و در برابر شرایط برابر پاسخ‌های یکسان دارند.
- اگر پرتاب لیوان از یک طبقه موجب شکسته شدن آن شود، پرتاب لیوان از طبقات بالاتر هم موجب شکسته شدن آن می‌شود.
- با تجهیزات پیش‌رفته‌ی موجود، شکسته شدن یا نشدن لیوان پرتاب‌شده را از هر طبقه‌ای می‌توان دید.
- پرتاب لیوان‌ها از طبقه ۱ (همکف) موجب شکسته شدن آن‌ها نمی‌شود.
- پرتاب لیوان‌ها از طبقه‌ی آخر حتما موجب شکسته شدن آن‌ها می‌شود.
- از لیوان‌های شکسته شده نمی‌توان در ادامه‌ی آزمایش استفاده کرد.
- از لیوان‌های شکسته نشده می‌توان در ادامه‌ی آزمایش استفاده کرد.
برای برداشتن لیوان‌های پرتاب شدهی شکسته نشده، آقای ب. باید ابتدا به طبقه‌ی ۱ برود و بعد آن‌ها را در جیب خود جمع کند. آقای ب. کمردرد دارد و می‌خواهد در بدترین حالت، کم‌ترین میزان ممکن بالا رفتن از طبقات را داشته باشد؛ دقت کنید که میزان پایین رفتن از پله‌ها و مکان نهایی او اهمیتی ندارد. او در ابتدا در طبقه‌ی ۱ قرار دارد و همه‌ی لیوان‌های قابل آزمایش در جیبش هستند.
برنامه‌ای بنویسید که:
- تعداد طبقات ساختمان پنتاگون (همان $f$) و تعداد لیوان‌های موجود ( یعنی $g$ ) را از کتاب‌خانه‌ی پیوندی بخواند.
- به کمک توابع کتاب‌خانه‌ی پیوندی آقای ب. را در انجام آزمایشش یاری نماید.
- کم‌ترین شمارهی طبقه‌ای را به کتاب‌خانه‌ی پیوندی اعلام کند که پرتاب لیوان از آن موجب شکسته شدنش می‌شود.
کتاب‌خانه
توابع زیر در کتاب‌خانه یافت می‌شود:
()int getfloors این تابع $f$ (تعداد طبقات ساختمان پنتاگون) را باز می‌گرداند ($2\leq f \leq 50$).
()int getglasses این تابع $g$ (تعداد لیوان‌های قابل استفاده‌ی موجود) را باز می‌گرداند ($1\leq g \leq 10$).
(void go(int floorNumber این تابع به آقای ب. می‌گوید که به چه طبقه‌ای برود. بدیهی است که floorNumber باید عددی بین ۱ و $f$ باشد.
()int drop با فراخوانی این تابع، آقای ب.، یکی از لیوان‌های موجود در جیبش را از پنجره‌ی طبقه‌ای که در آن است به بیرون پرتاب می‌کند. بدیهی است فراخوانی این تابع زمانی معنی دارد که لیوانی در جیب آقای ب. موجود باشد. خروجی تابع یکی از دو مقدار BROKEN یا NOTBROKEN است که در فایل glass.h تعریف شده‌اند و به ترتیب نشان می‌دهند که لیوان پرتاب شده شکسته شده یا نه.
()void collect با فراخوانی این تابع، آقای ب.، لیوان‌های پرتاب شدهی شکسته نشده در طبقه‌ی ۱ را جمع می‌کند و در جیبش می‌گذارد. فراخوانی این تابع زمانی معنی دارد که او در طبقه‌ی ۱ باشد.
(void report(int floorNumber با فراخوانی این تابع می‌توانید پاسخ خود را به کتاب‌خانه تحویل دهید. این تابع باز نمی‌گردد و پس از فراخوانی‌اش برنامه‌ی شما پایان می‌یابد. مقدار floorNumber باید عددی بین ۱ و $f$ و شمارهی پایین‌ترین طبقه‌ای باشد که پرتاب لیوان از آن‌جا موجب شکسته شدن آن می‌شود.
یکی از دو تابع ()getFloors یا getGlasses باید حتما قبل از دیگر توابع کتاب‌خانه فراخوانی شوند. نقض شرایط گفته شده به منزله‌ی نقض استفاده‌ی درست از کتاب‌خانه است. برنامه‌ی شما نباید با هیچ فایلی کار کرده، از ورودی بخواند یا به خروجی بنویسد. در ضمن برنامه‌ی شما نباید سعی کند که به فضایی خارج از برنامه دست‌رسی داشته باشد. بدیهی است که نقض هر یک از این حدود می‌تواند منجر به حذف شدن از گردونه‌ی رقابت‌ها گردد.
دو فایل glass.h و glasslib.cpp به شما داده شده است. بالای برنامه‌ی شما باید عبارت #include”glass.h” را قرار دهید. توابع و تعاریفی که توسط کتاب‌خانه در اختیار شما قرار گرفته، به صورت زیر است:
#define BROKEN 1
#define NOTBROKEN 0
int getFloors();
int getGlasses();
void go(int floorNumber);
int drop();
void collect();
void report(int floorNumber);
برای هم‌گردانی برنامه‌یتان فایل‌های فوق‌الذکر را پیش برنامه‌یتان (در این جا با نام glass.cpp) کپی کرده و از دستور:
g++ -02 –sstatic glass.cpp glasslib.cpp -lm
استفاده کنید. فایل sglass.cpp نیز یک نمونه از کار کردن با این کتاب‌خانه است. توجه به دو نکته ضروری است:
- برنامه‌ی نمونه داده شده، یعنی
sglass.cppکار مفیدی انجام نمی‌دهد و تنها برای نمایش نحوه‌ی کار کردن با کتاب‌خانه فراهم شده است. - در هنگام ارزیابی برنامه‌ها از کتاب‌خانه‌ی دیگری استفاده خواهد شد که توابع و تعاریف درون
glass.hرا حمایت می‌کند.
ورودی
در تنها سطر ورودی، باید به ترتیب ۳ عدد $f$(تعداد طبقات ساختمان پنتاگون)، $g$ (تعداد لیوان‌ها) و $a$ (شمارهی پایین‌ترین طبقه‌ای که لیوان پرتاب شده از آن می‌شکند) نوشته شده باشند.
شما آزادید برنامه‌هایی که در اختیارتان قرار داده شده را تغییر دهید ولی توصیه می‌شود که فایل glass.h را تغییر ندهید.
خروجی
محدودیت‌ها
- محدودیت زمان: ۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
