PROBLEM LINK:
Author: Aman
Editorialist: Aman
DIFFICULTY:
MEDIUM.
PREREQUISITES:
Sorting, Maths.
PROBLEM:
Sagar is running on a treadmill of length 2l which has n fixed but detachable blocks of negligible height. You are given the positions of the blocks relative to the initial start position of the belt
0 ≤ a_1 < a_2 < … < a_n < 2l. The positions on the belt from 0 to l correspond to the top, and from
l to 2l — to the the bottom half of the belt. For each i from 0 to n calculate the probability that Sagar will kick out exactly i blocks, also print the minimum of blocks with the lowest probability of kick-out and maximum blocks with highest probability of kick-out.
EXPLANATION:
Wherever Sagar starts, he will run along the treadmill a segment of length D= (v_2 *l)/(v_1+v_2). Consider one block. To kick it, he needs to get on the treadmill in any moment of the segment
[a_i - D…a_i]. Consider all points like a_i - D and a_i (add 2l if that is negative). Also add points 0 and 2l.
Sort these points. Consider two neighboring points: x[i] & x[i+1]. If Sagar starts at any moment between them, he will kick the same numbers of blocks.
Consider events along a circle like (a[i] — D, +1) and (a[i], -1). One needs to move twice along the circle and use the second run to add the current length to the answer for the current number of blocks.
After getting probability of every number of blocks to kick-out, we can find the maximum number of blocks having the highest probability and the minimum number of blocks having the lowest probability by iteration.
The solution require O(NlogN) time.
SOLUTIONS:
Solution
/* *JAT BALWAN JAI BHAGWAN* */
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;
typedef pair<double, int> pnt;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<bool> vb;
#define x first
#define y second
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 300005;
/*..........................wake up to reality.............................*/
int main () {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n, l, v1, v2;
scanf ("%d%d%d%d", &n, &l, &v1, &v2);
double d = (double)l * v2 / (v1 + v2);
vector <pnt> v(n);
v.push_back (pnt (0., 0));
v.push_back (pnt (2. * l, 0));
for (int i = 0; i < n; i++) {
double a;
scanf ("%lf", &a);
double x = a - d;
if (x < 0) {
v.push_back (pnt (2 * l + x, +1));
v.push_back (pnt (2 * l, -1));
x = 0;
}
v.push_back (pnt (x, +1));
v.push_back (pnt (a, -1));
}
sort (v.begin(), v.end());
double p = 0;
int cnt = 0;
vector <double> res(2 * n, 0);
for (int i = 0; i < (int)v.size(); i++) {
res[cnt] += v[i].x - p;
p = v[i].x;
cnt += v[i].y;
}
int pos, loc;
double mx = 0, mn = 1;
vector<pair<long double, long long int> > kuch;
for (int i = 0; i <= n; i++) {
printf ("%.9lf\n", res[i] / (2 * l));
double val = (res[i] / (2 * l));
kuch.push_back({val, i});
}
sort(kuch.begin(), kuch.end());
cout << kuch[0].second << " " << kuch[n].second << endl;
return 0;
}
//template by abs