pc04.ms

.\" PSTITLE: NIT Wednesday Programming Problem \- PC04
.so pc__.ms
.nr fa.pg 0
.ds fa.cl "#797
.blm PP
.TL "چهارشنبه‌ی چهارم\&" "مسئله‌ی برنامه‌نویسی \m[#8f4]چهارشنبه\m[]\&" "می‌خواهیم بهترین باشیم..."
.sp 1
.LP
شیوه‌ی فرستادن جواب‌ها در چهارشنبه‌ی چهارم نیز مشابه چهارشنبه‌های پیشین است؛
در مستند \*[en http://nit.rudi.ir/ctsubmit.pdf] گام‌های
لازم برای فرستادن جواب و دیدن نتیجه‌ی ارزیابی شرح داده شده‌اند.
در ستون آخر نتایج، به ازای هر نمونه‌ی ورودی یک حرف نمایش داده
می‌شود.  در این ستون حرف \*[en P] به معنی خروجی با شکل مناسب،
حرف \*[en F] به معنی خروجی اشتباه،
حرف \*[en T] به معنی خاتمه نیافتن جواب در زمان مجاز دو ثانیه،
حرف \*[en E] به معنی خطای ترجمه و
حرف \*[en R] به معنی خطای زمان اجرا است.

.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 pc04]" "\f(FXشناسه‌ی مسئله\fP"
.	tblrow "\*[num 4] از \*[num 9]" "\f(FXسختی مسئله\fP"
.	tblrow "ساعت \*[num 16]    \*[num 1396/2/20]" "\f(FXزمان شروع\fP"
.	tblrow "ساعت \*[num 16]    \*[num 1396/3/3\0]" "\f(FXزمان پایان\fP"
.tblend
.nr VS +6

.LP
.sp |9.5i
.ps -6
این فایل با هوشمندانه‌ترین برنامه‌ی حروفچینی دنیا )نیتراف( تولید شده است.
.bp 1
.nr fa.pg 1

.SH "تبلیغات در نانل
شهردار شهر نانل در حال برنامه‌ریزی برای جمع‌آوری تبلیغات نامزدها
پس از انتخابات است.  او وعده داده است که این کار را در کمترین
زمان ممکن انجام می‌دهد و از این رو تعدادی ماشین پیشرفته‌ی تشخیص و
جمع‌آوری تبلیغات اجاره کرده است.  شهر نانل به شکل یک گراف است که
رأس‌های آن تقاطع‌ها هستند.  این رأس‌ها با تعدادی خیابان به هم
وصل شده‌اند )هر تقاطع به تعداد زوجی خیابان متصل است(.
شهردار قصد دارد این ماشین‌ها را به شکلی در تقاطع‌ها
قرار دهد و مسیری برای هر یک از آنها تعیین کند که در
کمترین زمان همه‌ی خیابان‌ها از تبلیغات خالی شوند.
فرض کنید زمان مورد نیاز برای تمیز کردن خیابان‌ها برابر باشد.
با تعیین مکان ماشین‌ها و مسیر حرکت آنها، به شهردار کمک کنید.

ورودی با سه عدد شروع می‌شود.  این اعداد به ترتیب تعداد
تقاطع‌ها )حداکثر ده هزار(،
تعداد خیابان‌ها و تعداد ماشین‌ها )حداکثر ده هزار( را نشان می‌دهند.
سپس در ادامه به تعداد خیابان‌ها
خط ظاهر می‌شوند که هر یک شامل دو عدد است که دو سر یک خیابان
را مشخص می‌کند.
خروجی با یک عدد شروع می‌شود که
زمان مورد نیاز برای تمیز کردن شهر را نشان می‌دهد.  سپس
به تعداد ماشین‌ها خط در خروجی ظاهر می‌شوند.  هر یک از
این خط‌ها، مسیر یکی از ماشین‌ها را مشخص می‌کند.
.bp

در مثال زیر شهر پنج تقاطع دارد که با پنج خیابان
به هم وصل شده‌اند و از دو ماشین برای تمیز کردن شهر
استفاده می‌شود.  در خروجی، سه واحد زمان برای تمیز کردن
شهر درخواست شده است.  ماشین اول باید از تقاطع صفرم کار خود
را شروع کند، سپس به تقاطع یکم، دوم و در نهایت به تقاطع سوم
برود.  ماشین دوم نیز از تقاطع دوم حرکت می‌کند و سپس به تقاطع
سوم، چهارم و صفرم می‌رود.  در پایان، هر پنج خیابان شهر
حداقل توسط یکی از ماشین‌ها تمیز می‌شوند.
دقت کنید که برخی از خیابان‌ها می‌توانند چند بار تمیز شوند.
همچنین طول مسیر همه‌ی ماشین‌ها برابر و به اندازه‌ی زمان
درخواست شده است )طول مسیر به تعداد یال‌ها و یکی بیشتر از
تعداد رأس‌های مسیر است(.
.iobeg
5 5 2
0 1
1 2
2 3
3 4
4 0
.iocut
3
0 1 2 3
2 3 4 0
.ioend