المپدیا

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

ابزار کاربر

ابزار سایت


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

Antography

آیا می‌دانید گر یک نقطه‌ی آبی روی دیوار ببینید که در حال حرکت است، آن نقطه چیست؟

درست حدس زدید: یک مورچه که شلوار لی پوشیده!

همان‌طور که می‌دانید آیدین علاقه‌ی زیادی به عکس گرفتن از در و دیوار دارد. دیشب وقتی آیدین داشت به عکس‌هایی که دیروز از در و دیوار باشگاه گرفته بود نگاه می‌کرد، متوجه شد دو عکس وجود دارند که آن‌ها را دقیقا از یک جای دیوار ولی در دو زمان متفاوت گرفته است. وقتی بیش‌تر به این دو عکس دقت کرد، $n$ نقطه‌ی آبی (مورچه با شلوار لی) در هر عکس دید، که البته چون مورچه‌ها حرکت می‌کنند، جای این نقطه‌ها در دو عکس لزوما یکسان نسیت. فرض کنید که تمام مورچه‌ها روی یک خط راست موازی محور $x$ها هستند و روی همان خط حرکت می کنند. ضمنا تمام مورچه‌ها در هر دو عکس حضور دارند.

از آن‌جا که آیدین مطلاعه‌ی زیادی درباره‌ی زندگی مورچه‌ها دارد، می‌داند که هر مورچه در طول عمرش یا فقط به سمت راست حرکت می‌کند یا فقط به سمت چپ و هم‌چنین هر مورچه در هر ثانیه دقیقا یک سانتی‌متر جابه‌جا می‌شود و چون مورچه‌ها موجوداتی متمدن و اجتماعی هستند، وقتی دو مورچه به هم می‌رسند، به هم دیگر سلام می‌کنند.

حالا آیدین در این فکر است که در فاصله‌ی زمانی بین این دو عکس، هر مورچه به چند مورچه‌ی دیگر سلام کرده است. در ضمن چون دوربین آیدین زمان عکس گرفتن را هم به طور دقیق ذخیره می‌کند، می‌تواند فاصله‌ی زمانی این دو عکس را بفهمد. شما باید با توجه به این اطلاعات پاسخ سوال آیدین را به او بگویید. دقت کنید که در هر عکس، هیچ دو مورچه‌ای روی یک نقطه قرار ندارند(البته ممکن است مکان مورچه‌ای در عکس اول، با مکان مورچه‌ای در عکس دوم برابر باشد).

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

  • مکان مورچه‌ها در دو عکس و فاصله‌ی زمانی بین دو عکس را از ورودی بخواند
  • تعداد مورچه‌هایی را که هر مورچه به آن‌ها سلام کرده است محاسبه کند.
  • پاسخ را در خروجی بنویسید.

ورودی

  • در سطر اول ورودی، $n$(تعداد مورچه‌ها) و $t$(فاصله‌ی زمانی بین دو عکس به ثانیه) آمده است که با یک فاصله از هم جدا شده‌اند.($1\leq n \leq 10^6$ و $1\leq t \leq 10^7$)
  • در سطر دوم، $n$ عدد صحیح با فاصله از هم آمده‌اند که مکان مورچه‌ها در عکس اول (بر حسب سانتی‌متر) را به ترتیبی دل‌خواه نشان می‌دهند.
  • در سطر سوم، $n$ عدد صحیح با فاصله از هم آمده‌اند که مکان مورچه‌ها در عکس دوم (بر حسب سانتی‌متر) به ترتیبی دل‌خواه هستند.

خروجی

در تنها سطر خروجی، به تعداد مورچه‌ها ($n$) عدد بنویسید که با فاصله از هم جدا شده‌اند. عدد $i$ام، تعداد سلام‌های مورچه‌ی $i$ام به سایر مورچه‌ها است. منظور از مورچه‌ی $i$ام، $i$امین مورچه‌ای است که مکان اولیه‌ی آن در ورودی داده شده است(یعنی مورچه‌ی متناظر با $i$امین عدد سطر دوم ورودی). در صورتی که رسیدن مورچه‌ها از حالت اولیه به حالت نهایی امکان‌پذیر نبود، در تنها سطر خروجی عبارت«impossible» را بنویسید.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
2 3
2 1
4 -1
1 1

ابزار صفحه