فرض کنید $x_1 < x_2 < \ldots < x_n < d$ و هم‌چنین $y_1 < y_2 < \ldots < y_n$ اعدادی حقیقی باشند. به ازای هر $1 \le i, j \le n$ یک خودرو در نقطه‌ی $(x_i, y_j)$ قرار دارد که با سرعت ثابت و مثبت $v_{i, j}$ در راستای محور $x$ حرکت می‌کند.

قرار است با فرمان سلطان، تمام خودروها به طور هم‌زمان شروع به حرکت کنند. هر خودرو تا زمانی که مانعی نداشته باشد، با سرعت ثابت خود حرکت می‌کند و به محض این که به خودرویی دیگر برسد، مجبور است پشت سر و چسبیده به آن و با سرعتی کندتر حرکت کند. هر خودرو به محض رسیدن به خط $x=d$ متوقف می‌شود. تضمین می‌شود $d$ آن‌قدر زیاد است که اگر دو خودرو بتوانند به هم برسند، تا قبل از توقف این کار انجام شود. به ازای هر خودرو، مدت زمان بین صدور فرمان تا توقف را در نظر گرفته و این مقادیر را جمع کنید. به مقدار حاصل، هزینه‌ی انتظار تا شیشلیک می‌گوییم!

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

از ورودی مقادیر $n$، $x_i$ ها، $y_i$ ها، $d$ و $v_{i,j}$ ها داده می‌شود. متأسفانه امروز ایلیچ حضور نداشته و کمینه کردن هزینه‌ی انتظار تا شیشلیک به عهده‌ی شماست! الگوریتمی از $O(n^3)$ ارائه دهید که کمینه‌ی هزینه‌ی انتظار تا شیشلیک را بیابد.

• سوال بعد
• سوال قبل