vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
To protect people from evil, 
a long and tall wall was constructed a few years ago. 
But just a wall is not safe, there should also be soldiers on it, 
always keeping vigil. 
The wall is very long and connects the left and the right towers. 
There are exactly N spots (numbered 1 to N) on the wall for soldiers. 
The Kth spot is K miles far from the left tower and (N+1-K) miles from the right tower.

Given a permutation of spots P of {1, 2, ..., N}, soldiers occupy the N spots in that order. 
The P[i]th spot is occupied before the P[i+1]th spot. 
When a soldier occupies a spot, he is connected to his nearest soldier already placed to his left. 
If there is no soldier to his left, he is connected to the left tower. The same is the case with right side. 
A connection between two spots requires a wire of length equal to the distance between the two.

The realm has already purchased a wire of M miles long from Nokia, 
possibly the wire will be cut into smaller length wires. 
As we can observe, the total length of the used wire depends on the permutation of the spots P. Help the realm in minimizing the length of the unused wire. If there is not enough wire, output -1.

-----Input-----
First line contains an integer T (number of test cases, 1 ≤ T ≤ 10 ). Each of the next T lines contains two integers N M, as explained in the problem statement (1 ≤ N ≤ 30 , 1 ≤ M ≤ 1000).

-----Output-----
For each test case, output the minimum length of the unused wire, or -1 if the the wire is not sufficient.

-----Example-----
Input:
4
3 8
3 9
2 4
5 25

Output:
0
0
-1
5

Explanation:

In the 1st case, for example, the permutation P = {2, 1, 3} will use the exact 8 miles wires in total.

In the 2nd case, for example, the permutation P = {1, 3, 2} will use the exact 9 miles wires in total.

To understand the first two cases, you can see the following figures:



In the 3rd case, the minimum length of wire required is 5, for any of the permutations {1,2} or {2,1}, so length 4 is not sufficient.

In the 4th case, for the permutation {1, 2, 3, 4, 5} we need the maximum length of the wire = 20. So minimum possible unused wire length = 25 - 20 = 5.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Heidi and Library (medium)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Whereas humans nowadays read fewer and fewer books on paper, book readership among marmots has surged. Heidi has expanded the library and is now serving longer request sequences.

Input Specification:
Same as the easy version, but the limits have changed: 1<=≤<=*n*,<=*k*<=≤<=400<=000.

Output Specification:
Same as the easy version.

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

Demo Output:
['2\n', '3\n', '3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Developing tools for creation of locations maps for turn-based fights in a new game, Petya faced the following problem.

A field map consists of hexagonal cells. Since locations sizes are going to be big, a game designer wants to have a tool for quick filling of a field part with identical enemy units. This action will look like following: a game designer will select a rectangular area on the map, and each cell whose center belongs to the selected rectangle will be filled with the enemy unit.

More formally, if a game designer selected cells having coordinates (x_1, y_1) and (x_2, y_2), where x_1 ≤ x_2 and y_1 ≤ y_2, then all cells having center coordinates (x, y) such that x_1 ≤ x ≤ x_2 and y_1 ≤ y ≤ y_2 will be filled. Orthogonal coordinates system is set up so that one of cell sides is parallel to OX axis, all hexagon centers have integer coordinates and for each integer x there are cells having center with such x coordinate and for each integer y there are cells having center with such y coordinate. It is guaranteed that difference x_2 - x_1 is divisible by 2.

Working on the problem Petya decided that before painting selected units he wants to output number of units that will be painted on the map.

Help him implement counting of these units before painting.

 [Image] 


-----Input-----

The only line of input contains four integers x_1, y_1, x_2, y_2 ( - 10^9 ≤ x_1 ≤ x_2 ≤ 10^9,  - 10^9 ≤ y_1 ≤ y_2 ≤ 10^9) — the coordinates of the centers of two cells.


-----Output-----

Output one integer — the number of cells to be filled.


-----Examples-----
Input
1 1 5 5

Output
13

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function 
```javascript 
tripledouble(num1,num2)
```
```python
triple_double(num1, num2)
```
which takes numbers `num1` and `num2` and returns `1` if there is a straight triple of a number at any place in `num1` and also a straight double of the **same** number in `num2`.

If this isn't the case, return `0`

## Examples

```python
triple_double(451999277, 41177722899) == 1
# num1 has straight triple 999s and num2 has straight double 99s

triple_double(1222345, 12345) == 0
# num1 has straight triple 2s but num2 has only a single 2

triple_double(12345, 12345) == 0

triple_double(666789, 12345667) == 1
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive number $x$. Find the smallest positive integer number that has the sum of digits equal to $x$ and all digits are distinct (unique).


-----Input-----

The first line contains a single positive integer $t$ ($1 \le t \le 50$) — the number of test cases in the test. Then $t$ test cases follow.

Each test case consists of a single integer number $x$ ($1 \le x \le 50$).


-----Output-----

Output $t$ answers to the test cases:

if a positive integer number with the sum of digits equal to $x$ and all digits are different exists, print the smallest such number;

otherwise print -1.


-----Examples-----

Input
4
1
5
15
50
Output
1
5
69
-1


-----Note-----

None

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef wants to buy a new phone, but he is not willing to spend a lot of money. Instead, he checks the price of his chosen model everyday and waits for the price to drop to an acceptable value. So far, he has observed the price for $N$ days (numbere $1$ through $N$); for each valid $i$, the price on the $i$-th day was $P_i$ dollars.
On each day, Chef considers the price of the phone to be good if it is strictly smaller than all the prices he has observed during the previous five days. If there is no record of the price on some of the previous five days (because Chef has not started checking the price on that day yet), then Chef simply ignores that previous day ― we could say that he considers the price on that day to be infinite.
Now, Chef is wondering ― on how many days has he considered the price to be good? Find the number of these days.

-----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$.
- The second line contains $N$ space-separated integers $P_1, P_2, \dots, P_N$.

-----Output-----
For each test case, print a single line containing one integer ― the number of days with a good price.

-----Constraints-----
- $1 \le T \le 100$
- $7 \le N \le 100$
- $350 \le P_i \le 750$ for each valid $i$

-----Subtasks-----
Subtask #1 (30 points): $N = 7$
Subtask #2 (70 points): original constraints

-----Example Input-----
1
7
375 750 723 662 647 656 619

-----Example Output-----
2

-----Explanation-----
Example case 1: Chef considers the price to be good on day $1$, because he has not observed any prices on the previous days. The prices on days $2, 3, 4, 5, 6$ are not considered good because they are greater than the price on day $1$. Finally, the price on day $7$ is considered good because it is smaller than all of the prices on days $2, 3, 4, 5, 6$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The problem was inspired by Pied Piper story. After a challenge from Hooli's compression competitor Nucleus, Richard pulled an all-nighter to invent a new approach to compression: middle-out.

You are given two strings $s$ and $t$ of the same length $n$. Their characters are numbered from $1$ to $n$ from left to right (i.e. from the beginning to the end).

In a single move you can do the following sequence of actions:

  choose any valid index $i$ ($1 \le i \le n$),  move the $i$-th character of $s$ from its position to the beginning of the string or move the $i$-th character of $s$ from its position to the end of the string. 

Note, that the moves don't change the length of the string $s$. You can apply a move only to the string $s$.

For example, if $s=$"test" in one move you can obtain:

  if $i=1$ and you move to the beginning, then the result is "test" (the string doesn't change),  if $i=2$ and you move to the beginning, then the result is "etst",  if $i=3$ and you move to the beginning, then the result is "stet",  if $i=4$ and you move to the beginning, then the result is "ttes",  if $i=1$ and you move to the end, then the result is "estt",  if $i=2$ and you move to the end, then the result is "tste",  if $i=3$ and you move to the end, then the result is "tets",  if $i=4$ and you move to the end, then the result is "test" (the string doesn't change). 

You want to make the string $s$ equal to the string $t$. What is the minimum number of moves you need? If it is impossible to transform $s$ to $t$, print -1.


-----Input-----

The first line contains integer $q$ ($1 \le q \le 100$) — the number of independent test cases in the input.

Each test case is given in three lines. The first line of a test case contains $n$ ($1 \le n \le 100$) — the length of the strings $s$ and $t$. The second line contains $s$, the third line contains $t$. Both strings $s$ and $t$ have length $n$ and contain only lowercase Latin letters.

There are no constraints on the sum of $n$ in the test (i.e. the input with $q=100$ and all $n=100$ is allowed).


-----Output-----

For every test print minimum possible number of moves, which are needed to transform $s$ into $t$, or -1, if it is impossible to do.


-----Examples-----
Input
3
9
iredppipe
piedpiper
4
estt
test
4
tste
test

Output
2
1
2

Input
4
1
a
z
5
adhas
dasha
5
aashd
dasha
5
aahsd
dasha

Output
-1
2
2
3



-----Note-----

In the first example, the moves in one of the optimal answers are:

  for the first test case $s=$"iredppipe", $t=$"piedpiper": "iredppipe" $\rightarrow$ "iedppiper" $\rightarrow$ "piedpiper";  for the second test case $s=$"estt", $t=$"test": "estt" $\rightarrow$ "test";  for the third test case $s=$"tste", $t=$"test": "tste" $\rightarrow$ "etst" $\rightarrow$ "test".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Andryusha goes through a park each day. The squares and paths between them look boring to Andryusha, so he decided to decorate them.

The park consists of n squares connected with (n - 1) bidirectional paths in such a way that any square is reachable from any other using these paths. Andryusha decided to hang a colored balloon at each of the squares. The baloons' colors are described by positive integers, starting from 1. In order to make the park varicolored, Andryusha wants to choose the colors in a special way. More precisely, he wants to use such colors that if a, b and c are distinct squares that a and b have a direct path between them, and b and c have a direct path between them, then balloon colors on these three squares are distinct.

Andryusha wants to use as little different colors as possible. Help him to choose the colors!


-----Input-----

The first line contains single integer n (3 ≤ n ≤ 2·10^5) — the number of squares in the park.

Each of the next (n - 1) lines contains two integers x and y (1 ≤ x, y ≤ n) — the indices of two squares directly connected by a path.

It is guaranteed that any square is reachable from any other using the paths.


-----Output-----

In the first line print single integer k — the minimum number of colors Andryusha has to use.

In the second line print n integers, the i-th of them should be equal to the balloon color on the i-th square. Each of these numbers should be within range from 1 to k.


-----Examples-----
Input
3
2 3
1 3

Output
3
1 3 2 
Input
5
2 3
5 3
4 3
1 3

Output
5
1 3 2 5 4 
Input
5
2 1
3 2
4 3
5 4

Output
3
1 2 3 1 2 


-----Note-----

In the first sample the park consists of three squares: 1 → 3 → 2. Thus, the balloon colors have to be distinct. [Image] Illustration for the first sample. 

In the second example there are following triples of consequently connected squares:   1 → 3 → 2  1 → 3 → 4  1 → 3 → 5  2 → 3 → 4  2 → 3 → 5  4 → 3 → 5  We can see that each pair of squares is encountered in some triple, so all colors have to be distinct. [Image] Illustration for the second sample. 

In the third example there are following triples:   1 → 2 → 3  2 → 3 → 4  3 → 4 → 5  We can see that one or two colors is not enough, but there is an answer that uses three colors only. [Image] Illustration for the third sample.

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

Complete the method that will determine the minimum number of coins needed to make change for a given amount in American currency.

Coins used will be half-dollars, quarters, dimes, nickels, and pennies, worth 50¢, 25¢, 10¢, 5¢ and 1¢, respectively. They'll be represented by the symbols `H`, `Q`, `D`, `N` and `P` (symbols in Ruby, strings in in other languages)

The argument passed in will be an integer representing the value in cents. The return value should be a hash/dictionary/object with the symbols as keys, and the numbers of coins as values. Coins that are not used should not be included in the hash. If the argument passed in is 0, then the method should return an empty hash.

## Examples

```python
make_change(0)   #-->  {}
make_change(1)   #-->  {"P":1}
make_change(43)  #-->  {"Q":1, "D":1, "N":1, "P":3}
make_change(91)  #-->  {"H":1, "Q":1, "D":1, "N":1, "P":1}
```

#### **If you liked this kata, check out [Part 2](https://www.codewars.com/kata/making-change-part-2/ruby).**

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Petya is a beginner programmer. He has already mastered the basics of the C++ language and moved on to learning algorithms. The first algorithm he encountered was insertion sort. Petya has already written the code that implements this algorithm and sorts the given integer zero-indexed array *a* of size *n* in the non-decreasing order. 

Petya uses this algorithm only for sorting of arrays that are permutations of numbers from 0 to *n*<=-<=1. He has already chosen the permutation he wants to sort but he first decided to swap some two of its elements. Petya wants to choose these elements in such a way that the number of times the sorting executes function swap, was minimum. Help Petya find out the number of ways in which he can make the swap and fulfill this requirement.

It is guaranteed that it's always possible to swap two elements of the input permutation in such a way that the number of swap function calls decreases.

Input Specification:
The first line contains a single integer *n* (2<=≤<=*n*<=≤<=5000) — the length of the permutation. The second line contains *n* different integers from 0 to *n*<=-<=1, inclusive — the actual permutation.

Output Specification:
Print two integers: the minimum number of times the swap function is executed and the number of such pairs (*i*,<=*j*) that swapping the elements of the input permutation with indexes *i* and *j* leads to the minimum number of the executions.

Demo Input:
['5\n4 0 3 1 2\n', '5\n1 2 3 4 0\n']

Demo Output:
['3 2\n', '3 4\n']

Note:
In the first sample the appropriate pairs are (0, 3) and (0, 4). 

In the second sample the appropriate pairs are (0, 4), (1, 4), (2, 4) and (3, 4).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alice lives on a flat planet that can be modeled as a square grid of size $n \times n$, with rows and columns enumerated from $1$ to $n$. We represent the cell at the intersection of row $r$ and column $c$ with ordered pair $(r, c)$. Each cell in the grid is either land or water.

 [Image] An example planet with $n = 5$. It also appears in the first sample test. 

Alice resides in land cell $(r_1, c_1)$. She wishes to travel to land cell $(r_2, c_2)$. At any moment, she may move to one of the cells adjacent to where she is—in one of the four directions (i.e., up, down, left, or right).

Unfortunately, Alice cannot swim, and there is no viable transportation means other than by foot (i.e., she can walk only on land). As a result, Alice's trip may be impossible.

To help Alice, you plan to create at most one tunnel between some two land cells. The tunnel will allow Alice to freely travel between the two endpoints. Indeed, creating a tunnel is a lot of effort: the cost of creating a tunnel between cells $(r_s, c_s)$ and $(r_t, c_t)$ is $(r_s-r_t)^2 + (c_s-c_t)^2$.

For now, your task is to find the minimum possible cost of creating at most one tunnel so that Alice could travel from $(r_1, c_1)$ to $(r_2, c_2)$. If no tunnel needs to be created, the cost is $0$.


-----Input-----

The first line contains one integer $n$ ($1 \leq n \leq 50$) — the width of the square grid.

The second line contains two space-separated integers $r_1$ and $c_1$ ($1 \leq r_1, c_1 \leq n$) — denoting the cell where Alice resides.

The third line contains two space-separated integers $r_2$ and $c_2$ ($1 \leq r_2, c_2 \leq n$) — denoting the cell to which Alice wishes to travel.

Each of the following $n$ lines contains a string of $n$ characters. The $j$-th character of the $i$-th such line ($1 \leq i, j \leq n$) is 0 if $(i, j)$ is land or 1 if $(i, j)$ is water.

It is guaranteed that $(r_1, c_1)$ and $(r_2, c_2)$ are land.


-----Output-----

Print an integer that is the minimum possible cost of creating at most one tunnel so that Alice could travel from $(r_1, c_1)$ to $(r_2, c_2)$.


-----Examples-----
Input
5
1 1
5 5
00001
11111
00111
00110
00110

Output
10

Input
3
1 3
3 1
010
101
010

Output
8



-----Note-----

In the first sample, a tunnel between cells $(1, 4)$ and $(4, 5)$ should be created. The cost of doing so is $(1-4)^2 + (4-5)^2 = 10$, which is optimal. This way, Alice could walk from $(1, 1)$ to $(1, 4)$, use the tunnel from $(1, 4)$ to $(4, 5)$, and lastly walk from $(4, 5)$ to $(5, 5)$.

In the second sample, clearly a tunnel between cells $(1, 3)$ and $(3, 1)$ needs to be created. The cost of doing so is $(1-3)^2 + (3-1)^2 = 8$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

When the final results for the employement competition were announced, Nour Eddin Ramadan was thrilled to find his name among the accepted co-Chefs.

However, after a while Nour started wasting time at the kitchen. He would usually spend hours talking to girls, and he even invited a girl to the kitchen pretending that he is the most valuable employer at Chef's restaurant.

When Chef found out about it, he decided that it was time to teach Nour a lesson. Before going home that night, Chef called Nour to his office and asked him to solve the following problem, saying that he better come to work tomorrow with a solution for it, or otherwise, it would be better if he doesn't come at all:

Given T queries, where each query contains a single number Y, Nour has to find the number of pairs A and B, such that the following equation holds true:

A^{2} + B ≤ Y

Where A is any positive integer, and B holds (1 ≤ B ≤ 700).

Nour was really busy that night (Yeah he got that girl to go out with him after all!), and he asked for your help.
 
------ Input ------ 

The first line contains T denoting the number of test cases.

T lines follows, Each line contains a single integer Y denoting the right side of the formula.

------ Output ------ 

For each test print a single line, containing a single number, indicating the answer for the test.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ Y ≤ 10^{10}$
$Note that A must be any positive integer, and B must hold 1 ≤ B ≤ 700.$

----- Sample Input 1 ------ 
4

2

3

4

10000000000
----- Sample Output 1 ------ 
1

2

3

69999300

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recall that a binary search tree is a rooted binary tree, whose nodes each store a key and each have at most two distinguished subtrees, left and right. The key in each node must be greater than any key stored in the left subtree, and less than any key stored in the right subtree.

The depth of a vertex is the number of edges on the simple path from the vertex to the root. In particular, the depth of the root is $0$.

Let's call a binary search tree perfectly balanced if there doesn't exist a binary search tree with the same number of vertices that has a strictly smaller sum of depths of its vertices.

Let's call a binary search tree with integer keys striped if both of the following conditions are satisfied for every vertex $v$:   If $v$ has a left subtree whose root is $u$, then the parity of the key of $v$ is different from the parity of the key of $u$.  If $v$ has a right subtree whose root is $w$, then the parity of the key of $v$ is the same as the parity of the key of $w$. 

You are given a single integer $n$. Find the number of perfectly balanced striped binary search trees with $n$ vertices that have distinct integer keys between $1$ and $n$, inclusive. Output this number modulo $998\,244\,353$.


-----Input-----

The only line contains a single integer $n$ ($1 \le n \le 10^6$), denoting the required number of vertices.


-----Output-----

Output the number of perfectly balanced striped binary search trees with $n$ vertices and distinct integer keys between $1$ and $n$, inclusive, modulo $998\,244\,353$.


-----Examples-----
Input
4

Output
1

Input
3

Output
0



-----Note-----

In the first example, this is the only tree that satisfies the conditions: $\left. \begin{array}{l}{\text{perfectly balanced}} \\{\text{striped}} \\{\text{binary search tree}} \end{array} \right.$

In the second example, here are various trees that don't satisfy some condition: [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 The `hamming distance` between a pair of numbers is the number of binary bits that differ in their binary notation. 
 
# Example

 For `a = 25, b= 87`, the result should be `4`
```
25: 00011001
87: 01010111
```
The `hamming distance` between these two would be 4 ( the `2nd, 5th, 6th, 7th` bit ).


# Input/Output


 - `[input]` integer `a`

  First Number. `1 <= a <= 2^20`


 - `[input]` integer `b`

  Second Number. `1 <= b <= 2^20`


 - `[output]` an integer

  Hamming Distance

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