المپدیا

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

ابزار کاربر

ابزار سایت


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

خوش‌ترکیب‌سازی

تعاریف

$(a)$ به مجموعه‌ای از بازه‌ها مثل $I$، $L$-خوش‌ترتیب می‌گوییم اگر در شرایط زیر صدق کند:

  1. مختصات لبه‌های بازه‌ها اعداد صحیح بین ۰ تا $L$ باشند (می‌توانند خود ۰ و $L$ هم باشند)
  2. هیچ دو بازه‌ای باهم اشتراک نداشته باشند (مگر احیانا در لبه‌های بازه‌ها)

$(b)$ مجموعه‌ی بازه‌های $I+l$ که $I$ مجموعه‌ای از بازه‌هاست و $l$ عددی صحیح به این صورت تعریف می‌شود:

$$I+l=\{(a+l,b+l)|(a,b) \in I\}$$

صورت سوال

دو مجموعه‌ی $L$-خوش‌ترتیب $I_1$ و $I_2$ از بازه‌ها به شما داده می‌شود. شما دو عدد صحیح $l_1$ و $l_2$ بیابید به صورتی که:

$(a)$ $(I_1+l_1) \cap (I_2+l_2)=\emptyset$

$(b)$ $(I_1+l_1) \cup (I_2+l_2)$، $L$-خوش‌ترکیب باشد. (توجه داشته باشید که $l_1$ و $l_2$ می‌توانند منفی باشند)

ورودی

در سطراول فایل ورودی عدد $L$ و در دو سطر بعدی $I_1$ و $I_2$ به ترتیب توصیف شده‌اند. برای توصیف هر $I_i$ نخست تعداد بازه‌های درون آن نوشته می‌‌شود. سپس مختصات لبه‌های بازه‌های عضو آن مجموعه به ترتیب صعودی نوشته می‌شود.( $1\leq L \leq 7777777$ و $1\leq |I_2|,|I_1| \leq 777$ )

خروجی

در سطر اول فایل خروجی دو عدد $l_1$ و $l_2$ را به همین ترتیب با یک فاصله بنویسید.

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

ورودي نمونه خروجي نمونه
7
3 0 1 2 4 6
2 0 1 2 3
0 4

ابزار صفحه