IU Programming Challenge 2024
A. Luddy Rocks
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Cora is a new student at Luddy! A staunch supporter of her school, Cora wants to display the message LUDDYROCKS on her window, so that everyone knows about her enthusiasm. Armed with a pair of scissors, some tape, and a banner of $$$n$$$ uppercase characters, Cora wants to cut and rearrange the letters from the banner (throwing out the extra letters she doesn't need) and tape them up on her window! Will Cora be able to write her message?

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 100$$$) — the length of the banner.

The second line of each test case contains a string $$$s$$$ of $$$n$$$ uppercase characters — the banner.

Output

For each test case, output YES if Cora will be able to write her message on her window, or NO if she cannot. Any case is accepted (e.g. Yes and nO are allowed).

Example
Input
3
13
WOWLUDDYROCKS
9
OLYSUKRCD
10
YLRDOUCDSK
Output
YES
NO
YES

B. Bus Routes
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It's a new semester, and the first class of the day is in a building you've never been to. Fortunately for you, the building is on the same street as your apartment!

The street has $$$n$$$ bus stops. You live at stop $$$1$$$, and the building is at stop $$$n$$$. There are $$$k$$$ bus routes, where the $$$i$$$th bus route goes back and forth between stops $$$L_i$$$ and $$$R_i$$$. You can get on or off the $$$i$$$th bus at any stop $$$x$$$ such that $$$L_i \leq x \leq R_i$$$. If you are not on any bus, and you are currently at stop $$$x$$$, you can also get to stop $$$y$$$ by walking a distance of $$$|x - y|$$$ blocks.

What is the minimum number of blocks that you'd have to walk to get to the building from your apartment?

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2\cdot10^5$$$, $$$0 \leq k \leq 2\cdot10^5$$$) — the number of bus stops and the number of bus routes.

Each of the following $$$k$$$ lines contains two integers $$$L_i$$$ and $$$R_i$$$ ($$$1 \leq L_i \lt R_i \leq n$$$) — the endpoints of the $$$i$$$th bus route.

Output

For each test case, output the minimum number of blocks that you must walk to go from your apartment to the building.

Example
Input
4
3 1
1 3
5 2
2 3
3 4
10 4
1 3
4 6
5 7
9 10
1 0
Output
0
2
3
0

C. SeaTac
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Seba and Cam are roommates in Seattle. Seba is a frequent flyer, and Cam often has to drive Seba to and from SeaTac airport. Cam's car gets decent gas mileage, but not enough to be driving Seba around Seattle for free all the time, so Cam asks Seba to reimburse him for the gas. Seba needed a ride to SeaTac today, so Seba agreed to fill up Cam's tank when they arrived at SeaTac. The catch is Seba will be giving Cam directions and can direct him anywhere in Seattle, leaving him none the wiser.

Seattle can be modeled as an undirected, connected graph with $$$n$$$ nodes and $$$m$$$ roads. Seba and Cam's house is at node $$$1$$$, and SeaTac is at node $$$n$$$. A path $$$P$$$ of length $$$k$$$ is a sequence of $$$k$$$ nodes such that for all $$$1 \leq i \leq k-1$$$, there is an edge between $$$P_i$$$ and $$$P_{i+1}$$$. Seba can choose any path $$$P$$$ such that $$$P_1 = 1$$$ and $$$P_k = n$$$.

Cam's gas tank can hold $$$g$$$ gallons of gasoline, and it starts off full. It takes one gallon of gasoline to traverse a single road. Whenever Cam runs out of gas, he has to stop and fill up, paying out of his own pocket. Suppose the gas tank has $$$x$$$ gallons when Seba and Cam reach SeaTac. Then, Seba will pay for the remaining $$$g-x$$$ gallons of gasoline.

Seba wants to direct Cam on a route such that the amount of gas Seba is required to pay for is minimized! Seba is far too busy last minute packing for their trip, so they have tasked you with finding an optimal route through Seattle from their house to SeaTac.

Cam's car is European, so the capacity of his gas tank is always prime.

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$g$$$ ($$$2 \leq n \leq 2\cdot10^5$$$, $$$1 \leq m \leq 2\cdot10^5$$$, $$$2 \leq g \leq 2\cdot10^5$$$, $$$g$$$ is prime) — the number of nodes, the number of roads, and the size of Cam's gas tank, respectively.

Each of the following $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i,v_i \leq n$$$, $$$u_i \ne v_i$$$) — $$$i$$$th undirected edge connecting nodes $$$u_i$$$ and $$$v_i$$$.

It is guaranteed that the graph is connected and that there is at most one edge between any pair of nodes.

Output

Output the number of gallons of gasoline that Seba has to pay for.

Examples
Input
5 5 2
1 2
1 3
2 4
3 4
4 5
Output
1
Input
4 3 3
1 2
2 3
3 4
Output
0

D. Assignment Allocation
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ assignments in a course, and $$$d$$$ days in the semester. Assignment $$$i$$$ is assigned at the start of day $$$S_i$$$ and is due by the end of day $$$E_i$$$. Thus, you can work on assignment $$$i$$$ on any day $$$t$$$ such that $$$S_i \leq t \leq E_i$$$.

The professor has a forgiveness policy, where she will drop at most $$$k$$$ missed assignments from the final grade.

You have recently been obsessed with Honkai Star Rail, and decide that you will only complete at most one assignment per day, to make time for your daily quests. As an optimally lazy student, what is the minimum number of missed assignments on your final grade?

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of each test case contains three integers $$$n$$$, $$$d$$$, and $$$k$$$ ($$$1 \leq n,d \leq 2\cdot10^5$$$, $$$0 \leq k \leq n$$$) — the number of assignments, the number of days in the semester, and the maximum number of forgiven assignments, respectively.

Each of the following $$$n$$$ lines contains two integers $$$S_i$$$ and $$$E_i$$$ ($$$1 \leq S_i \leq E_i \leq d$$$) — the assignment start date and end date.

It is guaranteed that the sum of $$$n$$$ over all test cases is at most $$$2 \cdot 10^5$$$, and the sum of $$$d$$$ over all test cases is at most $$$2 \cdot 10^5$$$.

Output

For each test case, output the minimum number of points you will lose if you complete at most one assignment per day.

Example
Input
3
2 1 0
1 1
1 1
3 2 1
1 1
1 2
2 2
9 16 0
1 8
1 5
3 12
1 3
1 3
2 4
2 4
1 1
3 6
Output
1
0
1

E. Mole Whacking Robots
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing Whack-a-mole! There are $$$n$$$ holes arranged in a straight line, each with a mole hiding inside. The game lasts $$$n$$$ seconds. At the start of each second after the game begins, exactly one mole, chosen uniformly at random from the moles that are still hiding, jumps out of its hole for one second. Each mole will jump out of its hole exactly once. To win the game, each mole must be whacked during the second that it jumps out of its hole.

Unfortunately, you are much too slow for this game. That is why you've designed a pair of trusty mole-whacking robots! One robot starts at hole $$$1$$$, and the other starts at hole $$$n$$$. Each robot can move at most a distance of $$$v$$$ holes per second. The time it takes to whack a mole is negligible.

Assuming that the robots move optimally, what is the probability that they win the game for you?

Input

The only line of input contains two integers $$$n$$$ and $$$v$$$ ($$$1 \leq v \leq n \leq 8$$$) — the number of holes and the speed of the robots, respectively.

Output

Output the probability that the robots will win the game as a real number.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, if the jury's answer is $$$a$$$ and your answer is $$$b$$$, then for $$$b$$$ to be considered correct, $$$\frac{|b - a|}{\max(|a|, 1)} \leq 10^{-6}$$$.

Examples
Input
5 1
Output
0.716666666666667
Input
4 1
Output
1.000000000000000

F. Average of Averages
time limit per test
3 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ consisting of $$$n$$$ integers. A nonempty contiguous subarray from $$$l$$$ to $$$r$$$ ($$$1 \leq l \leq r \leq n$$$) has the average value $$$V(l, r) = \frac{1}{r - l + 1} \sum_{i=l}^r a_i$$$. Find the average value of subarray average values. In other words, find the average value of $$$V(l, r)$$$ over all $$$1 \leq l \leq r \leq n$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4)$$$ — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ space-separated integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the array $$$a$$$.

It's guaranteed that the sum of $$$n$$$ over all test cases is at most $$$2\cdot10^5$$$.

Output

For each test case, output the average of subarray averages as a real number.

Your answer will be considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$. Formally, if the jury's answer is $$$a$$$ and your answer is $$$b$$$, then for $$$b$$$ to be considered correct, $$$\frac{|b - a|}{\max(|a|, 1)} \leq 10^{-6}$$$.

Example
Input
2
4
1 2 3 4
1
5
Output
2.500000000000000
5.000000000000000