vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Translator's note: in Russia's most widespread grading system, there are four grades: 5, 4, 3, 2, the higher the better, roughly corresponding to A, B, C and F respectively in American grading system.

The term is coming to an end and students start thinking about their grades. Today, a professor told his students that the grades for his course would be given out automatically  — he would calculate the simple average (arithmetic mean) of all grades given out for lab works this term and round to the nearest integer. The rounding would be done in favour of the student — $4.5$ would be rounded up to $5$ (as in example 3), but $4.4$ would be rounded down to $4$.

This does not bode well for Vasya who didn't think those lab works would influence anything, so he may receive a grade worse than $5$ (maybe even the dreaded $2$). However, the professor allowed him to redo some of his works of Vasya's choosing to increase his average grade. Vasya wants to redo as as few lab works as possible in order to get $5$ for the course. Of course, Vasya will get $5$ for the lab works he chooses to redo.

Help Vasya — calculate the minimum amount of lab works Vasya has to redo.


-----Input-----

The first line contains a single integer $n$ — the number of Vasya's grades ($1 \leq n \leq 100$).

The second line contains $n$ integers from $2$ to $5$ — Vasya's grades for his lab works.


-----Output-----

Output a single integer — the minimum amount of lab works that Vasya has to redo. It can be shown that Vasya can always redo enough lab works to get a $5$.


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

Output
2

Input
4
5 4 5 5

Output
0

Input
4
5 3 3 5

Output
1



-----Note-----

In the first sample, it is enough to redo two lab works to make two $4$s into $5$s.

In the second sample, Vasya's average is already $4.75$ so he doesn't have to redo anything to get a $5$.

In the second sample Vasya has to redo one lab work to get rid of one of the $3$s, that will make the average exactly $4.5$ so the final grade would be $5$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a connected undirected graph consisting of $n$ vertices and $m$ edges. There are no self-loops or multiple edges in the given graph.

You have to direct its edges in such a way that the obtained directed graph does not contain any paths of length two or greater (where the length of path is denoted as the number of traversed edges).


-----Input-----

The first line contains two integer numbers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le 2 \cdot 10^5$) — the number of vertices and edges, respectively.

The following $m$ lines contain edges: edge $i$ is given as a pair of vertices $u_i$, $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$). There are no multiple edges in the given graph, i. e. for each pair ($u_i, v_i$) there are no other pairs ($u_i, v_i$) and ($v_i, u_i$) in the list of edges. It is also guaranteed that the given graph is connected (there is a path between any pair of vertex in the given graph).


-----Output-----

If it is impossible to direct edges of the given graph in such a way that the obtained directed graph does not contain paths of length at least two, print "NO" in the first line.

Otherwise print "YES" in the first line, and then print any suitable orientation of edges: a binary string (the string consisting only of '0' and '1') of length $m$. The $i$-th element of this string should be '0' if the $i$-th edge of the graph should be directed from $u_i$ to $v_i$, and '1' otherwise. Edges are numbered in the order they are given in the input.


-----Example-----
Input
6 5
1 5
2 1
1 4
3 1
6 1

Output
YES
10100



-----Note-----

The picture corresponding to the first example: [Image]

And one of possible answers: $\text{of}$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
 Timed Reading is an educational tool used in many schools to improve and advance reading skills. A young elementary student has just finished his very first timed reading exercise. Unfortunately he's not a very good reader yet, so whenever he encountered a word longer than maxLength, he simply skipped it and read on.

 Help the teacher figure out how many words the boy has read by calculating the number of words in the text he has read, no longer than maxLength.

 Formally, a word is a substring consisting of English letters, such that characters to the left of the leftmost letter and to the right of the rightmost letter are not letters.

# Example

 For `maxLength = 4` and `text = "The Fox asked the stork, 'How is the soup?'"`, the output should be `7`

 The boy has read the following words: `"The", "Fox", "the", "How", "is", "the", "soup".`

# Input/Output


 - `[input]` integer `maxLength`

    A positive integer, the maximum length of the word the boy can read.

    Constraints: `1 ≤ maxLength ≤ 10.`


 - `[input]` string `text`

    A non-empty string of English letters and punctuation marks.


 - `[output]` an integer

    The number of words the boy has read.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You've purchased a ready-meal from the supermarket.

The packaging says that you should microwave it for 4 minutes and 20 seconds, based on a 600W microwave.

Oh no, your microwave is 800W! How long should you cook this for?!

___

# Input

You'll be given 4 arguments:

## 1. needed power
The power of the needed microwave.  
Example: `"600W"`

## 2. minutes
The number of minutes shown on the package.  
Example: `4`

## 3. seconds
The number of seconds shown on the package.  
Example: `20`

## 4. power
The power of your microwave.  
Example: `"800W"`

___

# Output
The amount of time you should cook the meal for formatted as a string.  
Example: `"3 minutes 15 seconds"`

Note: the result should be rounded up.
```
59.2 sec  -->  60 sec  -->  return "1 minute 0 seconds"
```

___


## All comments/feedback/translations appreciated.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).
The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.
 
Example 1:
Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2:
Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3:
Input: s = "1111"
Output: 3

 
Constraints:

2 <= s.length <= 500
The string s consists of characters '0' and '1' only.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Bash and a Tough Math Puzzle

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Bash likes playing with arrays. He has an array *a*1,<=*a*2,<=... *a**n* of *n* integers. He likes to guess the greatest common divisor (gcd) of different segments of the array. Of course, sometimes the guess is not correct. However, Bash will be satisfied if his guess is almost correct.

Suppose he guesses that the gcd of the elements in the range [*l*,<=*r*] of *a* is *x*. He considers the guess to be almost correct if he can change at most one element in the segment such that the gcd of the segment is *x* after making the change. Note that when he guesses, he doesn't actually change the array — he just wonders if the gcd of the segment can be made *x*. Apart from this, he also sometimes makes changes to the array itself.

Since he can't figure it out himself, Bash wants you to tell him which of his guesses are almost correct. Formally, you have to process *q* queries of one of the following forms:
 -  1<=*l*<=*r*<=*x* — Bash guesses that the gcd of the range [*l*,<=*r*] is *x*. Report if this guess is almost correct. -  2<=*i*<=*y* — Bash sets *a**i* to *y*. 
Note: The array is 1-indexed.

Input Specification:
The first line contains an integer *n* (1<=≤<=*n*<=≤<=5·105)  — the size of the array.

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109)  — the elements of the array.

The third line contains an integer *q* (1<=≤<=*q*<=≤<=4·105)  — the number of queries.

The next *q* lines describe the queries and may have one of the following forms:
 -  1<=*l*<=*r*<=*x* (1<=≤<=*l*<=≤<=*r*<=≤<=*n*,<=1<=≤<=*x*<=≤<=109). -  2<=*i*<=*y* (1<=≤<=*i*<=≤<=*n*,<=1<=≤<=*y*<=≤<=109). 
Guaranteed, that there is at least one query of first type.

Output Specification:
For each query of first type, output "YES" (without quotes) if Bash's guess is almost correct and "NO" (without quotes) otherwise.

Demo Input:
['3\n2 6 3\n4\n1 1 2 2\n1 1 3 3\n2 1 9\n1 1 3 2\n', '5\n1 2 3 4 5\n6\n1 1 4 2\n2 3 6\n1 1 4 2\n1 1 5 2\n2 5 10\n1 1 5 2\n']

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

Note:
In the first sample, the array initially is {2, 6, 3}. 

For query 1, the first two numbers already have their gcd as 2.

For query 2, we can achieve a gcd of 3 by changing the first element of the array to 3. Note that the changes made during queries of type 1 are temporary and do not get reflected in the array. 

After query 3, the array is now {9, 6, 3}.

 For query 4, no matter which element you change, you cannot get the gcd of the range to be 2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Burenka came to kindergarden. This kindergarten is quite strange, so each kid there receives two fractions ($\frac{a}{b}$ and $\frac{c}{d}$) with integer numerators and denominators. Then children are commanded to play with their fractions.

Burenka is a clever kid, so she noticed that when she claps once, she can multiply numerator or denominator of one of her two fractions by any integer of her choice (but she can't multiply denominators by $0$). Now she wants know the minimal number of claps to make her fractions equal (by value). Please help her and find the required number of claps!


-----Input-----

The first line contains one integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. Then follow the descriptions of each test case.

The only line of each test case contains four integers $a$, $b$, $c$ and $d$ ($0 \leq a, c \leq 10^9$, $1 \leq b, d \leq 10^9$) — numerators and denominators of the fractions given to Burenka initially.


-----Output-----

For each test case print a single integer — the minimal number of claps Burenka needs to make her fractions equal.


-----Examples-----

Input
8
2 1 1 1
6 3 2 1
1 2 2 3
0 1 0 100
0 1 228 179
100 3 25 6
999999999 300000000 666666666 100000000
33 15 0 84
Output
1
0
2
0
1
1
1
1


-----Note-----

In the first case, Burenka can multiply $c$ by $2$, then the fractions will be equal.

In the second case, fractions are already equal.

In the third case, Burenka can multiply $a$ by $4$, then $b$ by $3$. Then the fractions will be equal ($\frac{1 \cdot 4}{2 \cdot 3} = \frac{2}{3}$).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We define the *goodness* of any array B of length M as: \sum_{i = 1}^{M - 1} |B_{i + 1} - B_{i}| (Here |X| denotes the absolute value of X). In particular, *goodness* of any array of length 1 is 0.

Alice and Bob have an array A containing N distinct elements and they play a game with it.  
Alice starts the game after which both the players make moves alternatively. In one move:
A player can delete any subarray from A such that the *goodness* of A does not change. 
 
Formally, the player chooses indices L and R such that 1 ≤ L ≤ R ≤ \mathrm{length}(A) and removes the subarray [A_{L}, A_{L + 1}, \ldots, A_{R}] from A such that the *goodness* of A does not change.

For e.g. A = [3, 1, 2, 4], a player can select L = 3, R = 3, then the resulting array will be [3, 1, 4]. Initially, the *goodness* was |1-3| + |2-1| + |4-2| = 5. After the move, the *goodness* is |1-3| + |4-1| = 5. Here we can observe that the goodness does not change.

The player who is not able to make a move loses. If both the players play optimally, determine who out of Alice and Bob will win the game.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, output the winner of the game if both players play optimally.

You may print each character of Alice and Bob in uppercase or lowercase (for example, aLiCe, ALIce, alice will be considered identical).

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

$1 ≤ T ≤ 10^{5}$
$2 ≤N ≤10^{5}$
$1 ≤A_{i} ≤10^{9}$
- All $A_{i}$ are distinct.
- Sum of $N$ over all test cases does not exceed $10^{6}$.

----- Sample Input 1 ------ 
2
3
1 3 2
4
1 2 3 4

----- Sample Output 1 ------ 
Bob
Alice

----- explanation 1 ------ 
Test case 1: Alice can not make any moves such that the goodness of the array does not change. Therefore Bob wins.

Test case 2: Alice can choose $L = 2, R = 3$ and remove the subarray $[A_{2}, A_{3}]$. The resulting array is $[1, 4]$.
- *Goodness* of the array before the operation $ = |2-1|+|3-2|+|4-3| = 3$.
- *Goodness* of the array after the operation $ = |4-1| = 3$.

Thus, the array has the same goodness as before. Now Bob can not make any move. Therefore Alice wins.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Limak is a little bear who loves to play. Today he is playing by destroying block towers. He built *n* towers in a row. The *i*-th tower is made of *h**i* identical blocks. For clarification see picture for the first sample.

Limak will repeat the following operation till everything is destroyed.

Block is called internal if it has all four neighbors, i.e. it has each side (top, left, down and right) adjacent to other block or to the floor. Otherwise, block is boundary. In one operation Limak destroys all boundary blocks. His paws are very fast and he destroys all those blocks at the same time.

Limak is ready to start. You task is to count how many operations will it take him to destroy all towers.

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

The second line contains *n* space-separated integers *h*1,<=*h*2,<=...,<=*h**n* (1<=≤<=*h**i*<=≤<=109) — sizes of towers.

Output Specification:
Print the number of operations needed to destroy all towers.

Demo Input:
['6\n2 1 4 6 2 2\n', '7\n3 3 3 1 3 3 3\n']

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

Note:
The picture below shows all three operations for the first sample test. Each time boundary blocks are marked with red color.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a table consisting of *n* rows and *m* columns. Each cell of the table contains a number, 0 or 1. In one move we can choose some row of the table and cyclically shift its values either one cell to the left, or one cell to the right.

To cyclically shift a table row one cell to the right means to move the value of each cell, except for the last one, to the right neighboring cell, and to move the value of the last cell to the first cell. A cyclical shift of a row to the left is performed similarly, but in the other direction. For example, if we cyclically shift a row "00110" one cell to the right, we get a row "00011", but if we shift a row "00110" one cell to the left, we get a row "01100".

Determine the minimum number of moves needed to make some table column consist only of numbers 1.

Input Specification:
The first line contains two space-separated integers: *n* (1<=≤<=*n*<=≤<=100) — the number of rows in the table and *m* (1<=≤<=*m*<=≤<=104) — the number of columns in the table. Then *n* lines follow, each of them contains *m* characters "0" or "1": the *j*-th character of the *i*-th line describes the contents of the cell in the *i*-th row and in the *j*-th column of the table.

It is guaranteed that the description of the table contains no other characters besides "0" and "1".

Output Specification:
Print a single number: the minimum number of moves needed to get only numbers 1 in some column of the table. If this is impossible, print -1.

Demo Input:
['3 6\n101010\n000100\n100000\n', '2 3\n111\n000\n']

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

Note:
In the first sample one way to achieve the goal with the least number of moves is as follows: cyclically shift the second row to the right once, then shift the third row to the left twice. Then the table column before the last one will contain only 1s.

In the second sample one can't shift the rows to get a column containing only 1s.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are the boss of ACM (Apples, Cherries, and Mangos), an upstanding company with a single goal of world domination.

ACM have provided lots of fruits for the last programming competition for minions in Helsinki. The leftovers should now be shipped to Singapore. There is, however, one constraint: In the case that one box of apples is infested with apple-eating insects and the next one in the line is also a box of apples, the insects might move on to the neighboring box and infect it as well. This constraint is applicable for boxes of cherries and boxes of mangos too.

In order to avoid this, ACM decides that the boxes of fruits are to be sent in such a way that two consecutive boxes contain different types of fruits. The statistics department of ACM wants to know how many ways there are to arrange the shipments of $A$ boxes of apples, $C$ boxes of cherries and $M$ boxes of mangos under this constraint.

Please provide a computer program to compute this for various choices of $A$, $C$, and $M$. Two arrangements are different if there exists $i$ such that the $i$-th box delivered in the two arrangements contain different types of fruits. Since the answer may be very big, output the answer modulo a prime number $10^9+7$.

-----Input-----
The input consists of a single line consisting of three single space separated integers $A$, $C$, and $M$, denoting the total number of boxes of apples, cherries, and mangos you need to ship to Singapore, respectively. All three integers will be between $1$ and $200000$, respectively.

-----Output-----
Output the number of different possible arrangements of delivery, modulo a prime number $10^9+7$. If there is no such order, output $0$.Sample Data Explanation

In the first example, the $6$ possible ways are:
 - Apple, Cherry, Mango, Cherry.
 - Cherry, Apple, Cherry, Mango.
 - Cherry, Apple, Mango, Cherry.
 - Cherry, Mango, Apple, Cherry.
 - Cherry, Mango, Cherry, Apple.
 - Mango, Cherry, Apple, Cherry.

-----Examples-----
Sample Input 1:
1 2 1
Sample Output 1:
6

Sample Input 2:
2 2 2
Sample Output 2:
30

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
_This kata is based on [Project Euler Problem 546](https://projecteuler.net/problem=546)_

# Objective

Given the recursive sequence 

fk(n) =


∑

i
=
0


n



fk(floor(i / k)) where fk(0) = 1

Define a function `f` that takes arguments `k` and `n` and returns the nth term in the sequence fk

## Examples

`f(2, 3)` = f2(3) = 6

`f(2, 200)` = f2(200) = 7389572

`f(7, 500)` = f7(500) = 74845

`f(1000, 0)` = f1000(0) = 1


**Note:** 
No error checking is needed, `k` ranges from 2 to 100 and `n` ranges between 0 and 500000 (mostly small and medium values with a few large ones)


As always any feedback would be much appreciated

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The four bases found in DNA are adenine (A), cytosine (C), guanine (G) and thymine (T).

In genetics, GC-content is the percentage of Guanine (G) and Cytosine (C) bases on a DNA molecule that are either guanine or cytosine. 

Given a DNA sequence (a string) return the GC-content in percent, rounded up to 2 decimal digits for Python, not rounded in all other languages.

For more information about GC-content you can take a look to [wikipedia GC-content](https://en.wikipedia.org/wiki/GC-content).

**For example**: the GC-content of the following DNA sequence is 50%:
"AAATTTCCCGGG".

**Note**: You can take a look to my others bio-info kata [here](http://www.codewars.com/users/nbeck/authored)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After six days, professor GukiZ decided to give more candies to his students. Like last time, he has $N$ students, numbered $1$ through $N$. Let's denote the number of candies GukiZ gave to the $i$-th student by $p_i$. As GukiZ has a lot of students, he does not remember all the exact numbers of candies he gave to the students. He only remembers the following properties of the sequence $p$:
- The numbers of candies given to each of the first $K$ students ($p_1, p_2, \dots, p_K$) are known exactly.
- All elements of the sequence $p$ are distinct and positive.
- GukiZ didn't give more than $x$ candies to any student (the maximum value in the sequence $p$ is not greater than $x$).
- For each student $i$, there is at least one other student $j$ such that $|p_i - p_j| \le D$.
- The professor gave out the biggest possible total number of candies, i.e. $S = p_1 + p_2 + p_3 + \ldots + p_N$ is maximum possible.
GukiZ would like to know the total number of candies $S$ he had at the beginning. However, times change and after six days, the professor is really tired, so it is possible that there is no sequence $p$ which satisfies the constraints. Can you help GukiZ find the number of candies he gave out, or tell him that he must have made a mistake?

-----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 four space-separated integers $N$, $K$, $x$, $D$.
- The second line contains $K$ distinct space-separated integers $p_1, p_2, \dots, p_K$.

-----Output-----
For each test case, print a single line containing one integer — the number of candies GukiZ had, or $-1$ if there is no valid sequence $p$.

-----Constraints-----
- $1 \le T \le 50$
- $3 \le N \le 10^9$
- $1 \le K \le \mathrm{min}(N, 2 \cdot 10^4)$ 
- $1 \le x \le 2 \cdot 10^9$
- $1 \le D \le 10^9$
- $1 \le p_i \le x$ for each valid $i$
- All values $p_i$ from input are distinct

-----Subtasks-----
Subtask #1 (15 points): $1 \leq x, N, D \leq 15$ 
Subtask #2 (35 points): $1 \leq x, N, D \leq 10^5$ 
Subtask #3 (50 points): original constraints

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

-----Example Output-----
12
-1

-----Explanation-----
Example case 1: There are four students. We know that the first student got $p_1 = 2$ candies, the second student got $p_2 = 1$ and the third got $p_3 = 5$ candies; we don't know the number of candies given to the last student. The maximum possible amount of candies given to some student is $x=5$. The best possible option is giving $p_4=4$ candies to the last student. Then, the fourth constraint (with $D=3$) is satisfied for all students. Only the pair of students $(2, 3)$ have numbers of candies that differ by more than $3$, but still, for each student, there are at least two other students with close enough numbers of candies.
Example case 2: GukiZ made some mistake in distribution and there is no valid sequence $p$. The answer is $-1$.

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