Processing math: 100%

المپدیا

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

ابزار کاربر

ابزار سایت


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

مشعل المپیک

در زمان‌های قدیم n محقق در غاری تاریک مشغول تحقیق بودند. می‌دانیم محقق iام برای انجام تحقیق ti ثانیه به روشنایی احتیاج داشته(ti ها اعداد صحیح نامنفی‌اند). در این غار دقیقا یک مشعل وجود داشته و برای این‌که کارها هم‌زمان پیش برود و کسی بیکار نماند، محققین مشعل را طبق قائده‌ای دست‌به‌دست می‌کرده‌اند. می‌دانیم عمل انتقال مشعل در آغاز یک ثانیه انجام می‌شده و می‌دانیم اگر محقق iام مشعل را از محقق j گرفته بوده باشد، حتما یک ثانیه مشعل را نگه می‌داشته و اگر کاری برایش مانده بوده باشد، یک ثانیه از آن کار را انجام می‌داده و سپس مشعل را به محقق aj,i ام می‌داده است. ti ها و aj,i ها از طریق باستان‌شناسی به‌دست آمده‌اند. در ضمن می‌دانیم در لحظه‌ی آغاز تاریخ مشعل را محقق yام مه محقق x ام داده است. می‌خواهیم بدانیم چقدر طول کشیده تا تمام کارها تمام شود.

ورودی

در ورودی در خط اول اعداد n و y و x آمده است. در سطر بعد ti ها به ترتیب آمده‌اند. سپس در n سطر در هر سطر n عدد آمده است. که عدد iام از سطر jام aj,i است.( 1n5000 و 1ti106)

خروجی

در خروجی تعداد ثانیه‌هایی که طول کشیده تا همه‌ی کارها تمام شوند را بنویسید. می‌دانیم که همه‌ی کارها تمام شده است.

محدودیت‌ها

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

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

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

پاسخ


ابزار صفحه