Breaking news: A young boy finds a treasure map hidden under his grandpa's pear tree, "Arrrrr, brave scallywags come join me crew 'n let us find the loot" the boy said.
Having pirate blood in you, you decided to join the "captain's" crew. $n$ other people also joined. The crew is now at the treasure's location and they know from the map that the treasure is buried $t$ meters under the ground, the captain decided that this will be the plan to dig out the treasure:
You know that you dig exactly $x$ meters in a single day, and that person $i$ will dig exactly $d_i$ meters in a single day.
The captain has already ordered the other $n$ people, and since you brought him a very expensive jui... drink as a gift, he allowed you to choose your position between the $n$ people, find how many positions out of the $n+1$ positions you can choose such that you will get half of the treasure for your self.
The first line contains three numbers $n, x, t$($1 \le n \le 2 \cdot 10 ^ 5$, $1 \le x \le 10 ^ 9$, $1 \le t \le 10 ^ {18}$), the number of people other than you, the exact number of meters you dig in a single day, the depth of the treasure in meters.
The second line contains $n$ numbers $d_1, d_2, ..., d_n$($1 \le d_i \le 10 ^ 9$), the exact number of meters person $i$ digs in a single day.
Print a single number, the answer as specified above.
In the first example, if you choose to be:
And so you can dig out the treasure only if you choose to be the last person.
In the second example, the treasure is only $1$ meters deep in the ground, so you have to be the first person in order to dig it out.
| Input | Output |
|---|---|
2 3 10 5 4 Copy
|
1 Copy
|
2 1 1 1 2 Copy
|
1 Copy
|
3 8 57 7 3 5 Copy
|
2 Copy
|
3 1000000000 1000000000000000000 1000000000 1000000000 1000000000 Copy
|
1 Copy
|
Let $sum$ be the sum of $x$ and all $d_i$, notice that every $n+1$ days, exactly $sum$ meters will be dug.
Now let's say we want to be after the $i$th person, at first $\lfloor \frac{t}{sum} \rfloor \cdot (n+1)$ days will pass, and we will have ($t - \lfloor \frac{t}{sum} \rfloor \cdot sum$) or ($t \mod sum$) more meters to dig, let's call that quantity $left$.
Let $s_i$ be the sum of all $d_i$ from $1$ to $i$, then we can stand after the $i$th person and take the treasure if and only if $s_i < left$ and $s_i + x \ge left$.
To solve the problem, we check for all possible positions if the above condition is satisfied, array $s$ is basically the prefix sum of array $d$. Don't forget to handle the case where ($t \mod sum = 0$)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)(n); ++i)
const int N = 200000;
ll h[N + 2];
int main() {
int n, hb;
ll htr;
scanf("%d%d%lld", &n, &hb, &htr);
f(i, 1, n + 1){
scanf("%lld", h + i);
h[i] += h[i - 1];
}
h[n + 1] = h[n] + hb;
htr %= h[n + 1];
if (htr == 0){
printf("1\n");
return 0;
}
int an = 0;
f(i, 0, n + 1)if (h[i] < htr && h[i] + hb >= htr)++an;
printf("%d\n", an);
}