pc07.ms

.\" PSTITLE: NIT Wednesday Programming Problem \- PC07
.so pc__.ms
.ps.info "NIT Wednesday Programming Problem - PC07" "Ali Gholami Rudi"
.nr fa.pg 0
.ds fa.cl "#74b573
.blm PP
.TL "چهارشنبه‌ی هفتم\&" "مسئله‌ی برنامه‌نویسی \m[#8f4]چهارشنبه\m[]\&" "می‌خواهیم بهترین باشیم..."
.sp 1
.LP
هفتمین مسئله‌ی برنامه‌نویسی چهارشنبه را در این مستند منتشر می‌کنیم.
.sp |6.5i
.nr VS -6
.tblbeg 4i 0
.	tblbox 1 1 1
.	tblmac fa.tblfc fa.tblfc
.	tblrow "\f(FXدسته‌های پلاکی\fP" "\f(FXعنوان مسئله\fP"
.	tblrow "\*[en pc07]" "\f(FXشناسه‌ی مسئله\fP"
.	tblrow "\*[num 4] از \*[num 9]" "\f(FXسختی مسئله\fP"
.	tblrow "ساعت \*[num 16]    \*[num 1397/\01/29]" "\f(FXزمان شروع\fP"
.	tblrow "ساعت \*[num 16]    \*[num 1397/\02/11]" "\f(FXزمان پایان\fP"
.tblend
.nr VS +6

.LP
.sp |9.5i
.ps -6
این فایل با هوشمندانه‌ترین برنامه‌ی حروفچینی دنیا )نیتراف( تولید شده است.
.bp 1
.nr fa.pg 1
.SH "دسته‌های پلاکی
.EQ
delim $$
.EN
یکی از دقدقه‌های شهردار نانل، رساندن سریع بسته‌های پستی به
گیرنده‌های آنها است.  در بین صدها پیشنهاد ممکن برای کاهش
زمان رساندن بسته‌ها، شهردار یکی از آنها را بسیار تحسین کرده
است )بنا به تصادف، این روش توسط خواهر زاده‌ی شهردار پیشنهاد
شده است که البته بدون تردید، این ارتباط نقشی در تحسین شهردار
نداشته است؛ شهردار محترم نانل نه روابط و نه توصیه‌ها را،
بلکه فقط جنبه‌های فنی را در تحسین‌هایش لحاظ می‌کند(.
اما شهردار در مورد این روش سؤالی دارد که خواهر زاده برای پاسخ آن
به کمک شما نیاز دارد.

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

با گرفتن دنباله‌ای از $n$ عدد صحیح )شماره‌ی پلاک‌ها به ترتیب
ظاهر شدن(، زیر دنباله‌ای از $k$ عدد متوالی
از آن را بیابید به صورتی که اختلاف بزرگ‌ترین و کوچک‌ترین
اعداد این زیر دنباله بیشینه باشد.  ورودی با دو عدد شروع می‌شود
که مقدار $n$ و $k$ را نشان می‌دهند )حداکثر پانصد هزار(.
سپس $n$ عدد در ادامه ظاهر
می‌شوند که دنباله‌ی ورودی را مشخص می‌نمایند.  خروجی شامل یک عدد
است که مکان اولین عدد دنباله‌ی انتخاب شده را نشان می‌دهد )مکان
اولین عدد صفر است(.  اگر چند جواب با اختلاف حداقل وجود داشته
باشند، هر کدام از آنها درست محسوب می‌شوند.
.PP
در نمونه‌ی زیر، دنباله‌ای از ده عدد به عنوان ورودی داده شده
است و خروجی زیر دنباله‌ای را مشخص می‌کند که از عدد ششم )عدد
نه( شروع می‌شود، یعنی اعداد $left < 9, 7, 1 right >$.
اختلاف بزرگ‌ترین و کوچک‌ترین اعداد این دنباله هشت می‌باشد که در
بین سایر زیر دنباله‌های متوالی این دنباله بزرگ‌تر است.
.iobeg
10 3
5 0 6 2 4 4 9 7 1 7
.iocut
6
.ioend
.LP
.bp
.SH "فرستادن جواب‌ها
در \*[urlfa http://nit.rudi.ir/ctsubmit.pdf "این مستند"] گام‌های
لازم برای فرستادن جواب، دیدن نتیجه‌ی ارزیابی و شیوه‌ی انتخاب بهترین
جواب شرح داده شده‌اند.
برای فرستادن جواب از سیستم عامل ویندوز، می‌توانید از
\*[urlfa https://github.com/includeamin/NITCT/raw/master/Release/NITCT.exe "این برنامه"]
که توسط آقای امین جمال نوشته شده است استفاده کنید.

برنامه‌هایی که فرستاده می‌شوند باید از ورودی استاندارد
ورودی‌های مسئله را بخوانند و خروجی‌ها را به خروجی استاندارد بفرستند.
هر برنامه، به ازای تعدادی نمونه‌ی ورودی اجرا می‌شود.
در ستون آخر نتایج، به ازای هر نمونه‌ی ورودی یک حرف نمایش داده
می‌شود.  در این ستون حرف \*[en P] به معنی خروجی با شکل مناسب،
حرف \*[en F] به معنی خروجی اشتباه،
حرف \*[en T] به معنی خاتمه نیافتن جواب در زمان مجاز دو ثانیه،
حرف \*[en E] به معنی خطای ترجمه و
حرف \*[en R] به معنی خطای زمان اجرا است.
در صورتی که خروجی با شکل مناسب تولید شده باشد، به جواب امتیازی
برای آن نمونه داده می‌شود.
مجموع امتیازها در نمونه‌های ورودی، در ستون سوم نتایج نمایش
داده می‌شود.  قطعا بهترین جواب، جوابی است که امتیاز بالاتری را
به دست می‌آورد )به نمونه‌های بیشتری به درستی پاسخ داده است(.
دقت کنید که برای فرستادن جواب‌ها با زبان جاوا، برنامه باید
یک کلاس به نام \*[en Main] داشته باشد که در یک \*[en package]
نباشد.