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

المپدیا

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

ابزار کاربر

ابزار سایت


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

پینوکیو و فیل‌های زرنگ

زمان:۱۵ ژولای سال ۱۸۰۴

مکان: شکم نهنگ عظیم‌الجثه

در تاریکی مطلق این دو موجود آتش روشن کرده‌اند. نهنگ عظیم‌الجثه خشمگین شده، بالا و پایین می‌پرد. همه‌چیز در هم می‌ریزد و قایق چوبی آن دو موجود می‌شکند.

پیرمرد:«پینوکیو خودتو نجات بده…»

زمان: ۳ روز بعد

مکان: دهکده ساحلی

بالاخره پینوکیو از دهان نهنگ عظیم‌الجثه بیرون آمد و به هر زحمتی که شده بود خودش را به دهکده ساحلی رساند. او از چوبی بودن خسته شده است. تصمیم می‌گیرد هر جور شده پری مهربان را پیدا کند.

زمان:همان شب

مکان: تخت‌خواب پینوکیو

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

پری مهربان:«چون تو پسر خوبی بودی تصمیم گرفتم بیام و آدمت کنم.»

پینوکیو:«شما همیشه لطف دارین، من واقعا لذت می‌برم…»

پری مهربان:«آره، می‌دونم… منم از خدامه که تو آدم بشی تا من از این داستان بیام بیرون و برم دنبال یه شغل نون و آب‌دار. اما خب وظیفه‌ی من حکم می‌کنه که قبل از این که آدمت بکنم، کاملا مطمئن بشم که تو لیاقت آدم شدن رو داری. برای همین ازت چند تا سوال می‌کنم و تو باید همه رو به دقت جواب بدی.»

و بعد از موافقت از پینوکیو، پری مهربان ادامه داد:…

توضیح:

« در صفحه شطرنجی n×n‌ حداکثر چند تا مهره‌ی فیل می‌شه قرار داد، به طوری‌که هیچ دو تایی از اون‌ها هم‌دیگر را تهدید نکنن؟»

پری مهربان k تا سوالاین مدلی از پینوکیو پرسید. به پینوکیو کمک کنین تا زودتر آدم بشه!

ورودی

در سطر اول فایل ورودی 1k100، تعداد سوال‌های این تیپی پرسیده شده از پینوکیو آمده است. سپس در k‌ سطر بعدی، در سطر i+1 ام (1ik) یک عدد 1ni10100 آمده است که اندازه‌ی صفحه‌ی شطرنج مربوط به سوال i ام است.

خروجی

شما باید در فایل خروجی در k سطر جواب سوال‌های پرسیده شده از پینوکیو را بنویسید. عدد نوشته شده در سطر i ام باید جواب سوال باشد: «در صفحه‌ی شطرنج ni×ni حداکثر چند مهره‌ی فیل می‌توان قرار داد، به‌طوری که هیچ دو تایی از آن‌ها هم‌دیگر را تهدید نکنند؟»

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
2
2
3
2
4

ابزار صفحه