Hanoi final contest
A. Daniel and Perpendophobia
time limit per test
1 second
memory limit per test
512 megabytes
input
PHOBIA.INP
output
PHOBIA.OUT

Daniel is a master on Codeforces, thus he is particularly fond of golden color.

Instead of maintaining his streak of master title on Codeforces, Daniel decides to take a day off and goes for real golden treasures in a remote location.

Though the place that he chooses to dig gold is quite complicated, for the sake of simplicity, Daniel models it as the first quadrant of the Cartesian plane:

The place contains $$$N$$$ gold mines in different coordinates. Daniel does not care how much value of gold he could take, but he wants to explore as many gold mines as possible. As he is eager to explore, he considers the following strategy:

  1. He first starts at the origin.
  2. He notes down his current location, which means he records the coordinates of the point he is standing.
  3. As Daniel has trouble with perpendophobia - an extremely rare phobia, he has to avoid certain gold mines. He must avoid a gold mine located at $$$A(x, y)$$$ if and only if there exists a point $$$B(u, v)$$$ in his record that the line that passes through $$$A$$$ and $$$B$$$ is perpendicular with vertical axis $$$Oy$$$ or horizontal axis $$$Ox$$$.
  4. If his current location is a gold mine, he starts digging for treasures.
  5. Then Daniel picks a random gold mine that he does not need to avoid and has not explored yet. If there is no mine satisfying that, he stops there and comes back home, enjoying the gold that he digs.
  6. Or else, he goes from his current location to the location of the chosen gold mine in the straight line, ignoring every mine lying on his way to the chosen gold mine. Once he gets there, he restarts from step 2.

So, can you calculate the maximum number of gold mines that Daniel could explore, if he executes his strategy optimally?

Input

The first line contains integer $$$N (N\ge 1)$$$.

$$$N$$$ lines follow, each line contains 2 integer $$$x, y\ (0\le x, y\le 10^{9})$$$ denoting the coordinate of a gold mine. It is guaranteed that no two gold mines is located on the same spot and no goal mine is located at $$$O(0, 0)$$$.

Integers on the same line are separated by spaces.

Output

A single integer denoting the maximum number of gold mines that Daniel could explore, if he executes his strategy optimally.

Scoring

This problem worths 60 points.

Subtasks:

  1. 5 points: $$$N\le 10$$$.
  2. 15 points: $$$N\le 20$$$.
  3. 20 points: $$$N\le 400$$$.
  4. 20 points: $$$N\le 80000$$$.
Examples
Input
5
100 400
200 200
200 300
300 400
400 100
Output
3
Input
4
0 1
1 2
2 3
3 0
Output
2

B. Daniel and gameshow
time limit per test
2 seconds
memory limit per test
512 megabytes
input
DTREE.INP
output
DTREE.OUT

Daniel decides to participate in a quite interesting gameshow with others. Below is the description of the game:

Each player will play on a undirected connected graph consisting of $$$n$$$ nodes numbered from 1 to $$$n$$$ and $$$n-1$$$ edges. The rules simply dictates that player starts from a specific node according to Organizing Committee, then moves along the edges to other nodes. Visiting a node and moving through an edge multiple times are acceptable. However, the edge $$$i\ (1\le i\le n-1)$$$ has initial toughness $$$a_i$$$, and each time a player moves through that edge, its toughness decreases $$$1$$$. When its toughness reaches $$$0$$$, the current player and other following players are forbidden to cross that edge.

A player's turn is completed when that player is currently on a node, and they could not move to other node or they decide to terminate. Their score is equal to the number of times they moves through edges of the graph.

The winner is the one with the greatest score.

Daniel is the first player and he wants to maximize his winning chance. Calculate the largest score that Daniel can obtain. Remember, Daniel must start from node $$$R (0\le R\le n)$$$, where $$$R=0$$$ indicates that Daniel could freely pick his starting node.

Input

Line 1 contains an integer $$$n\ (1\le n\le 10^{5})$$$.

Line 2...$$$n$$$: Each line contains three positive integers $$$u, v, r$$$ represents an edge connecting node $$$u$$$ and node $$$v$$$ of the graph $$$(1\le u, v\le n,\ u \ne v)$$$ and its toughness is $$$r\ (1\le r\le 10^{9})$$$.

Line $$$n+1$$$: An integer $$$R (0\le R \le n)$$$

Numbers on the same line are separated by spaces.

Output

A number indicating the maximum score that Daniel can obtain in his turn.

Scoring

This problem worths 70 points including 6 subtasks:

  1. 7 points: Edges connect node $$$1$$$ and node $$$i$$$ with $$$\forall i=\overline{2, n}$$$.
  2. 8 points: Edges connect node $$$i$$$ and node $$$i+1$$$ with $$$\forall i=\overline{1, n-1}$$$, $$$R=1$$$.
  3. 10 points: Edges connect node $$$i$$$ and node $$$i+1$$$ with $$$\forall i=\overline{1, n-1}$$$, $$$R=0$$$.
  4. 14 points: $$$R\ne 0$$$.
  5. 15 points: $$$n\le 2000, R = 0$$$
  6. 16 points: No other conditions applied.
Examples
Input
5
1 2 3
1 3 4
1 4 3
1 5 4
0
Output
14
Input
5
1 2 2
2 3 1
3 4 2
4 5 1
1
Output
4
Input
7
1 2 1
1 3 1
2 4 9
2 5 9
3 6 9
3 7 9
1
Output
18
Input
1
1
Output
0

C. Daniel's game
time limit per test
2 seconds
memory limit per test
512 megabytes
input
DGAME.INP
output
DGAME.OUT

On a beautiful day in December, Daniel invites Andy to play an interesting game: Daniel will pick an array $$$A$$$ which has $$$n$$$ non-negative integers $$$A_1, A_2,..., A_n$$$ and a non-negative integer $$$M$$$. After that, Andy will randomly pick a non-empty sub-array of $$$A$$$, which means he will pick two integers $$$l, r\ (1\le l \le r \le n)$$$ và take $$$A_l, A_{l+1},..., A_r$$$ from the array $$$A$$$. Andy has to preserve the order of the taken integers.

Andy is only allowed to increase his taken integers. Suppose after doing so he receives $$$A'_l, A'_{l+1},..., A'_r$$$ where $$$A'_i \in \mathbb{Z},\ A'_i \ge A_i \forall i=\overline{l, r}$$$. However, he must follow the restriction below:

$$$$$$\sum_{i=l}^{r} A'_i - A_i\le M$$$$$$.

If $$$A'_l, A'_{l+1},..., A'_r$$$ in this order form a non-decreasing array, Daniel will award Andy with bubble tea.

Right after Andy accepts the challenge, Daniel thinks hard to lower the chance of Andy winning as much as possible. Therefore, when he thinks of array $$$A$$$, Daniel has to calculate quickly the number of non-empty sub-arrays of $$$A$$$ that Andy can pick to win this game.

After $$$\frac{21}{10}$$$ second, Daniel has to start the game by telling Andy the array. Please help him to calculate in 2 secs.

Input

Line 1 contains 2 integers $$$n, M$$$.

Line 2 contains $$$n$$$ integers of array $$$A$$$: $$$A_1, A_2,..., A_n$$$.

Numbers on the same line are separated by spaces

Output

An integer indicating the answer

Scoring

In all testcases, $$$n \ge 1, 0\le M\le 2\times 10^{14}, 0\le A_i\le 10^{9}\ \forall i=\overline{1, n}$$$.

70 points with 3 subtasks:

  1. 12 points: $$$n\le 100$$$.
  2. 18 points: $$$n\le 1000$$$.
  3. 40 points: $$$n\le 2\times 10^{5}$$$.
Examples
Input
6 6
5 4 1 1 5 5
Output
18
Input
5 5
6 5 4 3 2
Output
12
Input
1 0
1234
Output
1