Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

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

ابزار کاربر

ابزار سایت


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

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

تعاریف

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

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

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

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

صورت سوال

دو مجموعه‌ی L-خوش‌ترتیب I1 و I2 از بازه‌ها به شما داده می‌شود. شما دو عدد صحیح l1 و l2 بیابید به صورتی که:

(a) (I1+l1)(I2+l2)=

(b) (I1+l1)(I2+l2)، L-خوش‌ترکیب باشد. (توجه داشته باشید که l1 و l2 می‌توانند منفی باشند)

ورودی

در سطراول فایل ورودی عدد L و در دو سطر بعدی I1 و I2 به ترتیب توصیف شده‌اند. برای توصیف هر Ii نخست تعداد بازه‌های درون آن نوشته می‌‌شود. سپس مختصات لبه‌های بازه‌های عضو آن مجموعه به ترتیب صعودی نوشته می‌شود.( 1L7777777 و 1|I2|,|I1|777 )

خروجی

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

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

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

ابزار صفحه