المپدیا

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

ابزار کاربر

ابزار سایت


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

راه فرار مستقیم

یک توری $N\times N$ $(N\leq 100)$ داده شده است. نقاط این توری با مختصات $(i,j)$ مشخص می‌شوند. مختصات نقطه‌ی واقع در گوشه‌ی سمت چپ و پایین توری $(0,0)$ و مختصات نقطه‌ی واقع در گوشه‌ی بالا و سمت راست $(N-1,N-1)$ است. هر نقطه مانند $(i,j)$ از این توری به چهار نقطه‌ی $(i,j \pm 1)$ و $(i\pm 1 , j)$ در صورت وجود وصل است.

$M$ نقطه در این توری داده شده‌اند. می‌خواهیم هر یک ا ز این نقطه‌ها را با مسیری مستقیم به عنوان راه فرار به یکی از نقاط مرزی توری وصل کنیم، به طوری که این مسیرها یک‌دیگر را قطع نکنند $(M\leq 100)$.

  1. با فرض این که مسیرها متصل‌کننده‌ی نقاط به نقاط مرزی، همگی یا به سمت راست و یا به سمت پایین باشند این مسئله را حل کنید.
  2. در صورتی که قسمت اول جواب نداشته باشد، با فرض این که مسیرها همگی به سمت راست، چپ و یا به سمت پایین باشند مسئله را حل کنید.

ورودي

در فایل ورودی چند مجموعه داده که با یک سطر فاصله‌ی خالی از هم جدا شده‌اند قرار دارد. در سطر اول هر مجموعه داده‌ی ورودی به ترتیب اعداد $N$ و $M$ و در $M$ سطر بعد، مختصات $M$ نقطه از توری قرار دارند.

خروجي

در فایل خروجی که در آن خروجی مربوط به هر مجموعه داده با یک سطر خالی از هم جدا می‌شوند. شکل خروجی مربوط به هر مجموعه داده به این صورت است: در صورتی که قسمت (۱) جواب داشته باشد، در $M$ سطر، در هر سطر مختصات یک نقطه‌ی ورودی و جهت راه فرار آن را بنویسید. جهت‌های راست، چپ و پایین را به ترتیب با نویسه‌های $R$، $L$ و $D$ مشخص کنید. در صورتی که قسمت (۱) جواب نداشته باشد، ابتدا پیغام زیر را بنویسید:

$$Part \quad 1 \quad has \quad no \quad solution.$$

و در سطر‌های بعد، در صورتی که قسمت (۲) جواب داشت، جواب آن را به همین صورت و در غیر این صورت پیغام زیر را بنویسید.

$$Part \quad 2 \quad has \quad no \quad solution.$$

به مثال زیر توجه کنید. مجموعه داده‌های اول و دوم این مثال در شکل زیر نشان داده شده است. همان‌طور که در مثال مشاهده می‌کنید در مورد مجموعه داده‌ی سوم هیچ یک از دو قسمت مسئله جواب ندارد.

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

ورودي نمونه خروجي نمونه
12 7
5 1
2 6
5 5
7 4
9 2
8 6
8 9

12 11
3 1
5 2
10 1
3 4
6 4
11 4
4 6
6 7
3 10
9 10
10 10

8 7
1 3
3 3
5 3
3 5
6 5
4 7
7 5
‎5 1 D
2 6 D
5 5 R
7 4 D
9 2 R
8 6 R
8 9 R
Part 1 has no solution.
3 1 D
5 2 D
10 1 R
3 4 L
6 4 D
11 4 R
4 6 D
6 7 L
3 10 L
9 10 D
10 10 R

Part 1 has no solution.
Part 2 has no solution. ‎

ابزار صفحه