المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی انتخاب تیم:دوره ی ۲:سوال ۱

روبات همیلتونی

بر روی صفحه‌ای $N$ نقطه‌ی $P_1$، $P_2$، … و $P_N$ به ترتیب با مختصات $(x_1,y_1)$، $(x_2,y_2)$، … و $(x_N,y_N)$ که همه اعدادی صحیح هستند داده شده است. روباتی قرار است از $P_1$ شروع به حرکت کرده، از همه‌ی نقاط فوق دقیقا یک بار عبور کند و مجددا به $P_1$ باز گردد. روبات در حرکت خود دارای محدودیت‌هایی است و فقط می‌تواند روی خط مستقیم حرکت کند.

در نقطه‌ی $P_1$ روبات می‌تواند هر جهت دل‌خواهی را انتخاب کند تا به یکی از $P_i$ ها برسد، اما از آن پس روبات تنها می‌تواند در همان راستای قبلی حرکت کند، یا ۹۰ درجه به سمت چپ و یا ۹۰ درجه به سمت راست بچرخد. به بیان دیگر، برنامه‌ی حرکت روبات شامل پنج نوع دستورالعمل است:

  • $ORIENTATION(x_k,y_k)$، که فقط به عنوان اولین دستور به کار می‌رود و مفهوم آن این است که روبات در نقطه‌ی $P_1$ به سمت نقطه‌ی $P_k$ می‌چرخد $(1<k \leq N)$.
  • $MOVETO(x_j,y_j)$، که اگر روبات بتواند بدون تغییر جهت به نقطه‌ی $P_j$ برود، این حرکت از نقطه‌ی فعلی به $P_j$ برود، این حرکت از نقطه‌ی فعلی به $P_j$ صورت می‌گیرد.
  • $TURNLEFT$، که روبات ۹۰ درجه به چپ می‌پیچد.
  • $TURNRIGHT$، که روبات ۹۰ درجه به راست می‌پیچد.
  • $STOP$، یا توقف روبات.

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

  1. مقدار $N$ و مختصات $N$ نقطه‌ی ورودی را از فایل ورودی دریافت کند. در سطر اول این فایل عدد $N$ و در $N$ سطر بعدی مختصات $N$ نقطه نوشته شده است.
  2. برنامه‌ای برای روبات تولید کند، به طوری که مطابق با قوانین حرکتی فوق بتواند از $P_1$ شروع به حرکت کند و به تمامی نقاط رفته، به $P_1$ بازگردد.
  3. اگر چنین مسیری وجود ندارد، برنامه‌ی روبات باید فقط شامل دستور $STOP$ باشد.
  4. روی صفحه‌ی نمایش نشان دهد که آیا مسیر مورد نظر وجود دارد یا خیر. در صورت وجود این مسیر، طول آن را به صورت عددی که تا دو رقم بعد اعشار گرد شده است روی صفحه بنویسد. طول مسیر برابر مجموع طول خطوط مستقیم بین نقاط متوالی مسیر است.
  5. برنامه‌ی تولیدی را دقیقا مثل مثال زیر در فایل خروجی بنویسید.

به مثال زیر توجه کنید. شکل زیر مسیری را که روبات در این مثال پیموده است نشان می‌دهد.

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

ورودي نمونه خروجي نمونه
4
2 -2
0 2
-1 -1
3 1
ORIENTATION(3,1)
MOVETO(3,1)
TURNLEFT
MOVETO(0,2)
TURNLEFT
MOVETO(-1,-1)
TURNLEFT
MOVETO(2,-2)
STOP

ابزار صفحه