المپدیا

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

ابزار کاربر

ابزار سایت


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

Movment

احمد در کشور عجیب و غریبی به نام توران گیر افتاده. او می‌خواهد فقط با کمک دو وسیله‌ی نقلیه‌ی عجیب‌تر، خود را تا حد ممکن به یک نقطه‌ای مشخص به نام یوتوپیا نزدیک کند. در صورت استفاده از وسیله‌ی اول، مکان احمد ۹۰ درجه حول نقطه‌ی $A(0,0)$ در یکی از دو جهت ساعت‌گرد و پاد ساعت‌گرد دوران پیدا می‌کند. دقت کنید که جهت دوران را احمد مشخص می‌کند. وسیله‌ی دوم هم مانند وسیله اول است، با این تفاوت که دوران حول نقطه‌ی $B(1,0)$ انجام می‌شود.

شما باید تعیین کنید که احمد با چه دنباله‌ی حرکاتی (دوران‌هایی) می‌تواند خود را به نزدیک‌ترین نقطه به یوتوپیا برساند. دقت کنید که تعداد حکات شما نباید از $5\times 10^5$ بیش‌تر شود. کمینه کردن تعداد حرکات در این سوال مدنظر نیست ولی باید تا حد ممکن احمد به یوتوپیا نزدیک شود.

این یک مسئله‌ی خروجی تنها می‌باشد. به همین خاطرفایل‌های movement1.in ،movment0.in،… و movment19.in به شما داده شده‌اند. شما باید فایل‌های خروجی movement1.out ،movment0. out ،… و movment19. Out را بسازید؛ لازم نیست که همه‌ی خروجی‌ها را در آرشیو قرار دهید و اگر نتوانستید برخی از موارد را حل کنید، کافی است که مواردی را که حل نموده‌اید، در آرشیو ارسالی جای دهید. ارسال شما در این مسئله یک آرشیو (با قالب $ZIP$ یا $tar-gzip$) می‌باشد که شامل تمام فایل‌های خروجی بدون هیچ گونه زیرشاخه‌ای است. اندازه‌ی آرشیو ارسالی نمی‌تواند بیش از ۳۰۰ کیلوبایت باشد. ساختار فایل‌های ورودی و خروجی‌هایی که شما باید تولید کنید، در ادامه آمده است.

ورودی

سطر نخست ورودی شامل چهار عدد صحیح است: دو عدد نخست مختصات ابتدایی احمد و دو عدد بعدی مختصات یوتوپیا می‌باشد. در خواندن مختصات توجه کنید که عدد اول مختصات افقی را نشان می‌دهد. قدر مطلق مختصات‌ها از $10^5$ تجاوز نمی‌کند.

خروجی

دنباله حرکاتی برای کمینه کردن فاصله‌ی احمد و یوتوپیا در خروجی قرار دهید. منظور از فاصله همان فاصله‌ی اقلیدسی است. در سطر اول خروجی ابتدا تعداد حرکات را بنویسید. سپس از خط دوم به بعد در هر خط یک دوران را با یکی از چهار رشته‌ي $+B،-A،+A$ یا $-B$ مشخص کنید. کارکتر $-$ نشان‌دهنده‌ی این است که دوران پاد ساعت‌گرد بوده. کاراکتر $+$ هم نشانگر ساعت‌گرد بودن دوران است. $A$ و $B$ هم مرکز دوران را نشان می‌دهد.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3 1
-2 -2
4
-A
+B
+B
+B
10 10
-10 -10
2
+A
+A

ابزار صفحه