المپدیا

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

ابزار کاربر

ابزار سایت


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

استوانه

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

وزن مسیر بابر است با مجموع مقادیر خانه‌های روی مسیر. خانه‌هایی $(1,1)$ و $(n,n)$ هم در وزن محسوب می‌شوند. هدف این است که یک مسیر با شرایط فوق، با وزن ماکسیمم پیدا کنید.

ورودی

در سطر اول فایل ورودی عدد $n$‌ آمده است. سپس در $n$‌ سطر عددهای جدول نوشته شده‌اند.( $n$‌ از ۳۰۰ بیش‌تر نیست)

خروجی

در فایل خروجی وزن ماکسیمم را بنویسید. سپس $k$، تعداد خانه‌ها در مسیر، را بنویسید. توجه کنید که خانه‌های اول و آخر ($(1,1)$ و $(n,n)$) هم محسوب می‌شوند. سپس مختصات این $k$‌تا خانه را بنویسید، بدین صورت که برای یک خانه، اول شماره‌ی سطر و سپس شماره‌ی ستون آن را بنویسید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
6
2 5 -1 1 -8 1
-1 6 3 -5 -2 -3
4 3 8 1 7 2
-7 9 1 1 1 0
2 6 0 0 -2 -10
0 1 1 1 1 1
61
17
1 1
1 2
2 2
2 3
3 3
3 1
3 5
3 6
3 1
3 2
4 2
5 2
6 2
6 3
6 4
6 5
6 6

ابزار صفحه