HOTTI PRACTICE TEST - B
Rectangular Side Length
Nộp bàiPoint: 5
Given three integers ~A, B, C~ are side lengths of a rectangle. Find the length of the remaining side.
Input Specification
The first line of input contains an integer ~A~;
The second line of input contains an integer ~B~;
The third line of input contains an integer ~C~.
It is guaranteed that there exists a solution.
Output Specification
- Output the length of the remaining side.
Examples
Input
3
4
3
Output
4
Constraints
~1 \le A, B, C \le 1000~
Count Perfect Squares
Nộp bàiPoint: 5
A perfect square is the result of an integer multiplied by itself. Some examples for perfect squares are ~0, 1, 4, 9, 16, ...~
Given two integers ~A, B~. Find the number of perfect squares between ~A~ and ~B~ (inclusive).
Input Specification
- Input contains two integers ~A, B~ separated by a whitespace.
Output Specification
- Output the number of perfect squares between ~A~ and ~B~.
Examples
Input
2 5
Output
1
Explanation
Such integer is: ~4~.
Input
3 25
Output
4
Explanation
Such integers are: ~4, 9, 16, 25~.
Constraints
For all subtasks:
~1\le L\le R\le 10^{12}~
~R-L\le 10^9~
Subtask 1 [40%]
- ~1\le L\le R\le 10^4~
Subtask 2 [40%]
~1\le L\le R\le 10^8~
~R-L\le 10^5~
Subtask 3 [20%]
- No additional constraints
Coffee Shop
Nộp bàiPoint: 4
TDZ has recently opened a coffee shop.
After using some tricks, he finds out that there will be ~N~ customers visiting the coffee shop on the grand opening day, with the ~i~-th customer coming at minute ~h_i~ (assuming the shop's opening is at minute ~0~). In order to maintain efficiency, he needs to hire some employees.
Each employee can work tirelessly, but he can only serve one customer in one minute. Also, if a customer doesn't receive immediate service, he will leave.
For instance, a customer visits the coffee shop at minute ~5~, then the employee will serve that customer until minute ~6~ and then he will serve other customers (if there is one).
Write a program to help TDZ find the minimum number of employees he needs to hire so that all ~N~ customers that day will be served.
Input Specification
The first line of input contains an integer ~N~;
The following line of input contains ~N~ integers ~h_1, h_2, ..., h_N~.
Output Specification
- Output the minimum number of employees needed.
Examples
Input
4
1 10 45 10
Output
2
Constraints
~1\le N\le 10^5~
~1\le h_i\le 10^5~
Cặp số
Nộp bàiPoint: 3
Art Exhibition
Nộp bàiPoint: 3
There are ~N~ pictures delivered for the exhibition. The ~i~-th painting has a beauty value of ~A_i~.
The exhibition organizer wants to make a triptych by choosing three paintings having indices of ~x, y, z~ such that ~1\le x\lt y\lt z\le N~ and ~A_x = P, A_y = Q, A_z = R~.
Write a program to help the organizer count the number of different triples of paintings that can be made into triptychs. Two triples of paintings are considered different if they do not contain the same set of paintings.
Input Specification
The first line of input contains an integer ~N~;
The following line of input contains ~N~ integers ~A_1, A_2, ..., A_N~;
The third line of input contains three integers ~P, Q, R~.
Output Specification
- Output the number of distinct triptychs the organizer can make.
Examples
Input
5
1 2 2 1 2
1 2 1
Output
2
Explanation
Such triples of indices of paintings are: ~(1, 2, 4), (1, 3, 4)~.
Input
5
1 2 2 1 2
2 1 1
Output
0
Explanation
There are no ways to make a triptych.
Constraints
For all subtasks:
~3\le N\le 2\times 10^6~
~1\le A_i\le 10^9~
~1\le P, Q, R \le 10^9~
Subtask 1 [30%]
- ~3\le N\le 200~
Subtask 2 [30%]
- ~200\lt N\le 3\times 10^4~
Subtask 3 [40%]
- No additional constraints