1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Lucky Ticket
Contest: Codeforces Round 104 (Div. 2)
Difficulty rating: 800
Tags: implementation

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya loves tickets very much. As we know, each ticket has a number that is a positive integer. Its length equals n (n is always even). Petya calls a ticket lucky if the ticket's number is a lucky number and the sum of digits in the first half (the sum of the first n / 2 digits) equals the sum of digits in the second half (the sum of the last n / 2 digits). Check if the given ticket is lucky.

Input format:
The first line contains an even integer n (2 ≤ n ≤ 50) — the length of the ticket number that needs to be checked. The second line contains an integer whose length equals exactly n — the ticket number. The number may contain leading zeros.

Output format:
On the first line print "YES" if the given ticket number is lucky. Otherwise, print "NO" (without the quotes).

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample the sum of digits in the first half does not equal the sum of digits in the second half (4 ≠ 7).

In the second sample the ticket number is not the lucky number.

Example input:
2
47

Example output:
NO

Example input:
4
4738

Example output:
NO

Editorial:
Lucky Mask
Contest: Codeforces Round 104 (Div. 2)
Difficulty rating: 1300
Tags: brute force, implementation

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive integers whose decimal record contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Petya calls a mask of a positive integer n the number that is obtained after successive writing of all lucky digits of number n from the left to the right. For example, the mask of number 72174994 is number 7744, the mask of 7 is 7, the mask of 9999047 is 47. Obviously, mask of any number is always a lucky number.

Petya has two numbers — an arbitrary integer a and a lucky number b. Help him find the minimum number c (c > a) such that the mask of number c equals b.

Input format:
The only line contains two integers a and b (1 ≤ a, b ≤ 105). It is guaranteed that number b is lucky.

Output format:
In the only line print a single number — the number c that is sought by Petya.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
1 7

Example output:
7

Example input:
100 47

Example output:
147

Editorial:
Palindromic Numbers
Contest: Codeforces Round 802 (Div. 2)
Difficulty rating: 1100
Tags: constructive algorithms, implementation, math

During a daily walk Alina noticed a long number written on the ground. Now Alina wants to find some positive number of same length without leading zeroes, such that the sum of these two numbers is a palindrome.

Recall that a number is called a palindrome, if it reads the same right to left and left to right. For example, numbers $$$121, 66, 98989$$$ are palindromes, and $$$103, 239, 1241$$$ are not palindromes.

Alina understands that a valid number always exist. Help her find one!

Input format:
The first line of input data contains an integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. Next, descriptions of $$$t$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 100\,000$$$) — the length of the number that is written on the ground.

The second line of contains the positive $$$n$$$-digit integer without leading zeroes — the number itself.

It is guaranteed that the sum of the values $$$n$$$ over all test cases does not exceed $$$100\,000$$$.

Output format:
For each of $$$t$$$ test cases print an answer — a positive $$$n$$$-digit integer without leading zeros, such that the sum of the input integer and this number is a palindrome.

We can show that at least one number satisfying the constraints exists. If there are multiple solutions, you can output any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case $$$99 + 32 = 131$$$ is a palindrome. Note that another answer is $$$12$$$, because $$$99 + 12 = 111$$$ is also a palindrome.

In the second test case $$$1023 + 8646 = 9669$$$.

In the third test case $$$385 + 604 = 989$$$.

Example input:
3
2
99
4
1023
3
385

Example output:
32
8646
604

Editorial:
Let X be the number in input. Consider two cases: first digit of X is 9 and not 9.
If the first digit of input number is not 9, we can simply output 9999...999 ($$$n$$$ digits) - X.
If the first digit is 9, we can output 111...1111 ($$$n + 1$$$ digits) - X. It is easy to show that this number will be exactly $$$n$$$-digit.
To simplify implementation, we can first find 9999...999 - X by subtracting all digits of X from 9, and than if this number is not $$$n$$$-digit, add 111...1111 - 9999...999 = 11111...1112 to it.
Overall complexity will be $$$\mathcal{O}(n)$$$.
Helping the Nature
Contest: Codeforces Round 802 (Div. 2)
Difficulty rating: 1700
Tags: constructive algorithms, data structures, greedy

Little Leon lives in the forest. He has recently noticed that some trees near his favourite path are withering, while the other ones are overhydrated so he decided to learn how to control the level of the soil moisture to save the trees.

There are $$$n$$$ trees growing near the path, the current levels of moisture of each tree are denoted by the array $$$a_1, a_2, \dots, a_n$$$. Leon has learned three abilities which will help him to dry and water the soil.

- Choose a position $$$i$$$ and decrease the level of moisture of the trees $$$1, 2, \dots, i$$$ by $$$1$$$.
- Choose a position $$$i$$$ and decrease the level of moisture of the trees $$$i, i + 1, \dots, n$$$ by $$$1$$$.
- Increase the level of moisture of all trees by $$$1$$$.

Leon wants to know the minimum number of actions he needs to perform to make the moisture of each tree equal to $$$0$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$)  — the number of test cases. The description of $$$t$$$ test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 200\,000$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) — the initial levels of trees moisture.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$200\,000$$$.

Output format:
For each test case output a single integer — the minimum number of actions. It can be shown that the answer exists.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case it's enough to apply the operation of adding $$$1$$$ to the whole array $$$2$$$ times.

In the second test case you can apply the operation of decreasing $$$4$$$ times on the prefix of length $$$3$$$ and get an array $$$6, 0, 3$$$.

After that apply the operation of decreasing $$$6$$$ times on the prefix of length $$$1$$$ and $$$3$$$ times on the suffix of length $$$1$$$. In total, the number of actions will be $$$4 + 6 + 3 = 13$$$. It can be shown that it's impossible to perform less actions to get the required array, so the answer is $$$13$$$.

Example input:
4
3
-2 -2 -2
3
10 4 7
4
4 -4 4 -4
5
1 -2 3 -4 5

Example output:
2
13
36
33

Editorial:
Consider the difference array $$$d_i = a_{i + 1} - a_{i}$$$. Note that for $$$d_i > 0$$$ it is necessary to make $$$d_i$$$ subtractions on the suffix. For $$$d_i < 0$$$, you need to make $$$-d_i$$$ subtractions on the prefix. Let's add them to the answer. Let's calculate the final array using prefix and suffix sums for $$$O(n)$$$. Note that it will consist of the same numbers. Add $$$|x|$$$ to the answer, where $$$x$$$ is the resulting number.
Windblume Ode
Contest: Technocup 2022 - Elimination Round 1
Difficulty rating: 800
Tags: math, number theory

A bow adorned with nameless flowers that bears the earnest hopes of an equally nameless person.

You have obtained the elegant bow known as the Windblume Ode. Inscribed in the weapon is an array of $$$n$$$ ($$$n \ge 3$$$) positive distinct integers (i.e. different, no duplicates are allowed).

Find the largest subset (i.e. having the maximum number of elements) of this array such that its sum is a composite number. A positive integer $$$x$$$ is called composite if there exists a positive integer $$$y$$$ such that $$$1 < y < x$$$ and $$$x$$$ is divisible by $$$y$$$.

If there are multiple subsets with this largest size with the composite sum, you can output any of them. It can be proven that under the constraints of the problem such a non-empty subset always exists.

Input format:
Each test consists of multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.

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

The second line of each test case contains $$$n$$$ distinct integers $$$a_{1},a_{2},\dots,a_{n}$$$ ($$$1 \leq a_{i} \leq 200$$$) — the elements of the array.

Output format:
Each test case should have two lines of output.

The first line should contain a single integer $$$x$$$: the size of the largest subset with composite sum. The next line should contain $$$x$$$ space separated integers representing the indices of the subset of the initial array.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, the subset $$$\{a_2, a_1\}$$$ has a sum of $$$9$$$, which is a composite number. The only subset of size $$$3$$$ has a prime sum equal to $$$11$$$. Note that you could also have selected the subset $$$\{a_1, a_3\}$$$ with sum $$$8 + 2 = 10$$$, which is composite as it's divisible by $$$2$$$.

In the second test case, the sum of all elements equals to $$$21$$$, which is a composite number. Here we simply take the whole array as our subset.

Example input:
4
3
8 1 2
4
6 9 4 2
9
1 2 3 4 5 6 7 8 9
3
200 199 198

Example output:
2
2 1
4
2 1 4 3
9
6 9 1 2 3 4 5 7 8
3
1 2 3

Editorial:
Let $$$s$$$ be equal to the sum of array $$$a$$$. If $$$s$$$ is composite then $$$a$$$ is the largest composite subset of itself. Otherwise, since $$$n \geq 3$$$, $$$s$$$ must be a prime number greater than $$$2$$$, meaning $$$s$$$ must be odd. Now notice that because all elements of $$$a$$$ are distinct, if we remove any one number from $$$a$$$, the remaining sum must be strictly greater than $$$2$$$. This leads us to the following solution: if $$$s$$$ is prime, removing any odd number from $$$a$$$ will give a composite subset of size $$$n-1$$$. This is because that since $$$s$$$ is assumed to be odd, an odd number must exist in $$$a$$$, and the difference of two odd numbers is always even. Since we claim that this difference is at least $$$4$$$, the new sum will always be composite.
Omkar and Heavenly Tree
Contest: Technocup 2022 - Elimination Round 1
Difficulty rating: 1200
Tags: constructive algorithms, trees

Lord Omkar would like to have a tree with $$$n$$$ nodes ($$$3 \le n \le 10^5$$$) and has asked his disciples to construct the tree. However, Lord Omkar has created $$$m$$$ ($$$\mathbf{1 \le m < n}$$$) restrictions to ensure that the tree will be as heavenly as possible.

A tree with $$$n$$$ nodes is an connected undirected graph with $$$n$$$ nodes and $$$n-1$$$ edges. Note that for any two nodes, there is exactly one simple path between them, where a simple path is a path between two nodes that does not contain any node more than once.

Here is an example of a tree:

A restriction consists of $$$3$$$ pairwise distinct integers, $$$a$$$, $$$b$$$, and $$$c$$$ ($$$1 \le a,b,c \le n$$$). It signifies that node $$$b$$$ cannot lie on the simple path between node $$$a$$$ and node $$$c$$$.

Can you help Lord Omkar and become his most trusted disciple? You will need to find heavenly trees for multiple sets of restrictions. It can be shown that a heavenly tree will always exist for any set of restrictions under the given constraints.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^4$$$). Description of the test cases follows.

The first line of each test case contains two integers, $$$n$$$ and $$$m$$$ ($$$3 \leq n \leq 10^5$$$, $$$\mathbf{1 \leq m < n}$$$), representing the size of the tree and the number of restrictions.

The $$$i$$$-th of the next $$$m$$$ lines contains three integers $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ ($$$1 \le a_i, b_i, c_i \le n$$$, $$$a$$$, $$$b$$$, $$$c$$$ are distinct), signifying that node $$$b_i$$$ cannot lie on the simple path between nodes $$$a_i$$$ and $$$c_i$$$.

It is guaranteed that the sum of $$$n$$$ across all test cases will not exceed $$$10^5$$$.

Output format:
For each test case, output $$$n-1$$$ lines representing the $$$n-1$$$ edges in the tree. On each line, output two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) signifying that there is an edge between nodes $$$u$$$ and $$$v$$$. Given edges have to form a tree that satisfies Omkar's restrictions.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The output of the first sample case corresponds to the following tree:

The output of the second sample case corresponds to the following tree:

Example input:
2
7 4
1 2 3
3 4 5
5 6 7
6 5 4
5 3
1 2 3
2 3 4
3 4 5

Example output:
1 2
1 3
3 5
3 4
2 7
7 6
5 1
1 3
3 2
2 4

Editorial:
Because the number of restrictions is less than $$$n$$$, there is guaranteed to be at least one value from $$$1$$$ to $$$n$$$ that is not a value of $$$b$$$ for any of the restrictions. Find a value that is not $$$b$$$ for all of the restrictions and construct a tree that is a "star" with that value in the middle. An easy way to do this is to make an edge from that value to every other number from $$$1$$$ to $$$n$$$.
Zmei Gorynich
Contest: Educational Codeforces Round 72 (Rated for Div. 2)
Difficulty rating: 1600
Tags: greedy, math

You are fighting with Zmei Gorynich — a ferocious monster from Slavic myths, a huge dragon-like reptile with multiple heads!

Initially Zmei Gorynich has $$$x$$$ heads. You can deal $$$n$$$ types of blows. If you deal a blow of the $$$i$$$-th type, you decrease the number of Gorynich's heads by $$$min(d_i, curX)$$$, there $$$curX$$$ is the current number of heads. But if after this blow Zmei Gorynich has at least one head, he grows $$$h_i$$$ new heads. If $$$curX = 0$$$ then Gorynich is defeated.

You can deal each blow any number of times, in any order.

For example, if $$$curX = 10$$$, $$$d = 7$$$, $$$h = 10$$$ then the number of heads changes to $$$13$$$ (you cut $$$7$$$ heads off, but then Zmei grows $$$10$$$ new ones), but if $$$curX = 10$$$, $$$d = 11$$$, $$$h = 100$$$ then number of heads changes to $$$0$$$ and Zmei Gorynich is considered defeated.

Calculate the minimum number of blows to defeat Zmei Gorynich!

You have to answer $$$t$$$ independent queries.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) – the number of queries.

The first line of each query contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 100$$$, $$$1 \le x \le 10^9$$$) — the number of possible types of blows and the number of heads Zmei initially has, respectively.

The following $$$n$$$ lines of each query contain the descriptions of types of blows you can deal. The $$$i$$$-th line contains two integers $$$d_i$$$ and $$$h_i$$$ ($$$1 \le d_i, h_i \le 10^9$$$) — the description of the $$$i$$$-th blow.

Output format:
For each query print the minimum number of blows you have to deal to defeat Zmei Gorynich.

If Zmei Gorynuch cannot be defeated print $$$-1$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first query you can deal the first blow (after that the number of heads changes to $$$10 - 6 + 3 = 7$$$), and then deal the second blow.

In the second query you just deal the first blow three times, and Zmei is defeated.

In third query you can not defeat Zmei Gorynich. Maybe it's better to convince it to stop fighting?

Example input:
3
3 10
6 3
8 2
1 4
4 10
4 1
3 2
2 6
1 100
2 15
10 11
14 100

Example output:
2
3
-1

Editorial:
Lets divide all dealing blows into two parts: the last blow and others blows.
The last hit should be with maximum value of $$$d$$$.
The others blows should be with the maximum value of $$$d - h$$$.
So, lets denote $$$\max\limits_{1 \le i \le n} d_i$$$ as $$$maxD$$$ and $$$\max\limits_{1 \le i \le n} (d_i - h_i)$$$ as $$$maxDH$$$.
Then if $$$x \le maxD$$$ the we can beat Zmei Gorynich with one blow. Otherwise, if $$$maxDH \le 0$$$, then we cannot defeat Zmei Gorynich.
Otherwise (if $$$x > maxD$$$ and $$$maxDH > 0$$$) the answer is $$$\lceil \frac{x - maxD}{maxDH} \rceil$$$.
The Number Of Good Substrings
Contest: Educational Codeforces Round 72 (Rated for Div. 2)
Difficulty rating: 1700
Tags: binary search, bitmasks, brute force

You are given a binary string $$$s$$$ (recall that a string is binary if each character is either $$$0$$$ or $$$1$$$).

Let $$$f(t)$$$ be the decimal representation of integer $$$t$$$ written in binary form (possibly with leading zeroes). For example $$$f(011) = 3, f(00101) = 5, f(00001) = 1, f(10) = 2, f(000) = 0$$$ and $$$f(000100) = 4$$$.

The substring $$$s_{l}, s_{l+1}, \dots , s_{r}$$$ is good if $$$r - l + 1 = f(s_l \dots s_r)$$$.

For example string $$$s = 1011$$$ has $$$5$$$ good substrings: $$$s_1 \dots s_1 = 1$$$, $$$s_3 \dots s_3 = 1$$$, $$$s_4 \dots s_4 = 1$$$, $$$s_1 \dots s_2 = 10$$$ and $$$s_2 \dots s_4 = 011$$$.

Your task is to calculate the number of good substrings of string $$$s$$$.

You have to answer $$$t$$$ independent queries.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of queries.

The only line of each query contains string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), consisting of only digits $$$0$$$ and $$$1$$$.

It is guaranteed that $$$\sum\limits_{i=1}^{t} |s_i| \le 2 \cdot 10^5$$$.

Output format:
For each query print one integer — the number of good substrings of string $$$s$$$.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Example input:
4
0110
0101
00001000
0001000

Example output:
4
3
4
3

Editorial:
At first, lets precalc the array $$$nxt_1, nxt_2, \dots , nxt_n$$$. The value of $$$nxt_i$$$ if equal the maximum position $$$j$$$ in range $$$1 \dots i$$$ such that $$$s_j = 1$$$.
After that lets iterate over the right boundary of substring and high $$$1$$$-bit position (denote it as $$$r$$$ and $$$l$$$ respectively).
Note that if $$$r - l > 18$$$ then $$$f(l, r) > 2 \cdot 10^5$$$.
So we iterate over such pair $$$(l, r)$$$ that $$$1 \le l \le r \le n$$$ and $$$r - l \le 18$$$.
Lets look at value $$$f(l, r)$$$. If $$$f(l, r) > r - l + 1$$$, then we have to increase the length of substring without increasing the value of $$$f(l, r)$$$. So we need to check if there exists a position $$$nl$$$ such that $$$f(nl, r) = f(l, r)$$$ and $$$r - nl + 1 = f(nl, r)$$$. This position exists if the condition $$$f(l, r) \le r - nxt_{l - 1}$$$ is met ($$$nxt_0$$$ is equal to -1).
Coloring Edges
Contest: Educational Codeforces Round 72 (Rated for Div. 2)
Difficulty rating: 2100
Tags: constructive algorithms, dfs and similar, graphs

You are given a directed graph with $$$n$$$ vertices and $$$m$$$ directed edges without self-loops or multiple edges.

Let's denote the $$$k$$$-coloring of a digraph as following: you color each edge in one of $$$k$$$ colors. The $$$k$$$-coloring is good if and only if there no cycle formed by edges of same color.

Find a good $$$k$$$-coloring of given digraph with minimum possible $$$k$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 5000$$$, $$$1 \le m \le 5000$$$) — the number of vertices and edges in the digraph, respectively.

Next $$$m$$$ lines contain description of edges — one per line. Each edge is a pair of integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — there is directed edge from $$$u$$$ to $$$v$$$ in the graph.

It is guaranteed that each ordered pair $$$(u, v)$$$ appears in the list of edges at most once.

Output format:
In the first line print single integer $$$k$$$ — the number of used colors in a good $$$k$$$-coloring of given graph.

In the second line print $$$m$$$ integers $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_i \le k$$$), where $$$c_i$$$ is a color of the $$$i$$$-th edge (in order as they are given in the input).

If there are multiple answers print any of them (you still have to minimize $$$k$$$).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
4 5
1 2
1 3
3 4
2 4
1 4

Example output:
1
1 1 1 1 1

Example input:
3 3
1 2
2 3
3 1

Example output:
2
1 1 2

Editorial:
Let's run dfs on the graph and color all "back edges" ($$$(u, v)$$$ is back edge if there is a path from $$$v$$$ to $$$u$$$ by edges from dfs tree) in black and all other edges in white.
It can be proven that any cycle will have at least one white edge and at least black edge. Moreover each back edge connected with at least one cycle (path from $$$v$$$ to $$$u$$$ and $$$(u, v)$$$ back edge). So the coloring we got is exactly the answer.
How to prove that any cycle have at least one edge of both colors? Let's look only at edges from dfs trees. We can always renumerate vertices in such way that index of parent $$$id(p)$$$ is bigger than the index of any its child $$$id(c)$$$. We can process and assign $$$id(p)$$$ with minimal free number after we processed all its children.
Now we can note that for any white edge $$$(u, v)$$$ (not only tree edge) condition $$$id(u) > id(v)$$$ holds (because of properties of dfs: forward edges are obvious; cross edge $$$(u, v)$$$ becomes cross because dfs at first processed vertex $$$v$$$ and $$$u$$$ after that, so $$$id(v) < id(u)$$$). And for each back edge $$$(u, v)$$$ it's true that $$$id(u) < id(v)$$$.
Since any cycle have both $$$id(u) > id(v)$$$ and $$$id(u) < id(v)$$$ situations, profit!
Tavas and Nafas
Contest: Codeforces Round 299 (Div. 2)
Difficulty rating: 1000
Tags: brute force, implementation

Today Tavas got his test result as an integer score and he wants to share it with his girlfriend, Nafas.

His phone operating system is Tavdroid, and its keyboard doesn't have any digits! He wants to share his score with Nafas via text, so he has no choice but to send this number using words.

He ate coffee mix without water again, so right now he's really messed up and can't think.

Your task is to help him by telling him what to type.

Input format:
The first and only line of input contains an integer s (0 ≤ s ≤ 99), Tavas's score.

Output format:
In the first and only line of output, print a single string consisting only from English lowercase letters and hyphens ('-'). Do not use spaces.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
You can find all you need to know about English numerals in http://en.wikipedia.org/wiki/English_numerals .

Example input:
6

Example output:
six

Example input:
99

Example output:
ninety-nine

Editorial:
Tavas and SaDDas
Contest: Codeforces Round 299 (Div. 2)
Difficulty rating: 1100
Tags: bitmasks, brute force, combinatorics, implementation

Once again Tavas started eating coffee mix without water! Keione told him that it smells awful, but he didn't stop doing that. That's why Keione told his smart friend, SaDDas to punish him! SaDDas took Tavas' headphones and told him: "If you solve the following problem, I'll return it to you."

The problem is:

You are given a lucky number n. Lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

If we sort all lucky numbers in increasing order, what's the 1-based index of n?

Tavas is not as smart as SaDDas, so he asked you to do him a favor and solve this problem so he can have his headphones back.

Input format:
The first and only line of input contains a lucky number n (1 ≤ n ≤ 109).

Output format:
Print the index of n among all lucky numbers.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
4

Example output:
1

Example input:
7

Example output:
2

Editorial: