المپدیا

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

ابزار کاربر

ابزار سایت


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

Car

در یک مسابقه‌ی ماشین‌سواری، تعدادی ماشین روی یک خط مستیقم به سمت خط پایان در حال حرکت می‌باشند. خط پایان درنقطه‌ی ‎$a$‎ قرار دارد. در لحظه ی ‎$0$‎ ماشین ‎$i$‎ام در نقطه‌ی ‎$x_i$‎ قرار دارد ( $0 \le x_i < a$‎) قرار دارد. هر ماشین در طول حرکت، سرعتی ثابت برابر با ‎$v_i$‎ دارد. اگر دو ماشین، قبل از رسیدن به نقطه‌ی پایان، یا در لحظه‌ی رسیدن به نقطه‌ی پایان، هم‌زمان در یک نقطه قرار بگیرند، هر دو منفجر شده و از دور مسابقه حذف می‌شوند (و طبعا ماشین دیگری هم با آن‌ها تصادف نخواهد کرد). محسن سوار یکی از ماشین‌هاست و ما می‌خواهیم کاری کنیم که او در این مسابقه اول شود. کاری که می‌توانیم بکنیم این است که بعضی از ماشین‌ها را از قبل دستکاری کنیم که در لحظه‌ی ‎$0$‎ خود به خود منفجر شوند و از دور مسابقه حذف شوند. اما برای این که ماجرا مشکوک نباشد، می‌خواهیم کم‌ترین تعداد لازم ماشین را برای قهرمانی محسن خراب کنیم. شما باید به ما کمک کنید و تعداد ماشین‌هایی که باید خراب شوند را پیدا کنید.

ورودی

  • در سطر اول ورودی به ترتیب عدد طبیعی ‎$1 \leq n \leq 200,000$‎ ( یعنی تعداد ماشین‌ها) و ‎$0 \leq a \leq 10^{12}$‎ آمده‌اند‎
  • در ‎$n$‎ سطر بعد، در هر سطر مشخصات یکی از ماشین‌ها آمده است‎.‎ در سطر ‎$i+1$‎ام اعداد ‎$0 \leq x_i < a$‎ و ‎$1 \leq v_i \leq 10,000$‎ آمده‌اند.‎
  • محسن در ماشین شماره ‎$1$‎ قرار دارد‎.‎
  • می‌دانیم که هیچ سه ماشینی در یک لحظه در یک نقطه قرار نمی‌گیرند، هیچ دو ماشینی در ابتدا در یک نقطه قرار ندارند و هیچ دو ماشینی در یک لحظه به خط پایان نمی‌رسند.
  • تمام اعداد ورودی صحیح می‌باشند.

خروجی

خروجی تنها باید شامل یک عدد صحیح باشد که حداقل تعداد ماشینی است که برای قهرمانی محسن، باید خراب کنیم.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3 10‎
5 3‎
4 4‎
1 3
1
3 10‎
1 1‎
2 5‎
‎3 4
0

ابزار صفحه