vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Neverending competitions

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are literally dozens of snooker competitions held each year, and team Jinotega tries to attend them all (for some reason they prefer name "snookah")! When a competition takes place somewhere far from their hometown, Ivan, Artsem and Konstantin take a flight to the contest and back.

Jinotega's best friends, team Base have found a list of their itinerary receipts with information about departure and arrival airports. Now they wonder, where is Jinotega now: at home or at some competition far away? They know that: 
 -  this list contains all Jinotega's flights in this year (in arbitrary order), -  Jinotega has only flown from his hometown to a snooker contest and back, -  after each competition Jinotega flies back home (though they may attend a competition in one place several times), -  and finally, at the beginning of the year Jinotega was at home. 
Please help them to determine Jinotega's location!

Input Specification:
In the first line of input there is a single integer *n*: the number of Jinotega's flights (1<=≤<=*n*<=≤<=100). In the second line there is a string of 3 capital Latin letters: the name of Jinotega's home airport. In the next *n* lines there is flight information, one flight per line, in form "XXX-&gt;YYY", where "XXX" is the name of departure airport "YYY" is the name of arrival airport. Exactly one of these airports is Jinotega's home airport.

It is guaranteed that flights information is consistent with the knowledge of Jinotega's friends, which is described in the main part of the statement.

Output Specification:
If Jinotega is now at home, print "home" (without quotes), otherwise print "contest".

Demo Input:
['4\nSVO\nSVO-&gt;CDG\nLHR-&gt;SVO\nSVO-&gt;LHR\nCDG-&gt;SVO\n', '3\nSVO\nSVO-&gt;HKT\nHKT-&gt;SVO\nSVO-&gt;RAP\n']

Demo Output:
['home\n', 'contest\n']

Note:
In the first sample Jinotega might first fly from SVO to CDG and back, and then from SVO to LHR and back, so now they should be at home. In the second sample Jinotega must now be at RAP because a flight from RAP back to SVO is not on the list.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Army

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
The Berland Armed Forces System consists of *n* ranks that are numbered using natural numbers from 1 to *n*, where 1 is the lowest rank and *n* is the highest rank.

One needs exactly *d**i* years to rise from rank *i* to rank *i*<=+<=1. Reaching a certain rank *i* having not reached all the previous *i*<=-<=1 ranks is impossible.

Vasya has just reached a new rank of *a*, but he dreams of holding the rank of *b*. Find for how many more years Vasya should serve in the army until he can finally realize his dream.

Input Specification:
The first input line contains an integer *n* (2<=≤<=*n*<=≤<=100). The second line contains *n*<=-<=1 integers *d**i* (1<=≤<=*d**i*<=≤<=100). The third input line contains two integers *a* and *b* (1<=≤<=*a*<=&lt;<=*b*<=≤<=*n*). The numbers on the lines are space-separated.

Output Specification:
Print the single number which is the number of years that Vasya needs to rise from rank *a* to rank *b*.

Demo Input:
['3\n5 6\n1 2\n', '3\n5 6\n1 3\n']

Demo Output:
['5\n', '11\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Chess Tourney

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Berland annual chess tournament is coming!

Organizers have gathered 2·*n* chess players who should be divided into two teams with *n* people each. The first team is sponsored by BerOil and the second team is sponsored by BerMobile. Obviously, organizers should guarantee the win for the team of BerOil.

Thus, organizers should divide all 2·*n* players into two teams with *n* people each in such a way that the first team always wins.

Every chess player has its rating *r**i*. It is known that chess player with the greater rating always wins the player with the lower rating. If their ratings are equal then any of the players can win.

After teams assignment there will come a drawing to form *n* pairs of opponents: in each pair there is a player from the first team and a player from the second team. Every chess player should be in exactly one pair. Every pair plays once. The drawing is totally random.

Is it possible to divide all 2·*n* players into two teams with *n* people each so that the player from the first team in every pair wins regardless of the results of the drawing?

Input Specification:
The first line contains one integer *n* (1<=≤<=*n*<=≤<=100).

The second line contains 2·*n* integers *a*1,<=*a*2,<=... *a*2*n* (1<=≤<=*a**i*<=≤<=1000).

Output Specification:
If it's possible to divide all 2·*n* players into two teams with *n* people each so that the player from the first team in every pair wins regardless of the results of the drawing, then print "YES". Otherwise print "NO".

Demo Input:
['2\n1 3 2 4\n', '1\n3 3\n']

Demo Output:
['YES\n', 'NO\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shivam owns a gambling house, which has a special wheel called The Wheel of Fortune. 
This wheel is meant for giving free coins to people coming in the house. 

The wheel of fortune is a game of chance. It uses a spinning wheel with exactly N numbered pockets and a coin is placed in between every consecutive pocket. The wheel is spun in either of the two ways.
Before the wheel is turned, all the coins are restored and players bet on a number K.
Then a needle is made to point to any one of the pocket which has number K written on it.
Wheel is then spun till the needle encounters number K again and the player gets all the coins the needle has encountered.

Shivam being the owner of the gambling house, has the authority to place the needle on any of the K numbered pockets and also he could rotate the wheel in either of the two ways.
Shivam has to figure out a way to minimize number of coins that he has to spend on every given bet.
You are given a wheel having N elements and Q players. Each player bets on a number K from the wheel. For each player you have to print minimum number of coins Shivam has to spend.


-----Input-----
- The first line of the input contains an integer T denoting the number of test cases . The description of T testcases follow.

- The first line of each test case contains single integer N .

- The second line of each test case contains N space seperated integers denoting the numbers on the wheel.

- The third line of each test case contains a single integer Q denoting the number of players.
- Then, Q lines follow a single integer K from the N numbers of the wheel 

-----Output-----
For each player, output the minimum number of coins Shivam has to spend.


-----Constraints-----

- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 100000
- 1 ≤ Number written on the Wheel ≤ 1000
- 1 ≤ Q ≤ 10000
- 1 ≤ K ≤ 1000
-  It is guaranteed that K belongs to the N numbers written on the wheel.

-----Example-----
Input:

2

3

1 2 3

3

1

2

3

6

2 1 5 3 2 1

4

1

2

3

5
Output:

3

3

3

2

2

6

6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are integers S and P.
Is there a pair of positive integers (N,M) such that N + M = S and N \times M = P?

-----Constraints-----
 - All values in input are integers.
 - 1 \leq S,P \leq 10^{12}

-----Input-----
Input is given from Standard Input in the following format:
S P

-----Output-----
If there is a pair of positive integers (N,M) such that N + M = S and N \times M = P, print Yes; otherwise, print No.

-----Sample Input-----
3 2

-----Sample Output-----
Yes

 - For example, we have N+M=3 and N \times M =2 for N=1,M=2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While creating high loaded systems one should pay a special attention to caching. This problem will be about one of the most popular caching algorithms called LRU (Least Recently Used).

Suppose the cache may store no more than k objects. At the beginning of the workflow the cache is empty. When some object is queried we check if it is present in the cache and move it here if it's not. If there are more than k objects in the cache after this, the least recently used one should be removed. In other words, we remove the object that has the smallest time of the last query.

Consider there are n videos being stored on the server, all of the same size. Cache can store no more than k videos and caching algorithm described above is applied. We know that any time a user enters the server he pick the video i with probability pi. The choice of the video is independent to any events before.

The goal of this problem is to count for each of the videos the probability it will be present in the cache after 10100 queries.

Input

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 20) — the number of videos and the size of the cache respectively. Next line contains n real numbers pi (0 ≤ pi ≤ 1), each of them is given with no more than two digits after decimal point.

It's guaranteed that the sum of all pi is equal to 1.

Output

Print n real numbers, the i-th of them should be equal to the probability that the i-th video will be present in the cache after 10100 queries. You answer will be considered correct if its absolute or relative error does not exceed 10 - 6. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if <image>.

Examples

Input

3 1
0.3 0.2 0.5


Output

0.3 0.2 0.5 

Input

2 1
0.0 1.0


Output

0.0 1.0 

Input

3 2
0.3 0.2 0.5


Output

0.675 0.4857142857142857 0.8392857142857143 

Input

3 3
0.2 0.3 0.5


Output

1.0 1.0 1.0 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Points on the line

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
We've got no test cases. A big olympiad is coming up. But the problemsetters' number one priority should be adding another problem to the round. 

The diameter of a multiset of points on the line is the largest distance between two points from this set. For example, the diameter of the multiset {1,<=3,<=2,<=1} is 2.

Diameter of multiset consisting of one point is 0.

You are given *n* points on the line. What is the minimum number of points you have to remove, so that the diameter of the multiset of the remaining points will not exceed *d*?

Input Specification:
The first line contains two integers *n* and *d* (1<=≤<=*n*<=≤<=100,<=0<=≤<=*d*<=≤<=100) — the amount of points and the maximum allowed diameter respectively.

The second line contains *n* space separated integers (1<=≤<=*x**i*<=≤<=100) — the coordinates of the points.

Output Specification:
Output a single integer — the minimum number of points you have to remove.

Demo Input:
['3 1\n2 1 4\n', '3 0\n7 7 7\n', '6 3\n1 3 4 6 9 10\n']

Demo Output:
['1\n', '0\n', '3\n']

Note:
In the first test case the optimal strategy is to remove the point with coordinate 4. The remaining points will have coordinates 1 and 2, so the diameter will be equal to 2 - 1 = 1.

In the second test case the diameter is equal to 0, so its is unnecessary to remove any points. 

In the third test case the optimal strategy is to remove points with coordinates 1, 9 and 10. The remaining points will have coordinates 3, 4 and 6, so the diameter will be equal to 6 - 3 = 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a binary tree, print nodes of extreme corners of each level but in alternate order.
Example:
For the above tree, the output is
1 2 7 8 31
– print rightmost node of 1st level
– print leftmost node of 2nd level
– print rightmost node of 3rd level
– print leftmost node of 4th level
– print rightmost node of 5th level
Example 1:
Input:
       1
     /  \
    2    3
Output: 1 2
Explanation: This represents a tree
with 3 nodes and 2 edges where root
is 1, left child of 1 is 3 and
right child of 1 is 2.
Your Task:
You don't have to take any input. Just complete the function ExtremeNodes() that takes root node as paramter  and return the answer (as vector in cpp, as ArrayList in Java, as list in python)
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ Number of nodes ≤ 100
1 ≤ Data of a node ≤ 1000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a string $s[1 \dots n]$ consisting of lowercase Latin letters. It is guaranteed that $n = 2^k$ for some integer $k \ge 0$.

The string $s[1 \dots n]$ is called $c$-good if at least one of the following three conditions is satisfied:  The length of $s$ is $1$, and it consists of the character $c$ (i.e. $s_1=c$); The length of $s$ is greater than $1$, the first half of the string consists of only the character $c$ (i.e. $s_1=s_2=\dots=s_{\frac{n}{2}}=c$) and the second half of the string (i.e. the string $s_{\frac{n}{2} + 1}s_{\frac{n}{2} + 2} \dots s_n$) is a $(c+1)$-good string;  The length of $s$ is greater than $1$, the second half of the string consists of only the character $c$ (i.e. $s_{\frac{n}{2} + 1}=s_{\frac{n}{2} + 2}=\dots=s_n=c$) and the first half of the string (i.e. the string $s_1s_2 \dots s_{\frac{n}{2}}$) is a $(c+1)$-good string. 

For example: "aabc" is 'a'-good, "ffgheeee" is 'e'-good.

In one move, you can choose one index $i$ from $1$ to $n$ and replace $s_i$ with any lowercase Latin letter (any character from 'a' to 'z').

Your task is to find the minimum number of moves required to obtain an 'a'-good string from $s$ (i.e. $c$-good string for $c=$ 'a'). It is guaranteed that the answer always exists.

You have to answer $t$ independent test cases.

Another example of an 'a'-good string is as follows. Consider the string $s = $"cdbbaaaa". It is an 'a'-good string, because:  the second half of the string ("aaaa") consists of only the character 'a';  the first half of the string ("cdbb") is 'b'-good string, because:   the second half of the string ("bb") consists of only the character 'b';  the first half of the string ("cd") is 'c'-good string, because:   the first half of the string ("c") consists of only the character 'c';  the second half of the string ("d") is 'd'-good string.   


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains one integer $n$ ($1 \le n \le 131~072$) — the length of $s$. It is guaranteed that $n = 2^k$ for some integer $k \ge 0$. The second line of the test case contains the string $s$ consisting of $n$ lowercase Latin letters.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer — the minimum number of moves required to obtain an 'a'-good string from $s$ (i.e. $c$-good string with $c =$ 'a'). It is guaranteed that the answer exists.


-----Example-----
Input
6
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z
2
ac

Output
0
7
4
5
1
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef bought a huge (effectively infinite) planar island and built $N$ restaurants (numbered $1$ through $N$) on it. For each valid $i$, the Cartesian coordinates of restaurant $i$ are $(X_i, Y_i)$.
Now, Chef wants to build $N-1$ straight narrow roads (line segments) on the island. The roads may have arbitrary lengths; restaurants do not have to lie on the roads. The slope of each road must be $1$ or $-1$, i.e. for any two points $(x_1, y_1)$ and $(x_2, y_2)$ on the same road, $|x_1-x_2| = |y_1-y_2|$ must hold.
Let's denote the minimum distance Chef has to walk from restaurant $i$ to reach a road by $D_i$. Then, let's denote $a = \mathrm{max}\,(D_1, D_2, \ldots, D_N)$; Chef wants this distance to be minimum possible.
Chef is a busy person, so he decided to give you the job of building the roads. You should find a way to build them that minimises $a$ and compute $a \cdot \sqrt{2}$.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- $N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $X_i$ and $Y_i$.

-----Output-----
For each test case, print a single line containing one real number — the minimum distance $a$ multiplied by $\sqrt{2}$. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

-----Constraints-----
- $1 \le T \le 100$
- $2 \le N \le 10^4$
- $|X_i|, |Y_i| \le 10^9$ for each valid $i$

-----Subtasks-----
Subtask #1 (10 points):
- $1 \le T \le 10$
- $2 \le N \le 5$
- $|X_i|, |Y_i| \le 10$ for each valid $i$
- $a \cdot \sqrt{2}$ is an integer
Subtask #2 (90 points): original constraints

-----Example Input-----
2
3
0 0
0 1
0 -1
3
0 1
1 0
-1 0

-----Example Output-----
0.5
0

-----Explanation-----
Example case 1: We should build roads described by equations $y-x+0.5 = 0$ and $y-x-0.5 = 0$.
Example case 2: We should build roads described by equations $y-x-1 = 0$ and $y+x-1 = 0$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given two binary strings A and B, each of length N. You can perform the following operation on string A any number of times:
Select a [prime number] X.
Choose any substring of string A having length X and reverse the substring.

Determine whether you can make the string A equal to B using any (possibly zero) number of operations.

A substring is obtained by deleting some (possibly zero) elements from the beginning and some (possibly zero) elements from the end of the string.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input.
- The first line of each test case contains an integer N — the length of the strings A and B.
- The second line contains the binary string A.
- The third line contains the binary string B.

------ Output Format ------ 

For each test case, output on a new line, YES, if you can make the string A equal to B using any number of operations and NO otherwise.

You can print each character in uppercase or lowercase. For example, YES, yes, Yes, and yES are all identical.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{5}$
$A_{i}$ and $B_{i}$ contain $0$ and $1$ only.
- The sum of $N$ over all test cases won't exceed $10^{5}$.

----- Sample Input 1 ------ 
4
2
00
00
4
1001
0111
5
11000
10010
5
11000
11010

----- Sample Output 1 ------ 
YES
NO
YES
NO

----- explanation 1 ------ 
Test case $1$: Both the strings are equal. Thus, we do not need any operations.

Test case $2$: It can be shown that we cannot make the string $A$ equal to $B$ using any number of operations.

Test case $3$: Choose $X = 3$ and reverse the substring $A[2,4] = 100$. Thus, the string $A$ becomes $10010$ which is equal to $B$.

Test case $4$: It can be shown that we cannot make the string $A$ equal to $B$ using any number of operations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are operating a taxi company in the Land of Bytes, which is an interesting city. First, all roads in the city either along the north-south direction or along the east-west direction. Second, it’s an extremely large city such that the sizes of blocks between different roads are negligible. Therefore, each position in this city can be represented by coordinates $(x, y)$ of real values.

The taxi drivers always takes the shortest path between the pick-up and drop-off points, following streets. Your company only operates the taxis within the central business district (CBD), which is a convex polygon of $n$ points.

Assuming the pick-up and drop-off points from the passengers are chosen, uniformly at random, from inside the CBD, what is the expected distance that a taxi will travel? Assume the taxi travel distance between any points $(x, y)$ and $(x_1, y_1)$ is always $|x-x_1|+|y-y_1|$.

-----Input-----
The first line contains an integer $n$ ($3 \le n \le 100000$).

Following this will be $n$ lines, each with two integer values values ($x, y$) representing the points on the border of CBD, where $|x|,|y| < 10^9$. The points are presented in a clockwise order and there will be no three points on the same line.

-----Output-----
The output is a single line containing one number, the expected distance expressed with a relative or absolute error less than $10^{-6}$.

-----Examples-----
Sample Input 1:
4
0 0
0 1
1 1
1 0
Sample Output 1:
0.666666666666667

Sample Input 2:
3
0 0
1 1
2 0
Sample Output 2:
0.733333333333333

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sinchan and his friends loves to eat. They have a 2D rectangular cake which they want to share. Sinchan is very kind and offers his friends to eat the cake first, all friends goes one by one to eat the cake. Each friend will cut cake into two parts. First part of the cake will be largest possible square from the cake, that the friend will eat, and will leave the second part for others, it continues untill cake is over or every friend gets to eat the cake.
Now Sinchan wonder how much cake would he be able to get.

-----Input-----
- First line of input contain T, denoting number of test case.
- First line of each test case contains N, denoting number of friends.
- Second line of test case contain L, B (L x B) denoting dimension of cake.

-----Output-----
- For each test case, if Sinchan gets to eat the cake print (without quotes) "Yes #" where # is area of cake that Sinchan gets. Otherwise print  (without quotes) "No"

-----Constraints-----
- 1 ≤ T, N, L, B ≤ 1000

-----Example-----
Input:
3
2
5 3
4
4 8
1
1 2

Output:
Yes 2
No
Yes 1

-----Explanation-----
Example case 1. First friend divides 5x3 cake in 3x3 and 2x3 since 3x3 is largest possible square, second Friend divides 2x3 cake in 2x2 and 1x2 and eat 2x2 piece. Finaly Sinchan gets to eat and area of cake is 1*2 hence Output is (without quotes) "Yes 2"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.