المپدیا

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

ابزار کاربر

ابزار سایت


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

Oscillation

داداش مهرداد یا تو سلف دانشگاه غذا می‌خوره یا تو قهوه‌خونه‌ی آذری. از اونجایی که مهرداد دوستای خیلی خوبی دارده، بعضی‌هاشون بهش پیشنهاد دادن که توی یه بازه‌ی زمانی مثلا از روز دوم تا روز پنجم می‌تونن توی یکی از این تا جا ناهار مهمونش کنن.

غذای سلف دانشگاه خیلی بدمزه‌ست و روزایی که مهرداد اونجا غذا می‌خورده اشتهاش کور می‌شه و دقیقا نصف مقدار غذایی که بار قبل خورده را می‌خوره؛ ولی اگه بره قهوه‌خونه آذری دقیقا دو برابر مقدار غذایی که دفعه‌ی قبل خورده غذا می‌خوره. در ضمن می‌دونیم مهرداد آدم خسیسیه و به همین خاطر روزایی که کسی مهمونش نکنه ناهار نمی‌خوره.

دیروز مهرداد $m$ کیلو ناهار خورد. بعد یکی از دوستای مهرداد بهش گفت اگه می‌تونی یه جوری عمل کن که مقدار غذایی که می‌خوری بیش‌ترین نوسان را داشته باشه؛ مثلا فرض کنید که مهرداد روز اول $x_1$ کیلوگرم، روز دوم $x_2$ کیلوگرم و روز چهارم $x_3$ کیلوگرم غذا می‌خورده(مقدار غذایی که مهرداد در یک روز می‌خوره یک عدد حقیقیه). در این صورت نوسان غذایی مهرداد می‌شه $|x_3 –x_2|+|x_2-x_1|+|x_1-m|$.

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

فرض کنید تعدادی پیش‌نهاد به مهرداد داده شده. شما به اون کمک کنید تا طوری غذا بخوره که بیش‌ترین نوسان غذایی رو داشته باشه.

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

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

ورودی

سطر نخست ورودی شامل دو عدد صحیح است $n$ و $m$ که به ترتیب نشان‌دهنده‌ی تعداد دعوت‌ها و مقدار غذایی هستند که مهرداد دیروز خورده ($1\leq n \leq 10^5$ و $1\leq m \leq 10^9$).

در هر یک از $n$ سطر بعدی توصیف یک پیشنهاد غذایی نوشته شده: به ترتیب۳ عدد $k$ و $x$ و $y$ که نشان می‌دهند مهرداد روز $x$ام و … و روز $y-1$ام می‌تواند به این پیش‌نهاد عمل کند؛ در صورتی که $k=0$ باشد، یعنی مهرداد به سلف دانشگاه دعوت شده و اگه $k=1$ باشه، یعنی به قهوه‌خونه آذری دعوت شده. در ضمن می‌دانیم $0\leq x \leq y \leq 10^9$ و $0\leq k \leq 1$ است.

خروجی

در سطر اول خروجی تعداد پیش‌نهادهایی (مثلا $r$) که مهرداد می‌پذیرد را بنویسید. در سطر دوم $r$ تا عدد بنویسید که با تعدادی فاصله‌ی خالی از هم جدا شده‌اند. این اعداد شماره‌ی پیش‌نهادهایی است که مهرداد به آن‌ها عمل می‌کند (پیش‌نهاد $i$ام در سطر $i+1$ام ورودی نوشته شده است) در ضمن شماره‌ی پیش‌نهادها را به ترتیبی بنویسید که مهرداد به آن‌ها عمل می‌کند. مثلا اگر روز اول به پیش‌نهاد سوم عمل می‌کند، روز دوم چیزی نمی‌خورد و روز سوم نیز به پیش‌نهاد اول پاسخ می‌دهد، در خروجی بنویسید: $3\quad1$.

محدودیت‌ها

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

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

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

ابزار صفحه