المپدیا

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

ابزار کاربر

ابزار سایت


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

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

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

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

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

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

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

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

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

زمان:همان شب

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

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

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

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

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

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

توضیح:

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

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

ورودی

در سطر اول فایل ورودی $1 \leq k \leq 100$، تعداد سوال‌های این تیپی پرسیده شده از پینوکیو آمده است. سپس در $k$‌ سطر بعدی، در سطر $i+1$ ام ($1\leq i \leq k$) یک عدد $1\leq n_i \leq 10^{100}$ آمده است که اندازه‌ی صفحه‌ی شطرنج مربوط به سوال $i$ ام است.

خروجی

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

محدودیت‌ها

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

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

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

ابزار صفحه