2026 United Kingdom and Ireland Programming Contest (UKIEPC 2026)
A. Austere Sign
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

We are going to paint a sign but we can only afford stencils for $$$k$$$ letters. Update the text of the sign to use only $$$k$$$ unique letters without changing the lengths of any of the words, so that we can subtly fix the sign later.

Illustration of Sample Input 1. You can do this!

Input
  • The first line of input contains the number of words, $$$n$$$ ($$$1 \le n \le 1000$$$), and the number of letters, $$$k$$$ ($$$1 \le k \le 26$$$).

  • The second line of input contains $$$n$$$ words. Each word consists of between $$$1$$$ and $$$20$$$ lowercase latin letters.
Output

Output a phrase using at most $$$k$$$ distinct letters, substituting as few from the original text as possible. If there are multiple possible answers, output any.

Examples
Input
2 3
good luck
Output
lool lull
Input
3 1
this is hard
Output
ssss ss ssss
Input
1 6
impossible
Output
imbossibee
B. Bust Blasting
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Charlie the CNC miller is a cad with a capital 'C'. He is going to clone a valuable statue of a famous voxel-based video game character, and you are going to help him.

The voxel shape is defined by three photos Charlie took, which have been traced into the form of simple, axis-aligned (but potentially concave) polygons representing front ($$$xy$$$), side ($$$zy$$$), and top ($$$xz$$$) views of the statue respectively.

The meaning of "axis-aligned" here is that every edge of every polygon is parallel with one of the $$$X$$$/$$$Y$$$/$$$Z$$$ axes.

Any 3-dimensional point not contained by all three polygon projections will be blasted out of existence leaving only the true form, which may consist of multiple pieces or no pieces at all.

Illustration of a complex statue.

Calculate the volume of the final statue.

Input

The input consists of three lines of input, each giving one view as a two-dimensional, axis-aligned polygon in anti-clockwise order, with integer coordinates measured in centimetres.

  • First, the number of points, $$$n_i$$$ ($$$4 \le n \le 100$$$).
  • Thereafter, $$$n_i$$$ pairs of integers $$$u_{ij}$$$ and $$$v_{ij}$$$ for all $$$1 \le j \le n_i$$$ ($$$-10\,000 \le u,v \le 10\,000$$$).

It is guaranteed that for all adjacent vertices $$$a$$$ and $$$b$$$, $$$u_{ia} = u_{ib}$$$ or $$$v_{ia} = v_{ib}$$$. No three consecutive vertices are collinear.

Output

Output the integer total volume of the resulting shape(s) in cubic centimetres.

Example
Input
4 0 0 10 0 10 10 0 10
4 5 7 15 7 15 15 5 15
4 11 6 11 12 6 12 6 6
Output
72
C. Cryptlet
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The 5 Latin letters a-e have each been assigned a distinct digit between 0-9. Given an expression involving the sum of two numbers written as X+Y=Z (each number having the same number of digits, at most $$$1000$$$, including any leading zeroes), written using letter substitutions, print plausible values for the assignments of all $$$5$$$ letters in order from a-e as a string of $$$5$$$ characters.

For instance, given ab+ac=ca, you may choose to output 18364. Or, given aaa+bbb=eee, you may output 45789.

Input
  • The only line of input contains a string of lowercase letters in [a-e] and symbols, of the form $$$X+Y=Z$$$ and with no spaces, where $$$1 \le (|X| = |Y| = |Z|) \le 1000$$$.
Output

If no assignment is possible, output impossible.

Otherwise, output any string of $$$5$$$ distinct digits which gives plausible values for the letters $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$, and $$$e$$$ respectively.

Examples
Input
ab+ac=ca
Output
18305
Input
aaaa+bbbb=eeee
Output
34567
Input
bba+bbc=bab
Output
10987
D. Dire Strait
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Mickey has been enjoying sailing on the local lake, but now it's the end of the day and it's time to go back to dock to return the rental boat on time.

Find the shortest path from its current location to the one remaining egress point over water, staying within or passing along the coastline of the lake.

The lake is represented as a simple, potentially concave, polygon having vertices at integer coordinates, and with no $$$3$$$ consecutive vertices being collinear.

A triangulation of the lake into $$$(n-2)$$$ pieces is also provided.

Illustration of Sample Input 1.

Input
  • The number of vertices in the polygon representing the lake, $$$n$$$ ($$$3 \le n \le 100\,000$$$), and the indices of the two vertices between which to travel, $$$a$$$ and $$$b$$$ ($$$1 \le a, b \le n; a \ne b$$$).
  • $$$n$$$ further lines, each giving integer coordinates $$$x_i$$$ $$$y_i$$$ of the $$$i$$$th vertex of the polygon ($$$-10^9 \le x, y \le 10^9$$$) in anti-clockwise order.
  • $$$(n-2)$$$ further lines giving a triangulation of the lake. Each line specifies the $$$1$$$-based indices of three vertices $$$u$$$ $$$v$$$ $$$w$$$ (in anti-clockwise order).

The given triangles correspond to the polygon, thus cover the lake without any self-overlaps, holes, or other hazards.

Output

Output the shortest distance from point $$$a$$$ to point $$$b$$$ without exiting the lake.

The output must be accurate to an absolute or relative error of $$$10^{-6}$$$.

Examples
Input
8 3 7
0 0
10 0
10 2
2 2
2 4
10 4
10 6
0 6
1 2 3
1 3 4
1 4 8
4 5 8
5 7 8
5 6 7
Output
18.246211251
Input
14 1 9
-3 -1
-1 -1
-1 -3
1 -3
1 -1
3 -1
3 1
1 1
1 3
5 3
5 5
-1 5
-1 1
-3 1
1 2 14
6 8 13
3 4 5
9 12 13
8 9 13
6 13 14
2 5 14
5 6 14
10 11 12
2 3 5
9 10 12
6 7 8
Output
5.6568542495
E. Elderberry Wine
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Jeanne and her son Semi-Demi-John are engaged in the elderberry-wine making business.

The recipe requires, aside from a closely-guarded secret quantity of the letter $$$r$$$, strict proportions of $$$12$$$ parts fresh elderberries, $$$12$$$ parts brewing sugar, and $$$40$$$ parts water. As long as one or more ingredients are lacking, the team will place an order for as much extra as needed to make up the weight, and start again.

For instance:

  • If they have $$$18$$$kg of elderberries, $$$9$$$kg of sugar, and $$$100$$$kg of water, they can use $$$9$$$kg of elderberries, all $$$9$$$kg of the sugar, and $$$30$$$kg of the water and then they are stuck.
  • They must then order $$$9$$$kg more of sugar in order to proceed and use $$$9$$$kg, $$$9$$$kg, and $$$30$$$kg again.
  • After this they must order $$$12$$$kg each of elderberries and sugar in order to finally use $$$12$$$kg, $$$12$$$kg, and $$$40$$$kg of elderberries, sugar, and water respectively.
PhaseEb (kg)Su (kg)$$$H_{2}O$$$ (kg)
Initial Stock189100
First Brewing Run-9-9-30
Remaining Stock (Stuck)9070
Sugar Order0+90
Stock After First Order9970
Second Brewing Run-9-9-30
Remaining Stock (Stuck)0040
Berry + Sugar Order+12+120
Stock After Second Order121240
Final Brewing Run-12-12-40
Input

The input consists of one line containing three floating-point numbers $$$a$$$, $$$b$$$, $$$c$$$ ($$$0 \le a, b, c \le 10^{16}$$$): the number of kilograms of elderberries, sugar, and water respectively.

Output

Output three floating-point numbers $$$a'$$$ $$$b'$$$ $$$c'$$$ giving the cumulative total quantities of elderberries, sugar, and water that will be ordered respectively.

The output must be accurate to an absolute or relative error of $$$10^{-6}$$$.

Examples
Input
18 9 100
Output
12 21 0
Input
1.5 17 5
Output
15.5 0 51.666667
Input
3 4 7000000000000000
Output
2099999999999997 2099999999999996 0
F. Footnotes
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Your colleague Cynthia likes writing asides in messages (but then again, don't we all (and there's nothing strictly wrong with that anyway)). As some people find the text hard to read this way, we are going to try to extract some parts of the sentences out into equally-sized footnotes instead of brackets.

For example, this(complicated(nested(passage))) could become:

this[1] [1] complicated[2] [2] nested(passage)

Given one such message, an unbroken string of up to $$$10^6$$$ characters (letters and brackets, without any spaces), isolate exactly two-thirds of the Latin letters into footnotes, each footnote containing exactly the same number of Latin letters.

Input
  • One line containing a string $$$s$$$ ($$$1 \le |s| \le 10^6$$$), each character in $$$s$$$ being a lowercase letter or an opening/closing round bracket.

It is guaranteed that the brackets in $$$s$$$ are properly matched and that the content of a pair of brackets is always non-empty.

Output

Output three lines in the form shown above, using exactly two footnotes in square brackets to indicate where passages were relocated. If there is no way of doing this, output impossible instead.

Your answer will be tested by substituting the footnotes back (inside brackets) and comparing character-by-character with the original text.

Examples
Input
(a(b(c(d(e(f(g(h(i)))))))))
Output
(a(b(c[1])))
[1] d(e(f[2]))
[2] g(h(i))
Input
a(b)(b)(b)((cc))
Output
impossible
Input
a((b)(b))(b)((cc))
Output
a[1](b)[2]
[1] (b)(b)
[2] (cc)
G. Gloucester Somersault
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

A piece of cheese with polygonal cross-sectional area is rolling along a flat surface as part of a major sporting event.

The piece of cheese rotates clockwise continuously, pivoting around the vertex with lowest $$$y$$$-coordinate and, in case of a tie, greatest x-coordinate.

Illustration of Sample Input 1.

The finish line is $$$m$$$ metres from the origin point and must be crossed at ground level, meaning that one of the vertices on the ground is strictly past the line.

How many revolutions does the piece of cheese make in order for at least one part touching the ground to be strictly past the line?

Input
  • The first line of input contains the number of vertices of the cheese piece, $$$n$$$ ($$$3 \le n \le 10\,000$$$), and the integer $$$x$$$-coordinate of the finish line in metres, $$$m$$$ ($$$1 \le m \le 10^6$$$).

  • The next $$$n$$$ lines of input contain the $$$x$$$ and $$$y$$$ coordinates of cheese vertices, in anti-clockwise order, $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 10\,000$$$).

No three adjacent vertices on the shape are collinear and at least one vertex has $$$y = 0$$$. The cheese has not yet crossed the line.

Output

Output the number of full $$$360$$$-degree rotations performed by the piece of cheese until it strictly crosses the line on the ground, rounded up to an integer.

Examples
Input
4 10
0 0
3 0
1 1
0 3
Output
1
Input
4 100
51 0
53 2
51 4
49 2
Output
5
H. Hoptimisation
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are practicing a sequence of hops on a rather boring hopscotch track consisting of several consecutive cells in a straight line, spaced 1m apart.

You have a planned route of cell names to visit. The total hopping distance depends on how you assign these names to the physical positions ($$$1$$$ to $$$k$$$).

For example, to complete the route A, B, A, C with the layout [A, B, C, D, E], the hops take $$$1 + 1 + 2 = 4$$$ metres total.

Illustration of Sample Input 1.

Given your sequence of hops, determine how to arrange the names across the cells (left to right) to minimize the total hopping distance.

Input
  • One line of input containing the number of cells, $$$k$$$ ($$$1 \le k \le 16$$$), and the number of hops, $$$n$$$ ($$$1 \le n \le 10^6$$$).
  • A second line of input containing $$$n$$$ lower-case strings, the $$$i\:$$$th string $$$s_i$$$ containing the target cell for the $$$i\:$$$th hop. ($$$1 \le |s| \le 10$$$).

It is guaranteed that no more than $$$k$$$ distinct cell names are given.

Output

Output $$$k$$$ strings of up to $$$10$$$ lower-case letters each: the names you want to assign to each cell from left to right. If there are multiple potential solutions, you may output any.

In case fewer than $$$k$$$ names are given in the input, feel free to invent more to fill the space.

Examples
Input
5 4
hop skip hop jump
Output
anything jump hop skip something
Input
9 16
a b c a b c a x y z x y z e f g
Output
g f e z y x a c b
I. Inverse Sum
time limit per test
2 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given an integer $$$n \gt 1$$$, and the equation: $$$$$$ \frac{1}{n}=\frac{1}{a}+ \frac{1}{b}$$$$$$ Find two distinct positive integers $$$a,b$$$ which both satisfy the above equation, and have a minimal sum $$$a+b$$$.

Input
  • The only line of input consists of one integer $$$n$$$ ($$$1 \lt n \le 10^8$$$) — the number for the left hand side of the equation.
Output

Output the best choices for $$$a$$$ and $$$b$$$ in ascending order.

Examples
Input
4
Output
6 12
Input
107
Output
108 11556
Input
999999
Output
1998000 2002000
Input
1000000
Output
1800000 2250000
J. Jammer Jam
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Swimming for exercise involves assigning swimmers to lanes suited to their fitness level.

We know the velocity of each swimmer in metres per hour. The swimmers start in any order but inevitably they will eventually become stuck behind the slowest swimmer in the lane and start matching their pace.

Illustration of Sample Input 3.

If we can assign swimmers to $$$l$$$ lanes, how can we ensure that the average speed of all of the swimmers in the pool (measured in metres per hour) is as high as possible? Output this average speed and an assignment of swimmers to lanes.

Input
  • One line containing the number of swimmers $$$n$$$ and the number of lanes $$$l$$$ ($$$1 \le l \le n \le 3\,000$$$).
  • One line containing $$$n$$$ integers giving speeds $$$a_1 \ldots a_n$$$ of the swimmers, in metres per hour ($$$1 \le a \le 10^6$$$).
Output

Output the maximum achievable average speed (mean metres per hour) on one line, followed by a possible assignment of swimmers to lanes to achieve this on the next line. The $$$i$$$th integer on this line is the lane number for the $$$i$$$th swimmer, $$$1 \le a \le l$$$.

The output must be accurate to an absolute or relative error of $$$10^{-6}$$$.

Examples
Input
3 2
100 200 50
Output
100
1 2 1
Input
4 2
11 22 34 47
Output
22.5
1 1 2 2
Input
10 3
34 123 127 161 168 30 44 150 183 193
Output
110.3
1 2 2 3 3 1 1 2 3 3
K. Kilt Quilt
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

An image set to be painted onto a tartan canvas consists of $$$n$$$ rows of $$$m$$$ pixels with each colour represented as a lowercase letter of the alphabet.

You are going to paint the image using long brush strokes that cover either a whole row of $$$m$$$ pixels, or a whole column of $$$n$$$ pixels. Each brush stroke overwrites any pixels that were previously there. You must cover the whole canvas with brush strokes.

Is it possible to do so? If so, output a sequence of instructions of the form x=[1-m] [a-z] or y=[1-n] [a-z]. If there are multiple sequences, output any of the shortest possible lists of instructions.

Illustration of Sample Input 2.

Input
  • The first line of input contains $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 200$$$)

  • The next $$$n$$$ lines of input contain a string of $$$m$$$ lowercase characters in a-z, each representing a colour.
Output

On the first line, output the minimum number of instructions needed. If no sequence of instructions covers the canvas, output impossible and exit.

On each of the next lines, output one instruction to follow in order. For example, "x=5 z", and "y=100 b" are both valid instructions.

Examples
Input
4 6
aaaaba
aaaaba
aaaaba
aaaaba
Output
5
y=1 a
y=2 a
y=3 a
y=4 a
x=5 b
Input
4 4
laaq
daaq
laaq
bbbq
Output
6
x=1 l
y=2 d
x=2 a
x=3 a
y=4 b
x=4 q
L. Lawn Stripes
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Lawn stripes are drawn using a roller to flatten grass blades in a particular direction and impart a sheen that, at a distance, is distinguishable from blades flattened in another direction. This is typically for aesthetic appeal.

We are going to draw lawn stripes in our square garden using a roller in any of the $$$4$$$ cardinal directions. The roller must stay on the lawn throughout. The final direction of a piece of lawn is determined by the last time the roller ran over it, including starting from or finishing there.

Illustration of Sample Input 1.

Given a description of the lawn and the starting point of the roller, determine how to draw the pattern.

Input
  • The first line of input contains the width and depth in metres of the lawn, $$$n$$$ ($$$1 \le n \le 100$$$)

  • The second line of input contains the row and column of the roller, $$$r$$$ and $$$c$$$ ($$$1 \le r, c \le n$$$).

  • Each of the next $$$n$$$ lines contains $$$n$$$ characters from (l|r|u|d) giving the desired direction of a square metre of lawn.
Output

If it is not possible to draw the pattern, output impossible. Otherwise, demonstrate a solution in under $$$10n^2$$$ moves by outputting the number of moves to use on one line, followed by the moves on the remaining lines.

Each move consists of a distance in metres $$$d$$$ and a direction from (l|r|u|d). A roller following the instructions must roll over every square metre without leaving the lawn.

Examples
Input
4
1 4
rrrd
llll
rrru
ulll
Output
8
3 l
3 r
3 d
3 l
1 u
3 r
1 u
3 l
Input
2
1 1
rd
ul
Output
impossible
M. Mid Clocking
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

We have a number of processor slots in a row. The processors are each dedicated to a single task that they can complete before going into a busy-looping mode while they wait for the next instruction.

A processor can run at 100% speed if it has enough cooling, and that requires there be no adjacent processor. If a processor has 1 adjacent processor, it only runs at 60% of maximum speed. If it has 2 adjacent processors it can only run at 30% of maximum speed.

Illustration of Sample Input 2.

We know how many seconds each task will take running on a processor at full speed, starting from $$$t=0$$$, and need to allocate tasks to processors to ensure the last task finishes as soon as possible.

Input
  • The number of tasks to run, $$$n$$$, and the number of processor slots, $$$s$$$ ($$$1 \le n \le s \le 10^6$$$).
  • $$$n$$$ further integers giving the duration of each task $$$t_i$$$ in seconds if performed at 100% speed ($$$1 \le t_i \le 10^9$$$).
Output

Output the minimum time by which all of the tasks can be finished.

The output must be accurate to an absolute or relative error of $$$10^{-6}$$$.

Examples
Input
4 5
1 1000 1 1
Output
1000
Input
7 10
5 2 3 5 4 6 7
Output
8.33333333