1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Lucky Probability
Contest: Codeforces Beta Round 84 (Div. 1 Only)
Difficulty rating: 1900
Tags: brute force, probabilities

Petya loves lucky numbers. We all know that 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.

Petya and his friend Vasya play an interesting game. Petya randomly chooses an integer p from the interval [pl, pr] and Vasya chooses an integer v from the interval [vl, vr] (also randomly). Both players choose their integers equiprobably. Find the probability that the interval [min(v, p), max(v, p)] contains exactly k lucky numbers.

Input format:
The single line contains five integers pl, pr, vl, vr and k (1 ≤ pl ≤ pr ≤ 109, 1 ≤ vl ≤ vr ≤ 109, 1 ≤ k ≤ 1000).

Output format:
On the single line print the result with an absolute error of no more than 10 - 9.

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

Note:
Consider that [a, b] denotes an interval of integers; this interval includes the boundaries. That is, $$\left[a,b\right] \stackrel{\mathrm{def}}{=}\{x\in\mathbb{R}:a\leqslant x\leqslant b\}$$

In first case there are 32 suitable pairs: (1, 7), (1, 8), (1, 9), (1, 10), (2, 7), (2, 8), (2, 9), (2, 10), (3, 7), (3, 8), (3, 9), (3, 10), (4, 7), (4, 8), (4, 9), (4, 10), (7, 1), (7, 2), (7, 3), (7, 4), (8, 1), (8, 2), (8, 3), (8, 4), (9, 1), (9, 2), (9, 3), (9, 4), (10, 1), (10, 2), (10, 3), (10, 4). Total number of possible pairs is 10·10 = 100, so answer is 32 / 100.

In second case Petya always get number less than Vasya and the only lucky 7 is between this numbers, so there will be always 1 lucky number.

Example input:
1 10 1 10 2

Example output:
0.320000000000

Example input:
5 6 8 10 1

Example output:
1.000000000000

Editorial:
Lucky Tree
Contest: Codeforces Beta Round 84 (Div. 1 Only)
Difficulty rating: 1900
Tags: dp, dsu, trees

Petya loves lucky numbers. We all know that 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.

One day Petya encountered a tree with n vertexes. Besides, the tree was weighted, i. e. each edge of the tree has weight (a positive integer). An edge is lucky if its weight is a lucky number. Note that a tree with n vertexes is an undirected connected graph that has exactly n - 1 edges.

Petya wondered how many vertex triples (i, j, k) exists that on the way from i to j, as well as on the way from i to k there must be at least one lucky edge (all three vertexes are pairwise distinct). The order of numbers in the triple matters, that is, the triple (1, 2, 3) is not equal to the triple (2, 1, 3) and is not equal to the triple (1, 3, 2).

Find how many such triples of vertexes exist.

Input format:
The first line contains the single integer n (1 ≤ n ≤ 105) — the number of tree vertexes. Next n - 1 lines contain three integers each: ui vi wi (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 109) — the pair of vertexes connected by the edge and the edge's weight.

Output format:
On the single line print the single number — the answer.

Please do not use the %lld specificator to read or write 64-bit numbers in С++. It is recommended to use the cin, cout streams or the %I64d specificator.

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

Note:
The 16 triples of vertexes from the first sample are: (1, 2, 4), (1, 4, 2), (2, 1, 3), (2, 1, 4), (2, 3, 1), (2, 3, 4), (2, 4, 1), (2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 1, 2), (4, 1, 3), (4, 2, 1), (4, 2, 3), (4, 3, 1), (4, 3, 2).

In the second sample all the triples should be counted: 4·3·2 = 24.

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

Example output:
16

Example input:
4
1 2 4
1 3 47
1 4 7447

Example output:
24

Editorial:
Lucky Sorting
Contest: Codeforces Beta Round 84 (Div. 1 Only)
Difficulty rating: 2000
Tags: constructive algorithms, sortings

Petya loves lucky numbers. We all know that 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.

Petya got an array consisting of n numbers, it is the gift for his birthday. Now he wants to sort it in the non-decreasing order. However, a usual sorting is boring to perform, that's why Petya invented the following limitation: one can swap any two numbers but only if at least one of them is lucky. Your task is to sort the array according to the specified limitation. Find any possible sequence of the swaps (the number of operations in the sequence should not exceed 2n).

Input format:
The first line contains an integer n (1 ≤ n ≤ 105) — the number of elements in the array. The second line contains n positive integers, not exceeding 109 — the array that needs to be sorted in the non-decreasing order.

Output format:
On the first line print number k (0 ≤ k ≤ 2n) — the number of the swaps in the sorting. On the following k lines print one pair of distinct numbers (a pair per line) — the indexes of elements to swap. The numbers in the array are numbered starting from 1. If it is impossible to sort the given sequence, print the single number -1.

If there are several solutions, output any. Note that you don't have to minimize k. Any sorting with no more than 2n swaps is accepted.

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

Example input:
2
4 7

Example output:
0

Example input:
3
4 2 1

Example output:
1
1 3

Editorial:
Lucky Interval
Contest: Codeforces Beta Round 84 (Div. 1 Only)
Difficulty rating: 2700
Tags: brute force, math

Petya loves lucky numbers. We all know that 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.

One day Petya came across an interval of numbers [a, a + l - 1]. Let F(x) be the number of lucky digits of number x. Find the minimum b (a < b) such, that F(a) = F(b), F(a + 1) = F(b + 1), ..., F(a + l - 1) = F(b + l - 1).

Input format:
The single line contains two integers a and l (1 ≤ a, l ≤ 109) — the interval's first number and the interval's length correspondingly.

Output format:
On the single line print number b — the answer to the problem.

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

Note:
Consider that [a, b] denotes an interval of integers; this interval includes the boundaries. That is, $$\left[a,b\right] \stackrel{\mathrm{def}}{=}\{x\in\mathbb{R}:a\leqslant x\leqslant b\}$$

Example input:
7 4

Example output:
17

Example input:
4 7

Example output:
14

Editorial:
Vasya and Coins
Contest: Codeforces Round 780 (Div. 3)
Difficulty rating: 800
Tags: greedy, math

Vasya decided to go to the grocery store. He found in his wallet $$$a$$$ coins of $$$1$$$ burle and $$$b$$$ coins of $$$2$$$ burles. He does not yet know the total cost of all goods, so help him find out $$$s$$$ ($$$s > 0$$$): the minimum positive integer amount of money he cannot pay without change or pay at all using only his coins.

For example, if $$$a=1$$$ and $$$b=1$$$ (he has one $$$1$$$-burle coin and one $$$2$$$-burle coin), then:

- he can pay $$$1$$$ burle without change, paying with one $$$1$$$-burle coin,
- he can pay $$$2$$$ burle without change, paying with one $$$2$$$-burle coin,
- he can pay $$$3$$$ burle without change by paying with one $$$1$$$-burle coin and one $$$2$$$-burle coin,
- he cannot pay $$$4$$$ burle without change (moreover, he cannot pay this amount at all).

So for $$$a=1$$$ and $$$b=1$$$ the answer is $$$s=4$$$.

Input format:
The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases in the test.

The description of each test case consists of one line containing two integers $$$a_i$$$ and $$$b_i$$$ ($$$0 \le a_i, b_i \le 10^8$$$) — the number of $$$1$$$-burle coins and $$$2$$$-burles coins Vasya has respectively.

Output format:
For each test case, on a separate line print one integer $$$s$$$ ($$$s > 0$$$): the minimum positive integer amount of money that Vasya cannot pay without change or pay at all.

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

Note:
- The first test case of the example is clarified into the main part of the statement.
- In the second test case, Vasya has only $$$1$$$ burle coins, and he can collect either any amount from $$$1$$$ to $$$4$$$, but $$$5$$$ can't.
- In the second test case, Vasya has only $$$2$$$ burle coins, and he cannot pay $$$1$$$ burle without change.
- In the fourth test case you don't have any coins, and he can't even pay $$$1$$$ burle.

Example input:
5
1 1
4 0
0 2
0 0
2314 2374

Example output:
4
5
1
1
7063

Editorial:
If Vasya has $$$b$$$ coins of $$$2$$$ burles, then he can collect amounts of $$$2, 4, \dots, 2 * b$$$ burls. If Vasya does not have $$$1$$$ burles coins, then he cannot collect the amount of $$$1$$$ burle. If he has at least one coin in $$$1$$$ burl, he can score odd amounts up to $$$2*b + a$$$. The following $$$1$$$burl coins increase the maximum amount he can make. If Vasya has $$$a$$$ coins for $$$1$$$ burle, he can make up the amount of $$$2 * b + a$$$ burles, and $$$2 * b + a + 1$$$ - not anymore.
Get an Even String
Contest: Codeforces Round 780 (Div. 3)
Difficulty rating: 1300
Tags: dp, greedy, strings

A string $$$a=a_1a_2\dots a_n$$$ is called even if it consists of a concatenation (joining) of strings of length $$$2$$$ consisting of the same characters. In other words, a string $$$a$$$ is even if two conditions are satisfied at the same time:

- its length $$$n$$$ is even;
- for all odd $$$i$$$ ($$$1 \le i \le n - 1$$$), $$$a_i = a_{i+1}$$$ is satisfied.

For example, the following strings are even: "" (empty string), "tt", "aabb", "oooo", and "ttrrrroouuuuuuuukk". The following strings are not even: "aaa", "abab" and "abba".

Given a string $$$s$$$ consisting of lowercase Latin letters. Find the minimum number of characters to remove from the string $$$s$$$ to make it even. The deleted characters do not have to be consecutive.

Input format:
The first line of input data contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) —the number of test cases in the test.

The descriptions of the test cases follow.

Each test case consists of one string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), where $$$|s|$$$ — the length of the string $$$s$$$. The string consists of lowercase Latin letters.

It is guaranteed that the sum of $$$|s|$$$ on all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, print a single number — the minimum number of characters that must be removed to make $$$s$$$ even.

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

Note:
In the first test case you can remove the characters with indices $$$6$$$, $$$7$$$, and $$$9$$$ to get an even string "aabbddcc".

In the second test case, each character occurs exactly once, so in order to get an even string, you must remove all characters from the string.

In the third test case, you can get an even string "aaaabb" by removing, for example, $$$4$$$-th and $$$6$$$-th characters, or a string "aabbbb" by removing the $$$5$$$-th character and any of the first three.

Example input:
6
aabbdabdccc
zyx
aaababbb
aabbcc
oaoaaaoo
bmefbmuyw

Example output:
3
3
2
0
2
7

Editorial:
We will act greedily: we will make an array $$$prev$$$ consisting of $$$26$$$ elements, in which we will mark $$$prev[i] = true$$$ if the letter is already encountered in the string, and $$$prev[i] = false$$$ otherwise. In the variable $$$m$$$ we will store the length of the even string that can be obtained from $$$s$$$. We will go through the string by executing the following algorithm:
• if $$$prev[i] = false$$$, mark $$$prev[i] = true$$$.
• if $$$prev[i] = true$$$, then we already have a pair of repeating characters to add to an even string — add $$$2$$$ to the number $$$m$$$ and clear the array $$$used$$$.
Clearing $$$prev$$$ is necessary because both characters that will make up the next pair must be in the $$$s$$$ string after the current character. In other words, if the last character in the current pair was $$$s_t$$$, then the first character in the new pair can be $$$s_k$$$, where $$$ t \lt k \lt n$$$.
Then we calculate the answer as $$$n - m$$$.
Help Farmer
Contest: Codeforces Round 102 (Div. 1)
Difficulty rating: 1600
Tags: brute force, math

Once upon a time in the Kingdom of Far Far Away lived Sam the Farmer. Sam had a cow named Dawn and he was deeply attached to her. Sam would spend the whole summer stocking hay to feed Dawn in winter. Sam scythed hay and put it into haystack. As Sam was a bright farmer, he tried to make the process of storing hay simpler and more convenient to use. He collected the hay into cubical hay blocks of the same size. Then he stored the blocks in his barn. After a summer spent in hard toil Sam stored A·B·C hay blocks and stored them in a barn as a rectangular parallelepiped A layers high. Each layer had B rows and each row had C blocks.

At the end of the autumn Sam came into the barn to admire one more time the hay he'd been stacking during this hard summer. Unfortunately, Sam was horrified to see that the hay blocks had been carelessly scattered around the barn. The place was a complete mess. As it turned out, thieves had sneaked into the barn. They completely dissembled and took away a layer of blocks from the parallelepiped's front, back, top and sides. As a result, the barn only had a parallelepiped containing (A - 1) × (B - 2) × (C - 2) hay blocks. To hide the evidence of the crime, the thieves had dissembled the parallelepiped into single 1 × 1 × 1 blocks and scattered them around the barn. After the theft Sam counted n hay blocks in the barn but he forgot numbers A, B и C.

Given number n, find the minimally possible and maximally possible number of stolen hay blocks.

Input format:
The only line contains integer n from the problem's statement (1 ≤ n ≤ 109).

Output format:
Print space-separated minimum and maximum number of hay blocks that could have been stolen by the thieves.

Note that the answer to the problem can be large enough, so you must use the 64-bit integer type for calculations. Please, do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

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

Note:
Let's consider the first sample test. If initially Sam has a parallelepiped consisting of 32 = 2 × 4 × 4 hay blocks in his barn, then after the theft the barn has 4 = (2 - 1) × (4 - 2) × (4 - 2) hay blocks left. Thus, the thieves could have stolen 32 - 4 = 28 hay blocks. If Sam initially had a parallelepiped consisting of 45 = 5 × 3 × 3 hay blocks in his barn, then after the theft the barn has 4 = (5 - 1) × (3 - 2) × (3 - 2) hay blocks left. Thus, the thieves could have stolen 45 - 4 = 41 hay blocks. No other variants of the blocks' initial arrangement (that leave Sam with exactly 4 blocks after the theft) can permit the thieves to steal less than 28 or more than 41 blocks.

Example input:
4

Example output:
28 41

Example input:
7

Example output:
47 65

Editorial:
Help General
Contest: Codeforces Round 102 (Div. 1)
Difficulty rating: 1800
Tags: constructive algorithms, greedy, implementation

Once upon a time in the Kingdom of Far Far Away lived Sir Lancelot, the chief Royal General. He was very proud of his men and he liked to invite the King to come and watch drill exercises which demonstrated the fighting techniques and tactics of the squad he was in charge of. But time went by and one day Sir Lancelot had a major argument with the Fairy Godmother (there were rumors that the argument occurred after the general spoke badly of the Godmother's flying techniques. That seemed to hurt the Fairy Godmother very deeply).

As the result of the argument, the Godmother put a rather strange curse upon the general. It sounded all complicated and quite harmless: "If the squared distance between some two soldiers equals to 5, then those soldiers will conflict with each other!"

The drill exercises are held on a rectangular n × m field, split into nm square 1 × 1 segments for each soldier. Thus, the square of the distance between the soldiers that stand on squares (x1, y1) and (x2, y2) equals exactly (x1 - x2)2 + (y1 - y2)2. Now not all nm squad soldiers can participate in the drill exercises as it was before the Fairy Godmother's curse. Unless, of course, the general wants the soldiers to fight with each other or even worse... For example, if he puts a soldier in the square (2, 2), then he cannot put soldiers in the squares (1, 4), (3, 4), (4, 1) and (4, 3) — each of them will conflict with the soldier in the square (2, 2).

Your task is to help the general. You are given the size of the drill exercise field. You are asked to calculate the maximum number of soldiers that can be simultaneously positioned on this field, so that no two soldiers fall under the Fairy Godmother's curse.

Input format:
The single line contains space-separated integers n and m (1 ≤ n, m ≤ 1000) that represent the size of the drill exercise field.

Output format:
Print the desired maximum number of warriors.

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

Note:
In the first sample test Sir Lancelot can place his 4 soldiers on the 2 × 4 court as follows (the soldiers' locations are marked with gray circles on the scheme):

In the second sample test he can place 6 soldiers on the 3 × 4 site in the following manner:

Example input:
2 4

Example output:
4

Example input:
3 4

Example output:
6

Editorial:
Help Caretaker
Contest: Codeforces Round 102 (Div. 1)
Difficulty rating: 2300
Tags: brute force, dp

Autumn came late to the kingdom of Far Far Away. The harvest was exuberant and it is now time to get ready for the winter. As most people celebrate the Harvest festival, Simon the Caretaker tries to solve a very non-trivial task of how to find place for the agricultural equipment in the warehouse.

He's got problems with some particularly large piece of equipment, which is, of course, turboplows. The problem is that when a turboplow is stored, it takes up not some simply rectangular space. It takes up a T-shaped space like on one of the four pictures below (here character "#" stands for the space occupied by the turboplow and character "." stands for the free space):

###      ..#      .#.      #...#.      ###      .#.      ###.#.      ..#      ###      #..

Simon faced a quite natural challenge: placing in the given n × m cells warehouse the maximum number of turboplows. As one stores the turboplows, he can rotate them in any manner (so that they take up the space like on one of the four pictures above). However, two turboplows cannot "overlap", that is, they cannot share the same cell in the warehouse.

Simon feels that he alone cannot find the optimal way of positioning the plugs in the warehouse that would maximize their quantity. Can you help him?

Input format:
The only line contains two space-separated integers n and m — the sizes of the warehouse (1 ≤ n, m ≤ 9).

Output format:
In the first line print the maximum number of turboplows that can be positioned in the warehouse. In each of the next n lines print m characters. Use "." (dot) to mark empty space and use successive capital Latin letters ("A" for the first turboplow, "B" for the second one and so on until you reach the number of turboplows in your scheme) to mark place for the corresponding turboplows considering that they are positioned in the optimal manner in the warehouse. The order in which you number places for the turboplows does not matter. If there are several optimal solutions for a warehouse of the given size, print any of them.

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

Example input:
3 3

Example output:
1
AAA
.A.
.A.

Example input:
5 6

Example output:
4
A..C..
AAAC..
ABCCCD
.B.DDD
BBB..D

Editorial:
Help Greg the Dwarf 2
Contest: Codeforces Round 102 (Div. 1)
Difficulty rating: 3000
Tags: geometry

Greg the Dwarf has been really busy recently with excavations by the Neverland Mountain. However for the well-known reasons (as you probably remember he is a very unusual dwarf and he cannot stand sunlight) Greg can only excavate at night. And in the morning he should be in his crypt before the first sun ray strikes. That's why he wants to find the shortest route from the excavation point to his crypt. Greg has recollected how the Codeforces participants successfully solved the problem of transporting his coffin to a crypt. So, in some miraculous way Greg appeared in your bedroom and asks you to help him in a highly persuasive manner. As usual, you didn't feel like turning him down.

After some thought, you formalized the task as follows: as the Neverland mountain has a regular shape and ends with a rather sharp peak, it can be represented as a cone whose base radius equals r and whose height equals h. The graveyard where Greg is busy excavating and his crypt can be represented by two points on the cone's surface. All you've got to do is find the distance between points on the cone's surface.

The task is complicated by the fact that the mountain's base on the ground level and even everything below the mountain has been dug through by gnome (one may wonder whether they've been looking for the same stuff as Greg...). So, one can consider the shortest way to pass not only along the side surface, but also along the cone's base (and in a specific case both points can lie on the cone's base — see the first sample test)

Greg will be satisfied with the problem solution represented as the length of the shortest path between two points — he can find his way pretty well on his own. He gave you two hours to solve the problem and the time is ticking!

Input format:
The first input line contains space-separated integers r and h (1 ≤ r, h ≤ 1000) — the base radius and the cone height correspondingly. The second and third lines contain coordinates of two points on the cone surface, groups of three space-separated real numbers. The coordinates of the points are given in the systems of coordinates where the origin of coordinates is located in the centre of the cone's base and its rotation axis matches the OZ axis. In this coordinate system the vertex of the cone is located at the point (0, 0, h), the base of the cone is a circle whose center is at the point (0, 0, 0), lying on the XOY plane, and all points on the cone surface have a non-negative coordinate z. It is guaranteed that the distances from the points to the cone surface do not exceed 10 - 12. All real numbers in the input have no more than 16 digits after decimal point.

Output format:
Print the length of the shortest path between the points given in the input, with absolute or relative error not exceeding 10 - 6.

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

Example input:
2 2
1.0 0.0 0.0
-1.0 0.0 0.0

Example output:
2.000000000

Example input:
2 2
1.0 0.0 0.0
1.0 0.0 1.0

Example output:
2.414213562

Editorial: