المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:سوال های ای سی ام سایت تهران:دوره ی ۸:i

Kadj Squares

در این سوال دنباله‌ای از مربع‌ها $S_1, S_2, ..., S_n$ با طول اضلاع طبیعی به شما داده می‌شود. مربع‌ها را به صورتی در قسمت اول صفحه مختصات قرار می‌دهیم که اضلاعشان با محور‌های $x$ و $y$ زاویه ۴۵ درجه ساخته و یکی از رئوسشان روی محور $x$ ها قرار بگیرد. فرض کنیم $x_i$ مکان $x$ رأس پایینی مربع $S_i$ باشد، $S_1$ را در مکانی قرار می‌دهیم که رأس چپش رو محور $y$ ها باشد. سپس مربع Si را طوری قرار می‌دهیم که $x_i$ کمینه شده و شروط زیر بر‌قرار باشد : ($i > 1$)

الف) $x_i$ کم‌تر از $x_i - 1$ باشد (رأس پایینی مربع iام راست‌تر از مربع ($i - 1$)ام باشد.

ب) مساحت داخل مربع iام با هیچ کدام از مربع‌های قبلی اشتراک نداشه باشد.

برنامه شما باید مشخص کند،‌ اگر از بالا نگاه کنیم، کدام مربع‌ها به طور کامل یا ناقص دیده می‌شوند. برای مثال در شکل بالا مربع‌های ۱ و ۲ و ۴ از بالا دیده می‌شوند. مربع $S_i$ از بالا دیده می‌شود اگر نقطه $p$ ای داشته باشد که نیم خطی که از $p$ به سمت بالا رسم می‌کنیم،‌ هیچ مربع دیگری را قطع نکند.

ورودی

در ورودی چند سناریو آمده است.

در خط اول هر سناریو عدد $n$، تعداد مربع‌ها ($n <= 50$) و در خط دوم هر سناریو $n$ عدد بین ۱ تا ۳۰ آمده است که عدد $i$ام طول ضلع مربع $S_i$ است.

در خط آخر ورودی تنها یک عدد صفر آمده است.

خروجی

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

محدودیت‌ها

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

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

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

پاسخ

منتظر پر کردن این قسمت توسط علاقمندان هستیم.


ابزار صفحه