In the country of Voronoi, there are \(N\) villages, located at distinct points on a straight road. Each of these villages will be represented by an integer position along this road.
Each village defines its neighbourhood as all points along the road which are closer to it than to any other village. A point which is equally close to two distinct villages \(A\) and \(B\) is in the neighbourhood of \(A\) and also in the neighbourhood of \(B\).
Each neighbourhood has a size which is the difference between the minimum (leftmost) point in its neighbourhood and the maximum (rightmost) point in its neighbourhood.
The neighbourhoods of the leftmost and rightmost villages are defined to be of infinite size, while all other neighbourhoods are finite in size.
Determine the smallest size of any of the neighbourhoods (with exactly 1 digit after the decimal point).
The first line will contain the number \(N\) \((3 \leq N \leq 100)\), the number of villages. On the next \(N\) lines there will be one integer per line, where the \(i\)th line contains the integer \(V_i\), the position of the \(i\)th village \((-1\ 000\ 000\ 000 \leq V_i \leq 1\ 000\ 000\ 000)\). All villages are at distinct positions.
Output the smallest neighbourhood size with exactly one digit after the decimal point.
5
16
0
10
4
153.0
The neighbourhoods around \(0\) and \(16\) are infinite. The neighbourhood around 4 is \(5\) units (\(2\) to the left, and \(3\) to the right). The neighbourhood around 10 is \(5.5\) units (\(3\) to the left and \(2.5\) to the right). The neighbourhood around 15 is \(3.0\) units (\(2.5\) to the left and \(0.5\) to the right).
Barbara plants \(N\) different sunflowers, each with a unique height, ordered from smallest to largest, and records their heights for \(N\) consecutive days. Each day, all of her flowers grow taller than they were the day before.
She records each of these measurements in a table, with one row for each plant, with the first row recording the shortest sunflower’s growth and the last row recording the tallest sunflower’s growth. The leftmost column is the first measurement for each sunflower, and the rightmost column is the last measurement for each sunflower.
If a sunflower was smaller than another when initially planted, it remains smaller for every measurement.
Unfortunately, her children may have altered her measurements by rotating her table by a multiple of 90 degrees.
Your job is to help Barbara determine her original data.
The first line of input contains the number \(N\) \((2 \leq N \leq 100)\). The next \(N\) lines each contain \(N\) positive integers, each of which is at most \(10^9\). It is guaranteed that the input grid represents a rotated version of Barbara’s grid.
Output Barbara’s original data, consisting of \(N\) lines, each of which contain \(N\) positive integers.
2
1 3
2 91 3
2 9The data has been rotated a multiple of 360 degrees, meaning that the input arrangement is the original arrangement.
3
4 3 1
6 5 2
9 7 31 2 3
3 5 7
4 6 9The original data was rotated 90 degrees to the right/clockwise.
3
3 7 9
2 5 6
1 3 41 2 3
3 5 7
4 6 9The original data was rotated 90 degrees to the left/counter-clockwise.
A robot has stolen treasure from a factory and needs to escape without getting caught. The factory can be modelled by an \(N\) by \(M\) grid, where the robot can move up, down, left, or right.
Each cell of the grid is either empty, a wall, a camera, a conveyor,
or the robot’s initial position. The robot can only walk on empty cells
(denoted by .) or conveyors. The first row,
last row, first column and last column of the grid consists of walls
(denoted by W), and there may be walls in
other cells.
Conveyors cause the robot to move in a specific direction, denoted by
L, R,
U, D for left,
right, up, down respectively. The robot is unable to move on its own
while on a conveyor. It is possible that the robot can become stuck
forever on conveyors.
Cameras (denoted by C) can see in all four
directions up, down, left, and right, but cannot see through walls. The
robot will be caught if it is in the same cell as a camera or is seen by
a camera while on an empty cell. Conveyors are slightly elevated, so the
robot cannot be caught while on a conveyor, but cameras can see empty
cells on the other side of conveyors.
The robot is initially at the cell denoted by
S. The exit could be at any of the empty
cells. For each empty cell, determine the minimum number of steps needed
for the robot to move there without being caught, or determine that it
is impossible to move there. A step consists of moving once up, down,
left or right. Being moved by a conveyor does not count as a step.
The first line of input contains two integers \(N\) and \(M\) \((4 \leq N,
M \leq 100)\). The next \(N\)
lines of input will each contain \(M\)
characters, each of which is one of the eight characters
W, .,
C, S,
L, R,
U, or D.
There will be exactly one S character and
at least one . character. The first and last
character of every row and column will be
W.
For 5 of the 15 marks available, there are no cameras or conveyors.
For an additional 5 of the 15 marks available, there are no conveyors.
For each empty cell, print one line with one integer, the minimum number of steps for the robot to move to this empty cell without being caught or \(-1\) if it is impossible to move to this empty cell.
The output should be in row major order; the order of empty cells seen if the input is scanned line by line top-to-bottom and then left-to-right on each line. See the sample outputs for examples of row major order output.
4 5
WWWWW
W.W.W
WWS.W
WWWWW-1
2
1The robot cannot move to the top left empty cell because it is blocked by walls.
The top right empty cell can be reached in \(2\) steps and the bottom right empty cell can be reached in \(1\) step.
5 7
WWWWWWW
WD.L.RW
W.WCU.W
WWW.S.W
WWWWWWW2
1
3
-1
-1
1The empty cell to immediate left of the robot is seen by the camera so the robot cannot move there.
The empty cell right below the R conveyor
is also seen by the camera as conveyors do not block the the sight of
cameras.
Note that the robot can use the U and
L conveyors to avoid the getting caught by the
camera.
If the robot moves to the R conveyor, it
will become stuck forever there.
Trees have many fascinating properties. While this is primarily true for trees in nature, the concept of trees in math and computer science is also interesting. A particular kind of tree, a perfectly balanced tree, is defined as follows.
Every perfectly balanced tree has a positive integer weight. A perfectly balanced tree of weight \(1\) always consists of a single node. Otherwise, if the weight of a perfectly balanced tree is \(w\) and \(w\ge 2\), then the tree consists of a root node with branches to \(k\) subtrees, such that \(2\le k \le w\). In this case, all \(k\) subtrees must be completely identical, and be perfectly balanced themselves.
In particular, all \(k\) subtrees must have the same weight. This common weight must be the maximum integer value such that the sum of the weights of all \(k\) subtrees does not exceed \(w\), the weight of the overall tree. For example, if a perfectly balanced tree of weight \(8\) has \(3\) subtrees, then each subtree would have weight \(2\), since \(2+2+2=6 \le 8\).
Given \(N\), find the number of perfectly balanced trees with weight \(N\).
The input will be a single line containing the integer \(N\) \((1\le N\le 10^9)\).
For \(5\) of the \(15\) marks available, \(N\le 1000\).
For an additional \(2\) of the \(15\) marks available, \(N\le 50000\).
For an additional \(2\) of the \(15\) marks available, \(N\le 10^6\).
Output a single integer, the number of perfectly balanced trees with weight \(N\).
4
3
One tree has a root with four subtrees of weight 1; a second tree has a root with two subtrees of weight 2; the third tree has a root with three subtrees of weight 1.
10
13
A long time ago in a galaxy far, far away, there are \(N\) planets numbered from \(1\) to \(N\). Each planet has \(M\) cities numbered from \(1\) to \(M\). Let city \(f\) of planet \(e\) be denoted as \((e, f)\).
There are \(N \times P\) two-way flights in the galaxy. For every planet \(e\) \((1 \le e \le N)\), there are \(P\) flights numbered from \(1\) to \(P\). Flight \(i\) connects cities \((e,a_i)\) and \((e,b_i)\) and costs \(c_i\) energy daily to maintain.
There are \(M \times Q\) two-way portals in the galaxy. For all cities with number \(f\) \((1 \le f \le M)\), there are \(Q\) portals numbered from \(1\) to \(Q\). Portal \(j\) connects cities \((x_j, f)\) and \((y_j, f)\) and costs \(z_j\) energy daily to maintain.
It is possible to travel between any two cities in the galaxy using only flights and/or portals.
Hard times have fallen on the galaxy. It was decided that some flights and/or portals should be shut down to save as much energy as possible, but it should remain possible to travel between any two cities afterwards.
What is the maximum sum of energy that can be saved daily?
The first line contains four space-separated integers \(N\), \(M\), \(P\), \(Q\) \((1\le N,M,P,Q \le 10^5)\).
Then \(P\) lines follow; the \(i\)-th one contains three space-separated integers \(a_i\), \(b_i\), \(c_i\) \((1 \le a_i, b_i \le M, 1 \le c_i \le 10^8)\).
Then \(Q\) lines follow; the \(j\)-th one contains three space-separated integers \(x_j\), \(y_j\), \(z_j\) \((1 \le x_j, y_j \le N, 1 \le z_j \le 10^8)\).
It is guaranteed that it will be possible to travel between any two cities using flights and/or portals. There may be multiple flights/portals between the same pair of cities or a flight/portal between a city and itself.
For 2 of the 15 available marks, \(P,Q \le 100\) and \(c_i = 1\) for all \(1 \le i \le P\), and \(z_j = 1\) for all \(1 \le j \le Q\).
For an additional 2 of the 15 available marks, \(P,Q \le 200\).
For an additional 5 of the 15 available marks, \(N,M \le 200\).
Output a single integer, the maximum sum of energy that can be saved daily.
2 2 1 2
1 2 1
2 1 1
2 1 13
2 3 4 1
2 3 5
3 2 7
1 2 6
1 1 8
2 1 541
One possible way is to shut down the flights between cities \((1,1)\) and \((1,1)\), \((2,1)\) and \((2,1)\), \((1,1)\) and \((1,2)\), \((1,3)\) and \((1,2)\), \((2,3)\) and \((2,2)\), and shut down the portal between cities \((2,3)\) and \((1,3)\) for total energy savings of \(8+8+6+7+7+5=41\).