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

در ﻳﻚ ﻣﺤﻴﻂ ۶×۶ ﺗﻌﺪادي ﺷﻲ اﻓﻘﻲ ﻳﺎ ﻋﻤﻮدي دارﻳﻢ ﻛﻪ اﺑﻌﺎد ﻫﺮ ﻳﻚ $1 \times m$ ﻣﻴﺒﺎﺷﺪ ($m$ > 1). ﻳﻜﻲ از اﻳﻦ اﺷﻴﺎ اﻓﻘﻲ (ﻛﻪ در ﺷﻜﻞ در ﺳﻄﺮ ﺳﻮم و ﺳﺘﻮﻧﻬﺎي دو و ﺳﻪ ﻗﺮار دارد – ﺑﻪ آن ﺷﻲ ﻃﻼﻳﻲ ﻣﻴﮕﻮﻳﻴﻢ) ﻣﻴﺨﻮاﻫﺪ از ﻣﻨﺘﻬﺎ اﻟﻴﻪ ﺳﻤﺖ راﺳﺖ از ﻣﺤﻴﻂ خارج شود.

ﻗﻮاﻧﻴﻦ ﺣﺮﻛﺖ ﺑﻪ اﻳﻦ ﺷﻜﻞ اﺳﺖ:

هر شی افقی ﺑﻪ ﺻﻮرت اﻓﻘﻲ و ﻫﺮ شی ﻋﻤﻮدي ﺑﻪ ﺻﻮرت ﻋﻤﻮدي ﺣﺮﻛﺖ ﻣﻴﻜﻨﺪ. (در ﻫﻤﺎن ﺳﻄﺮ ﻳﺎ در ﻫﻤﺎن ﺳﺘﻮن)

اشیا نمی‌توانند از روی هم عبور کنند؛ یعنی برای ﺣﺮﻛﺖ ﻳﻚ ﺷﻲ در ﻳﻚ ﻣﺴﻴﺮ، آن ﻣﺴﻴﺮ ﺑﺎﻳﺪ ﺧﺎﻟﻲ ﺑﺎﺷﺪ.

ﺷﻤﺎ ﺑﺎﻳﺪ ﺑﺎ داﺷﺘﻦ ﻣﺸﺨﺼﺎت ﻳﻚ ﻣﺤﻴﻂ ﻛﻤﺘﺮﻳﻦ ﺗﻌﺪاد ﻣﻮرد ﻧﻴﺎز ﺣﺮﻛﺖ ﺑﺮاي ﺧﺎرج ﻛﺮدن ﺷﻲ ﻃﻼﻳﻲ را ﭘﻴﺪا ﻛﻨﻴﺪ. ﻫﺮ ﺣﺮﻛﺖ ﺑﻪ ﻣﻌﻨﺎي ﺗﻐﻴﻴﺮ ﻣﻜﺎن ﻳﻚ ﺷﻲ از ﻳﻚ ﻣﻜﺎن ﺑﻪ ﻣﻜﺎن دﻳﮕﺮ ﺑﺎ رﻋﺎﻳﺖ ﺷﺮاﻳﻂ ﺑﺎﻻ ﻣﻴﺒﺎﺷﺪ.

ورودی🔗

در ﺳﻄﺮ اول ورودي $n$‌ تعداد اشیا آمده است.

در هر کدام از $n$ سطر بعدی مشخصات یک شی آمده است. هر سطر شامل چهار عدد $x1, y1, x2, y2$ است که $x1$ شماره‌ سطر و $y1$ شماره‌ ستون مربع ابتدایی و $x2$ و $y2$ به ترتیب شماره‌ سطر و ستون مربع انتهایی آن شی میباشد.

ﺷﻲ اول ﺷﻲ ﻃﻼﻳﻲ اﺳﺖ (ﻛﻪ ﻣﺸﺨﺼﺎت آن در ﺳﻄﺮ دوم آﻣﺪه اﺳﺖ) و ﻫﻤﻴﺸﻪ اﻓﻘﻲ و در ﺳﻄﺮ ﺳﻮم ﻗﺮار دارد. ﺧﺮوﺟﻲ ﻫﻢ ﻫﻤﻴﺸﻪ در ﻣﻨﺘﻬﻲ اﻟﻴﻪ ﺳﻤﺖ راﺳﺖ ﺳﻄﺮ ﺳﻮم ﻣﻴﺒﺎﺷﺪ. ورودي درﺳﺖ اﺳﺖ، ﻳﻌﻨﻲ ﻫﻴﭻ دو ﺷﻲاي روي ﻫﻢ ﻗﺮار ﻧﺪارﻧﺪ.

خروجی🔗

در تنها سطر خروجی، حداقل تعداد ﺣﺮﻛﺘﻬﺎي ﻻزم ﺑﺮاي ﺧﺎرج ﻛﺮدن ﺷﻲ ﻃﻼﻳﻲ را ﺑﻨﻮﻳﺴﻴﺪ.

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

مثال🔗

ورودی نمونه ۱🔗

10
3 2 3 3
1 1 2 1
3 1 4 1
6 1 6 3
1 2 1 3
1 4 2 4
3 4 4 4
2 5 3 5
1 6 3 6
5 4 5 6

خروجی نمونه ۱🔗

5

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

یک جایگشت از اعداد ۱ تا $n$ را $k$- متناوب می‌گوییم، اگر هیچ زیردنباله‌ی متوالی در آن وجود نداشته باشد که طولش از $k$ بیش‌تر باشد و یکنوا (صعودی یا نزولی) باشد. مثلا اگر $n = 5$، جایگشت <1,5,2,3,4> ۲-متناوب نیست.

برنامه‌ای بنویسید که:

اعداد $n$ و $k$ و یک جایگشت $n$ تایی $k$- متناوب را از ورودی بخواند.

با فرض این‌که همه جایگشت‌های $n$ تایی $k$-متناوب را به ترتیب الفبایی مرتب کنیم، حساب کند که جایگشت داده شده چندمین جایگشت است.

ورودی🔗

در سطر اول ورودی به ترتیب دو عدد $n$ و $k$ آمده است.

در سطر بعدی $n$ عدد آمده است که عناصر یک جایگشت $k$- متناوب را مشخص می‌کنند.

$2 \le k \le n \le 400$

خروجی🔗

در تنها سطر خروجی، باقی‌مانده رتبه جایگشت داده شده را بر عدد $1 \ 000 \ 000 \ 007$ (۱۰ به توان ۹ به علاوه ۷) بنویسید.

زیرمسئله‌ها🔗

مثال🔗

ورودی نمونه ۱🔗

5 2
1 3 2 5 4

خروجی نمونه ۱🔗

1

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

در شهر شانگولیا $n$ اداره دولتی به مردم از طریق وب سایت خود خدمت رسانی می‌کنند. از آن‌جا که همه این ادارات نیازمند دسترسی به اطلاعات شهروندان شانگولیا می‌باشند، شهردار این شهر تصمیم گرفت در سایت مرکزی شهرداری، یک سرور بانک اطلاعاتی شهروندان را راه اندازی نماید و سرور ادارات را از طریق یک بستر شبکه بدان و به یک‌دیگر متصل نماید. این کار از طریق یک شرکت پیمانکاری انجام شد.

هر یک از ادارات برای راه اندازی وب‌سایت خود از یک سرور استفاده کرده‌اند که یک سوکت شبکه دارد و بدان یک کابل شبکه متصل می‌شود. سرور بانک اطلاعاتی شهروندان پیشرفته‌تر است و قابلیت اتصال دو کابل شبکه را دارد.

برای ایجاد این بستر شبکه $n - 2$سوئیچ مورد استفاده قرار گرفت. هر یک از این سوئیچ‌ها سه سوکت دارد که به هر یک از آن‌ها، سر یک کابل شبکه متصل می‌شود و سوئیچ بسته‌های اطلاعاتی را بر اساس آدرس مقصدشان بین سه پایانه متصل به سوی دیگر کابل‌ها رد و بدل می‌کند. این سه پایانه ممکن است سرور ادارات، سرور بانک اطلاعاتی یا سایر سوئیچ‌ها باشند.

به دلیل رقابت بین ادارات در خدمت‌رسانی به شهروندان، هیچ یک از آن‌ها نمی‌خواهد مدت زمان ارسال بسته‌های اطلاعاتی از سرور بانک اطلاعاتی به سرور آن اداره بیش‌تر از سایر ادارات باشد. لذا ساختا این شبکه به گونه‌ای طراحی گردیده است که مدت زمان ارسال یک بسته اطلاعاتی از سرور بانک اطلاعات مرکزی به سرور تمامی ادارات دقیقا یکسان است. این مدت زمان فقط بر اساس جمع طول کابل شبکه‌ای که بین سرور بانک اطلاعات مرکزی تا سرور یک اداره وجود دارد محاسبه می‌شود، یعنی به ازای اساس جمع طول کابل شبکه‌ای که بین سرور بانک اطلاعات مرکزی تا سرور یک اداره وجود دارد محاسبه می‌شود، یعنی به ازای هر کیلومتر طول کابل شبکه، ۱ میلی ثانیه به مدت زمان عبور بسته اطلاعاتی از آن کابل افزوده می‌شود. فرض کنید طول تمامی کابل‌های شبکه بر اساس کیلومتر عددی صحیح است و زمان لازم برای عبور بسته‌های اطلاعاتی از سوئیچ‌های میانی صفر است.

اکنون پروژه به بهره‌برداری رسیده است و ارتباط تمامی ادارات با سرور بانک اطلاعاتی و با سرور سایر ادارات فراهم گردیده است،‌ اما شهردار معتقد است شرکت پیمانکار طول کابل‌های مورد استفاده در این پروژه را برای دریافت پول اضافه، بیش‌تر از مقدار واقعی گزارش کرده است. او از شما خواسته است جمع طول کابل‌های مورد استفاده رامشخص کنید.

برای این کار مشکل کوچکی وجود دارد، تمامی کابل‌ها از زیر زمین عبور کرده‌اند و شما تنها به سرور ادارات دسترسی دارید. خلاقانه‌ترین کاری که توانستید انجام دهید آن بود که مدت زمان ارسال اطلاعات بین هر جفت از سرور ادارات مختلف را اندازه‌گیری نموده‌اید. حال می‌بایست با استفاده از این اطلاعات مجموع طول کابل شبکه مورد استفاده را محاسبه نمایید.

ورودی🔗

در سطر اول ورودی، $n$ آمده است.

در $n$ سطر بعد ماتریس مدت زمان ارسال بسته اطلاعاتی بین هر جفت اداره بر اساس میلی‌ثانیه درج می‌گردد. این ماتریس همواره متقارن خواهد بود. اعداد داخل ماتریس از ۰۰۰ ۰۰۰ ۱۰۰۰ بیشتر نخواهند بود.

$3 \le n \le 1000$

خروجی🔗

در تنها سطر خروجی، طول کابل‌های شبکه را بر حسب کیلومتر به صورت یک عدد صحیح در خروجی چاپ نمایید.

مثال🔗

ورودی نمونه ۱🔗

4
0 6 20 20
6 0 20 20
20 20 0 12
20 20 12 0

خروجی نمونه ۱🔗

29