مقدمه
قصد دارید در جنگل نزدیک خانهتان یک خانهی درختی بسازید تا بتوانید طلوع و غروب خورشید را تماشا کنید.
از یک شرکت نقشهبرداری محلی دادههایی به دست آوردهاید که ارتفاع هر درخت را در هر بخش مستطیلی نقشه نشان میدهند.
باید هر شبکه روی نقشه را تحلیل کنید تا درختهای مناسب برای خانهی درختی خود را پیدا کنید.
درخت مناسب هر دو ویژگی زیر را دارد:
- از هر درختی در شرق و غرب بلندتر است تا بهترین منظرهی ممکن از طلوعها و غروبهای خورشید را داشته باشید.
- از هر درختی در شمال و جنوب کوتاهتر است تا میزان بالا رفتن از درخت را به کمترین حد برسانید.
دستورالعملها
وظیفهی شما این است که درختهای بالقوهای را پیدا کنید که بتوانید خانهی درختی خود را روی آنها بسازید.
شرکت دادهها، دادهها را به شکل جدولهایی ارائه میدهد که ارتفاع درختها را نشان میدهند.
سطرهای جدول جهت شرق-غرب و ستونهای آن جهت شمال-جنوب را نشان میدهند.
یک درخت قابلقبول، بزرگترین درخت در سطر خود و در عین حال کوچکترین درخت در ستون خود است.
ممکن است جدولی اصلاً هیچ درخت مناسبی نداشته باشد.
یا ممکن است یکی داشته باشد، یا حتی چندین درخت.
این جدولی است که دقیقاً یک درخت نامزد دارد.
↓
1 2 3 4
|-----------
1 | 9 8 7 8
→ 2 |[5] 3 2 4
3 | 6 6 7 1
- سطر ۲ مقادیر ۵، ۳، ۲ و ۴ را دارد. بزرگترین مقدار ۵ است.
- ستون ۱ مقادیر ۹، ۵ و ۶ را دارد. کوچکترین مقدار ۵ است.
پس نقطهی [2, 1] (سطر: ۲، ستون: ۱) جای بسیار خوبی برای خانهی درختی است.
دستورالعملهای مخصوص این مسیر
قالب ورودی
ورودی به شکل یک رشته خواهد بود.
برای اینکه این تمرین برای مبتدیها مناسب بماند، لازم نیست انتظار اعداد چندرقمی داشته باشید.
بایتهای ۶۴ تا ۱۹۱ از حافظهی خطی به رشتهی ورودی اختصاص داده شدهاند.
قالب خروجی
خروجی به شکل جفتهای سطر و ستون از نوع u8 انتظار میرود که مستقیماً پشت سر هم قرار میگیرند.
برای مثال، اگر سه نقطهی زینی وجود داشته باشد
سطر: ۲، ستون: ۱
سطر: ۲، ستون: ۲
سطر: ۲، ستون: ۳
در این صورت، خروجی مورد انتظار مقادیر u8 به شکل 2, 1, 2, 2, 2, 3 خواهد بود.
