المپدیا

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

ابزار کاربر

ابزار سایت


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

سینی دوبعدی

در دنیای دوبعدی ‎$n$‎ نفر، ‎$n$‎ دیس (ظروف بزرگی که مقدار زیادی غذا در آن‌ها جا می‌شود) را در دست گرفته و شروع به حرکت کرده‌اند. در این دنیا فرد ‎$i$‎ام با قد ‎$h_i$‎ متر و سرعت ثابت ‎$v_i$‎ متر در ثانیه، در حال حرکت است. هم‌چنین دیسی که در دست آدم ‎$i$‎ام قرار دارد طولی برابر ‎$l_i$‎ متر دارد؛ که افراد دیس‌ها را به صورت افقی در دست دارند. در ابتدای خلقت، تمام آدم‌ها در نقطه ‎ قرار دارند و در جهت مثبت محور مختصات در حال حرکت می‌باشند. همچنین در این دنیا در یک لحظه می‌تواند دو یا چند نفر در یک نقطه قرار داشته باشند، ولی قد آدم‌ها با هم برابر نیست!

در لحظه خلقت (زمان ‎$0$) که همه آدم‌ها در نقطه ‎$0$‎ قرار دارند، ناگهان باران می‌گیرد. باران‌های دنیای دوبعدی به صورت ‎$m$‎ قطره می‌باشد که هر قطره به صورت یک نقطه نمایش داده می‌شود. در این دنیا جاذبه عجیبی وجود دارد، به این صورت که هر قطره از زمانی که شروع به حرکت می‌کند با سرعت ثابت ‎$V$‎ به سمت پایین می‌آید. همچنین هر قطره در یک نقطه از دنیای دوبعدی بوجود می‌آید که با ارتفاع آن نقطه و مقدار ‎$x$‎ آن تعیین می‌شود؛ دقت کنید تمام قطره‌ها در لحظه ‎$0$‎ بوجود می‌آیند.

‎ وظیفه شما این است که به سازمان هواشناسی دنیای دوبعدی کمک کنید تا تعیین کند به سینی هر فرد چند قطره بارون می‌ریزد.

ورودی

  • در سطر اول ورودی به ترتیب ‎$n$‎ و ‎$m$‎ و ‎$V$‎ آمده است. ‎
  • در ‎$n$‎ سطر بعدی، در هر سطر سه عدد آمده است که به ترتیب، قد و سرعت و طول سینی یک فرد را مشخص می‌کند.
  • سپس در ‎$m$‎ سطر بعدی، در هر سطر دو عدد آمده که به ترتیب ارتفاع و مقدار ‎$x$‎ مکانی که قطره مورد نظر از آن بوجود می‌آید را به ما می‌گوید.
  • $1 \leq n \leq 1000$‎
  • $1 \leq m \leq 1000$‎
  • تمامی اعداد ورودی، صحیح و مثبت بوده و کمتر از ‎$10 000$‎ می‌باشد.

خروجی

در سطر ‎$i$‎ ام خروجی، یک عدد بنویسید که مشخص می‌کند فرد ‎$i$‎ ام چند قطره‌ی باران جمع می‌کند.

محدودیت‌ها

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

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

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

ابزار صفحه