• 2018-10-13
• 16
• 0

# A. Vova and Train

## Description:

Vova plans to go to the conference by train. Initially, the train is at the point 1 and the destination point of the path is the point L. The speed of the train is 1 length unit per minute (i.e. at the first minute the train is at the point 1, at the second minute — at the point 2 and so on).
There are lanterns on the path. They are placed at the points with coordinates divisible by v (i.e. the first lantern is at the point v, the second is at the point 2v and so on).
There is also exactly one standing train which occupies all the points from l to r inclusive.
Vova can see the lantern at the point p if p is divisible by v and there is no standing train at this position (p \not\in [l; r]). Thus, if the point with the lantern is one of the points covered by the standing train, Vova can’t see this lantern.
Your problem is to say the number of lanterns Vova will see during the path. Vova plans to go to t different conferences, so you should answer t independent queries.

## Input:

The first line of the input contains one integer t (1 \le t \le 10^4) — the number of queries.
Then t lines follow. The i-th line contains four integers L_i, v_i, l_i, r_i (1 \le L, v \le 10^9, 1 \le l \le r \le L) — destination point of the i-th path, the period of the lantern appearance and the segment occupied by the standing train.

## Output

Print t lines. The i-th line should contain one integer — the answer for the i-th query.

## Sample Input:

4
10 2 3 7
100 51 51 51
1234 1 100 199
1000000000 1 1 1000000000

## Sample Output:

3
0
1134
0

### 题目链接

1~L中没v个位置有一个灯笼，给出区间l~r，求区间外有多少个灯笼。

\frac{L}{v}是1~L的灯笼总数，那么显然\frac{l}{v}是1~l的灯笼总数，\frac{r}{v}是1~r的灯笼总数，所以用1~r区间灯笼数减去1~l区间灯笼数即为l~r区间灯笼数(注意特判l点为灯笼点的情况)，最后总数相减即为结果。

# B. Heaters

## Description:

Vova’s house is an array consisting of n elements (yeah, this is the first problem, I think, where someone lives in the array). There are heaters in some positions of the array. The i-th element of the array is 1 if there is a heater in the position i, otherwise the i-th element of the array is 0.
Each heater has a value r (r is the same for all heaters). This value means that the heater at the position pos can warm up all the elements in range [pos – r + 1; pos + r – 1].
Vova likes to walk through his house while he thinks, and he hates cold positions of his house. Vova wants to switch some of his heaters on in such a way that each element of his house will be warmed up by at least one heater.
Vova’s target is to warm up the whole house (all the elements of the array), i.e. if n = 6, r = 2 and heaters are at positions 2 and 5, then Vova can warm up the whole house if he switches all the heaters in the house on (then the first 3 elements will be warmed up by the first heater and the last 3 elements will be warmed up by the second heater).
Initially, all the heaters are off.
But from the other hand, Vova didn’t like to pay much for the electricity. So he wants to switch the minimum number of heaters on in such a way that each element of his house is warmed up by at least one heater.
Your task is to find this number of heaters or say that it is impossible to warm up the whole house.

## Input:

The first line of the input contains two integers n and r (1 \le n, r \le 1000) — the number of elements in the array and the value of heaters.
The second line contains n integers a_1, a_2, \dots, a_n (0 \le a_i \le 1) — the Vova’s house description.

## Output

Print one integer — the minimum number of heaters needed to warm up the whole house or -1 if it is impossible to do it.

6 2
0 1 1 0 0 1

3

5 3
1 0 0 0 1

2

5 10
0 0 0 0 0

-1

## Sample Input:

10 3
0 0 1 1 0 1 0 0 0 1

3

# C. Books Queries

## Description:

You have got a shelf and want to put some books on it.
You are given q queries of three types:
L id — put a book having index id on the shelf to the left from the leftmost existing book; R id — put a book having index id on the shelf to the right from the rightmost existing book; ? id — calculate the minimum number of books you need to pop from the left or from the right in such a way that the book with index id will be leftmost or rightmost. You can assume that the first book you will put can have any position (it does not matter) and queries of type 3 are always valid (it is guaranteed that the book in each such query is already placed). You can also assume that you don’t put the same book on the shelf twice, so ids don’t repeat in queries of first two types.
Your problem is to answer all the queries of type 3 in order they appear in the input.
Note that after answering the query of type 3 all the books remain on the shelf and the relative order of books does not change.
If you are Python programmer, consider using PyPy instead of Python when you submit your code.

## Input:

The first line of the input contains one integer q (1 \le q \le 2 \cdot 10^5) — the number of queries.
Then q lines follow. The i-th line contains the i-th query in format as in the problem statement. It is guaranteed that queries are always valid (for query type 3, it is guaranteed that the book in each such query is already placed, and for other types, it is guaranteed that the book was not placed before).
It is guaranteed that there is at least one query of type 3 in the input.
In each query the constraint 1 \le id \le 2 \cdot 10^5 is met.

## Output

Print answers to queries of the type 3 in order they appear in the input.

8
L 1
R 2
R 3
? 2
L 4
? 1
L 5
? 1

1
1
2

10
L 100
R 100000
R 123
L 101
? 123
L 10
R 115
? 100
R 110
? 115

0
2
1

# D. Boxes Packing

## Description:

Maksim has n objects and m boxes, each box has size exactly k. Objects are numbered from 1 to n in order from left to right, the size of the i-th object is a_i.
Maksim wants to pack his objects into the boxes and he will pack objects by the following algorithm: he takes one of the empty boxes he has, goes from left to right through the objects, and if the i-th object fits in the current box (the remaining size of the box is greater than or equal to a_i), he puts it in the box, and the remaining size of the box decreases by a_i. Otherwise he takes the new empty box and continues the process above. If he has no empty boxes and there is at least one object not in some box then Maksim cannot pack the chosen set of objects.
Maksim wants to know the maximum number of objects he can pack by the algorithm above. To reach this target, he will throw out the leftmost object from the set until the remaining set of objects can be packed in boxes he has. Your task is to say the maximum number of objects Maksim can pack in boxes he has.
Each time when Maksim tries to pack the objects into the boxes, he will make empty all the boxes he has before do it (and the relative order of the remaining set of objects will not change).

## Input:

The first line of the input contains three integers n, m, k (1 \le n, m \le 2 \cdot 10^5, 1 \le k \le 10^9) — the number of objects, the number of boxes and the size of each box.
The second line of the input contains n integers a_1, a_2, \dots, a_n (1 \le a_i \le k), where a_i is the size of the i-th object.

## Output:

Print the maximum number of objects Maksim can pack using the algorithm described in the problem statement.

5 2 6
5 2 1 4 2

4

5 1 4
4 2 3 4 1

1

5 3 3
1 2 3 1 1

5

# E. Binary Numbers AND Sum

## Description:

You are given two huge binary integer numbers a and b of lengths n and m respectively. You will repeat the following process: if b > 0, then add to the answer the value a~ \&~ b and divide b by 2 rounding down (i.e. remove the last digit of b), and repeat the process again, otherwise stop the process.
The value a~ \&~ b means bitwise AND of a and b. Your task is to calculate the answer modulo 998244353.
Note that you should add the value a~ \&~ b to the answer in decimal notation, not in binary. So your task is to calculate the answer in decimal notation. For example, if a = 1010_2~ (10_{10}) and b = 1000_2~ (8_{10}), then the value a~ \&~ b will be equal to 8, not to 1000.

## Input:

The first line of the input contains two integers n and m (1 \le n, m \le 2 \cdot 10^5) — the length of a and the length of b correspondingly.
The second line of the input contains one huge integer a. It is guaranteed that this number consists of exactly n zeroes and ones and the first digit is always 1.
The third line of the input contains one huge integer b. It is guaranteed that this number consists of exactly m zeroes and ones and the first digit is always 1.

## Output:

Print the answer to this problem in decimal notation modulo 998244353.

4 4
1010
1101

12

4 5
1001
10101

11