المپدیا

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

ابزار کاربر

ابزار سایت


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

مسیر پر مغز

مثلثی از اعداد طبیعی کوچک‌تر از ۱۰۰ شامل حداکثر ۱۰۰۰ خط در اختیار داریم. هر مثلث در سطر اول خود شامل یک عدد، در سطر دوم شامل دو عدد و … در سطر $n$ ام شامل $n$‌ عدد است. یک مسیر کامل مسیری است که از سطر اول مثلث آغاز و به یکی از اعداد سطر آخر ختم شود و در هر حرکت از عدد $j$ ام سطر $i$ ام به یکی از اعداد $j$ ام یا $j+1$ ام سطر $i+1$‌ ام برود. می‌خواهیم در این مثلث مسیر کاملی را پیدا کنیم که مجموع اعدادی که شامل می‌شود ماکزیمم باشد.

ورودی

در سطر اول فایل ورودی $m$، تعداد ورودی‌ها آمده است. سپس به ازای هر ورودی در یک سطر $n$ (تعداد سطر‌های مثلث) و در $n$ سطر بعدی به ترتیب سطرهای مثلث آمده‌اند.

خروجی

به ازای هر ورودی، مجموع اعداد مسیر کامل ماکزیمم مثلث داده شده را در یک سطر بدون فاصله بین سطرها بنویسید.

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

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

ابزار صفحه