المپدیا

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

ابزار کاربر

ابزار سایت


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

شهر چوبی

یک جدول مستطیلی $m\times n$ در نظر بگیرید که روی هر خانه‌ی آن یک مکعب مستطیل چوبی به قاعده‌‌ی $1 \times 1$ و به ارتفاع مشخص قرار دارد. به این شکل «شهر چوبی» می‌گوییم. می‌توانید فرض کنید مکعب‌های مذکور آسمان خراش‌های شهر هستند و ارتفاع هر مکعب تعداد طبقات آن آسمان خراش را نشان می‌دهد. ما به شما ابعاد شهر و ارتفاع هر آسمان خراش را می‌گوییم و برنامه‌ی شما باید مشخص کند که اگر این شهر چوبی را در یک مایع قرار دهیم تا کجا پایین می‌رود. چون این دوره‌ی المپیاد کامپیوتر است نه فیزیک ما بخش فیزیکی مسئله را برای شما حل کرده‌ایم. یک ضریب طبیعی $k$‌به شما داده می‌شود. برنامه شما باید ارتفاعی را به‌دست بیاورد که $k$ برابر حجم چوب بالای آن ارتفاع با حجم چوب پایین آن ارتفاع برابر باشد. چون این ارتفاع لزوما صحیح نیست برنامه شما باید مقدار صحیح این ارتفاع (اولین طبقه‌ای که بخشی (یا کل) آن از آب بیرون است) را مشخص کند. طبقات از پایین شماره‌گذاری می‌شوند و همکف همان طبقه‌ی شماره‌ی ۱ است!

ورودی

در خط اول فایل ورودی به ترتیب اعداد $m$ و $n$ و $k$ امده($1 \leq m,n \leq 300$) و در $m$ خط بعد در هر خط $n$ عدد داده شده است که عدد $j$ ام از سطر $i+1$ ام ورودی ارتفاع آسمان خراش(ارتفاع آسمان‌خراش از $10^6$ کم‌تر است) موجود در مختصات $(i,j)$ است.

خروجی

در فایل خروجی شماره‌ی اولین طبقه‌ای را که از آب بیرون است (بخشی یا کل آن) بنویسید.

محدودیت‌ها

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

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

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

پاسخ


ابزار صفحه