USACO Guide Problem Submission
A. Maximum Distance
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$N$$$ $$$(3 \leq N \leq 5000)$$$ integer points on the coordinate plane. Find the square of the maximum Euclidean distance (aka length of the straight line) between any two of the points.

Input

The first line contains an integer $$$N$$$. The second line contains $$$N$$$ integers, the $$$x$$$-coordinates of the points: $$$x_1, x_2, \dots, x_N$$$ ($$$-1000 \leq x_i \leq 1000$$$). The third line contains $$$N$$$ integers, the $$$y$$$-coordinates of the points: $$$y_1, y_2, \dots, y_N$$$ ($$$-1000 \leq y_i \leq 1000$$$).

Output

Print one integer, the square of the maximum Euclidean distance between any two of the points.

Example
Input
3
321 -15 -525
404 373 990
Output
1059112

B. Studying Algorithms
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Steph wants to improve her knowledge of algorithms over winter break. She has a total of $$$X$$$ ($$$1 \leq X \leq 10^4$$$) minutes to dedicate to learning algorithms. There are $$$N$$$ ($$$1 \leq N \leq 100$$$) algorithms, and each one of them requires $$$a_i$$$ ($$$1 \leq a_i \leq 100$$$) minutes to learn. Find the maximum number of algorithms she can learn.

Input

Line 1: Two space-separated integers $$$N$$$ and $$$X$$$

Line 2: $$$N$$$ space-separated integers $$$a_1, a_2, \dots a_N$$$

Output

A single integer, the answer to the problem.

Example
Input
6 15
4 3 8 4 7 3
Output
4

C. LCS on Permutations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two permutations $$$a$$$ and $$$b$$$ of length $$$N$$$ ($$$1 \leq N \leq 10^5$$$). Determine the length of their longest common subsequence.

Input

Line 1: The single integer $$$N$$$

Line 2: $$$N$$$ space separated integers $$$a_1 \dots a_N$$$ ($$$1 \leq a_i \leq N$$$ and $$$a_i \neq a_j$$$ for all $$$1 \leq i \lt j \leq N$$$)

Line 3: $$$N$$$ space separated integers $$$b_1 \dots b_N$$$ ($$$1 \leq b_i \leq N$$$ and $$$b_i \neq b_j$$$ for all $$$1 \leq i \lt j \leq N$$$)

Output

A single integer: the answer to the above problem

Example
Input
5
3 2 1 4 5
1 2 3 4 5
Output
3
Note

One possible longest common subsequence would be $$$3, 4, 5$$$.

D. Static Range Queries
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is an array $$$a$$$ of length $$$10^9$$$, initially containing all zeroes.

First perform $$$N$$$ updates of the following form:

  • Given integers $$$l$$$, $$$r$$$, and $$$v$$$, add $$$v$$$ to all values $$$a_l, a_{l+1}, \dots, a_{r-1}$$$.

Then, answer $$$Q$$$ queries of the following form:

  • Given integers $$$l$$$ and $$$r$$$, print the sum $$$a_l + a_{l+1} + \dots + a_{r-1}$$$.
Input

Line 1: The two space-separated integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N,Q \leq 10^5$$$)

Lines 2..N+1: Each line contains three space-separated integers $$$l$$$, $$$r$$$, and $$$v$$$, corresponding to an update ($$$0 \leq l \lt r \leq 10^9$$$, $$$v \leq 10^4$$$).

Lines N+2..N+Q+1: Each line contains two space-separated integers $$$l$$$ and $$$r$$$, corresponding to a query ($$$0 \leq l \lt r \leq 10^9$$$).

Output

Print $$$Q$$$ lines, the answers to the queries in the same order as given in the input.

Examples
Input
5 5
3 7 2
1 10 4
1 6 10
0 4 10
6 7 1
5 7
0 2
5 9
1 6
4 9
Output
23
34
31
106
47
Input
5 5
8 9 3
1 6 2
2 5 9
4 8 6
2 7 4
5 8
2 7
5 7
5 10
2 7
Output
28
73
22
31
73
Input
5 5
2 9 5
2 10 1
2 9 9
2 5 10
6 8 8
7 10
0 4
2 6
0 1
0 7
Output
39
50
90
0
113

E. KRUZNICE
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

There are $$$N$$$ circles on the coordinate axis defined by coordinate of their center, $$$C_i$$$, and radius, $$$R_i$$$.

Please determine the smallest number of circles that have to be removed such that there is no intersecting pair of circles among the remaining circles. Remaining circles are allowed to touch at one point.

Input

The first line contains one integer N ($$$1 \leq N \leq 1000$$$), number of circles.

The next N lines contain two integers each $$$C_i$$$ and $$$R_i$$$ ($$$1 \leq C_i, R_i \leq 100$$$), coordinate of the center and radius of each circle. Two circles with the same radius will always be centered at different coordinates.

Output

Output one integer, the smallest number of circles that have to be removed such that no pair of remaining circles intersects.

Examples
Input
6
2 1
5 1
6 1
1 2
3 2
4 3
Output
2
Input
7
40 30
25 15
35 5
70 20
60 30
60 10
80 10
Output
2
Note

In the first example, if we remove $$$(5,1)$$$ and $$$(1,2)$$$, the remaining circles do not intersect.

The circles in the image above also correlate with the first example.