1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Selection of Personnel
Contest: Experimental Educational Round: VolBIT Formulas Blitz
Difficulty rating: 1300
Tags: combinatorics, math

One company of IT City decided to create a group of innovative developments consisting from 5 to 7 people and hire new employees for it. After placing an advertisment the company received n resumes. Now the HR department has to evaluate each possible group composition and select one of them. Your task is to count the number of variants of group composition to evaluate.

Input format:
The only line of the input contains one integer n (7 ≤ n ≤ 777) — the number of potential employees that sent resumes.

Output format:
Output one integer — the number of different variants of group composition.

Constraints:
Time limit: 0.5 s
Memory limit: 64.0 MB

Example input:
7

Example output:
29

Editorial:
The amount of ways to choose a group of 5 people from n candidates is equal to the number of combinations $${ \binom { n } { 5 } }$$, the amount of ways to choose a group of 6 people from n candidates is $${ \binom { n } { 6 } }$$, the amount of ways to choose a group of 7 people from n candidates is $${ \binom { n } { 7 } }$$, the amount of ways to choose a group of 5, 6 or 7 people from n candidates is $${ \binom { n } { 5 } } + { \binom { n } { 6 } } + { \binom { n } { 7 } } = { \frac { n! } { ( n - 5 )! 5! } } + { \frac { n! } { ( n - 6 )! 6! } } + { \frac { n! } { ( n - 7 )! 7! } }$$.
To avoid 64-bit integer overflow $$\frac{n!}{(n-7)!7!}$$ can be calculated in the following way: n / 1 * (n - 1) / 2 * (n - 2) / 3 * (n - 3) / 4 * (n - 4) / 5 * (n - 5) / 6 * (n - 6) / 7. Each division returns an integer because each prefix of this formula after division is also the number of combinations $${\binom {n}{i}}$$.
Challenge Pennants
Contest: Experimental Educational Round: VolBIT Formulas Blitz
Difficulty rating: 1600
Tags: combinatorics, math

Because of budget cuts one IT company established new non-financial reward system instead of bonuses.

Two kinds of actions are rewarded: fixing critical bugs and suggesting new interesting features. A man who fixed a critical bug gets "I fixed a critical bug" pennant on his table. A man who suggested a new interesting feature gets "I suggested a new feature" pennant on his table.

Because of the limited budget of the new reward system only 5 "I fixed a critical bug" pennants and 3 "I suggested a new feature" pennants were bought.

In order to use these pennants for a long time they were made challenge ones. When a man fixes a new critical bug one of the earlier awarded "I fixed a critical bug" pennants is passed on to his table. When a man suggests a new interesting feature one of the earlier awarded "I suggested a new feature" pennants is passed on to his table.

One man can have several pennants of one type and of course he can have pennants of both types on his table. There are n tables in the IT company. Find the number of ways to place the pennants on these tables given that each pennant is situated on one of the tables and each table is big enough to contain any number of pennants.

Input format:
The only line of the input contains one integer n (1 ≤ n ≤ 500) — the number of tables in the IT company.

Output format:
Output one integer — the amount of ways to place the pennants on n tables.

Constraints:
Time limit: 0.5 s
Memory limit: 64.0 MB

Example input:
2

Example output:
24

Editorial:
First of all, ways to place both types of the pennants are independent. So each way to place "I fixed a critical bug" pennants on n tables is compatible to each way to place "I suggested a new feature" pennants on n tables. Therefore the answer of the problem is equal to the number of ways to place "I fixed a critical bug" pennants multiplied by the number of ways to place "I suggested a new feature" pennant.
The number of ways to place k identical items into n different places when any place can contain any amount of items is the definition of the number of k-combinations with repetitions or k-multicombinations. The formula for the number is $${ \frac { ( n + k - 1 )! } { ( n - 1 )! k! } }$$.
So the whole formula for the problem is $${ \frac { ( n + 4 )! } { ( n - 1 )! 5! } } \cdot { \frac { ( n + 2 )! } { ( n - 1 )! 3! } }$$.
To avoid overflow of 64-bit integer type recommended formulas for computation are (n + 2) / 1 * (n + 1) / 2 * n / 3 and (n + 4) / 1 * (n + 3) / 2 * (n + 2) / 3 * (n + 1) / 4 * n / 5.
Benches
Contest: Experimental Educational Round: VolBIT Formulas Blitz
Difficulty rating: 1400
Tags: combinatorics, math

The city park of IT City contains n east to west paths and n north to south paths. Each east to west path crosses each north to south path, so there are n2 intersections.

The city funded purchase of five benches. To make it seems that there are many benches it was decided to place them on as many paths as possible. Obviously this requirement is satisfied by the following scheme: each bench is placed on a cross of paths and each path contains not more than one bench.

Help the park administration count the number of ways to place the benches.

Input format:
The only line of the input contains one integer n (5 ≤ n ≤ 100) — the number of east to west paths and north to south paths.

Output format:
Output one integer — the number of ways to place the benches.

Constraints:
Time limit: 0.5 s
Memory limit: 64.0 MB

Example input:
5

Example output:
120

Editorial:
The number of ways to choose 5 east to west paths that will have benches from n is $${ \binom { n } { 5 } } = { \frac { n! } { ( n - 5 )! 5! } } = { \frac { n ( n - 1 ) ( n - 2 ) ( n - 3 ) ( n - 4 ) } { 5! } }$$. There are n ways to place a bench on the first of these paths. Given the place of the first bench there are n - 1 ways to place a bench on the second of these paths because one of north to south paths is already taken. Given the places of the first and second benches there are n - 2 ways to place a bench on the third of these paths because two of north to south paths are already taken. And the same way n - 3 and n - 4 for the fourth and the fifth benches. Total number of ways to place benches on selected 5 east to west path is n(n - 1)(n - 2)(n - 3)(n - 4). So the formula for the problem is $$\frac{n(n-1)(n-2)(n-3)(n-4)}{5!} \cdot n(n-1)(n-2)(n-3)(n-4)$$.
To avoid 64-bit integer overflow recommended order of computation is exactly as in the formula above, division should not be the last operation.
Parking Lot
Contest: Experimental Educational Round: VolBIT Formulas Blitz
Difficulty rating: 1700
Tags: combinatorics, math

To quickly hire highly skilled specialists one of the new IT City companies made an unprecedented move. Every employee was granted a car, and an employee can choose one of four different car makes.

The parking lot before the office consists of one line of (2n - 2) parking spaces. Unfortunately the total number of cars is greater than the parking lot capacity. Furthermore even amount of cars of each make is greater than the amount of parking spaces! That's why there are no free spaces on the parking lot ever.

Looking on the straight line of cars the company CEO thought that parking lot would be more beautiful if it contained exactly n successive cars of the same make. Help the CEO determine the number of ways to fill the parking lot this way.

Input format:
The only line of the input contains one integer n (3 ≤ n ≤ 30) — the amount of successive cars of the same make.

Output format:
Output one integer — the number of ways to fill the parking lot by cars of four makes using the described way.

Constraints:
Time limit: 0.5 s
Memory limit: 64.0 MB

Note:
Let's denote car makes in the following way: A — Aston Martin, B —   Bentley, M — Mercedes-Maybach, Z — Zaporozhets. For n = 3 there are the following appropriate ways to fill the parking lot: AAAB AAAM AAAZ ABBB AMMM AZZZ BBBA BBBM BBBZ BAAA BMMM BZZZ MMMA MMMB MMMZ MAAA MBBB MZZZ ZZZA ZZZB ZZZM ZAAA ZBBB ZMMM

Originally it was planned to grant sport cars of Ferrari, Lamborghini, Maserati and Bugatti makes but this idea was renounced because it is impossible to drive these cars having small road clearance on the worn-down roads of IT City.

Example input:
3

Example output:
24

Editorial:
There are the following ways to place n cars of the same make. They can be the first n, the last n, or they can be somewhere in the middle of the parking lot.
When n cars of the same make are the first or the last, there are 4 ways to choose the make of these n cars, then there are 3 ways to choose the make of one car adjacent to them (the make should be different from the make of n cars) and there are 4 ways to choose the make of each of the remaining n - 3 cars. So the formula for the case of n cars of the same make on either end of the parking lot is 4·3·4n - 3.
When n cars of the same make are situated somewhere in the middle, there are 4 ways to choose the make of these n cars, then there are 3 ways to choose the make of each of two cars adjacent to them (the makes of these two cars should be different from the make of n cars) and there are 4 ways to choose the make of each of the remaining n - 4 cars. So the formula for the case of n cars of the same make on a given position somewhere in the middle of the parking lot is 4·32·4n - 4.
There are 2 positions of n cars of the same make in the end of the parking lot and there are n - 3 positions of n cars of the same make somewhere in the middle of the parking lot. So the final formula is 2·4·3·4n - 3 + (n - 3)·4·32·4n - 4.
Divisibility
Contest: Experimental Educational Round: VolBIT Formulas Blitz
Difficulty rating: 1100
Tags: math, number theory

IT City company developing computer games invented a new way to reward its employees. After a new game release users start buying it actively, and the company tracks the number of sales with precision to each transaction. Every time when the next number of sales is divisible by all numbers from 2 to 10 every developer of this game gets a small bonus.

A game designer Petya knows that the company is just about to release a new game that was partly developed by him. On the basis of his experience he predicts that n people will buy the game during the first month. Now Petya wants to determine how many times he will get the bonus. Help him to know it.

Input format:
The only line of the input contains one integer n (1 ≤ n ≤ 1018) — the prediction on the number of people who will buy the game.

Output format:
Output one integer showing how many numbers from 1 to n are divisible by all numbers from 2 to 10.

Constraints:
Time limit: 0.5 s
Memory limit: 64.0 MB

Example input:
3000

Example output:
1

Editorial:
Let's factorize numbers from 2 to 10. 2 = 2, 3 = 3, 4 = 22, 5 = 5, 6 = 2·3, 7 = 7, 8 = 23, 9 = 32, 10 = 2·5. If a number is divisible by all numbers from 2 to 10, its factorization should contain 2 at least in the power of 3, 3 at least in the power of 2, 5 and 7 at least in the power of 1. So it can be written as x·23·32·5·7 = x·2520. So any number divisible by 2520 is divisible by all numbers from 2 to 10.
There are $$\lfloor n/2520 \rfloor$$ numbers from 1 to n divisible by all numbers from 2 to 10. In a programming language it is usually implemented as simple integer division.
Cracking the Code
Contest: Experimental Educational Round: VolBIT Formulas Blitz
Difficulty rating: 1400
Tags: implementation, math

The protection of a popular program developed by one of IT City companies is organized the following way. After installation it outputs a random five digit number which should be sent in SMS to a particular phone number. In response an SMS activation code arrives.

A young hacker Vasya disassembled the program and found the algorithm that transforms the shown number into the activation code. Note: it is clear that Vasya is a law-abiding hacker, and made it for a noble purpose — to show the developer the imperfection of their protection.

The found algorithm looks the following way. At first the digits of the number are shuffled in the following order <first digit><third digit><fifth digit><fourth digit><second digit>. For example the shuffle of 12345 should lead to 13542. On the second stage the number is raised to the fifth power. The result of the shuffle and exponentiation of the number 12345 is 455 422 043 125 550 171 232. The answer is the 5 last digits of this result. For the number 12345 the answer should be 71232.

Vasya is going to write a keygen program implementing this algorithm. Can you do the same?

Input format:
The only line of the input contains a positive integer five digit number for which the activation code should be found.

Output format:
Output exactly 5 digits without spaces between them — the found activation code of the program.

Constraints:
Time limit: 0.5 s
Memory limit: 64.0 MB

Example input:
12345

Example output:
71232

Editorial:
In this problem just implementation of the actions described in the statement is required. However there are two catches in this problem.
The first catch is that the fifth power of five-digit number cannot be represented by a 64-bit integer. But we need not the fifth power, we need the fifth power modulo 105. And mod operation can be applied after each multiplication (see problem A above).
The second catch is that you need to output five digits, not the fifth power modulo 105. The difference is when fifth digit from the end is zero. To output a number with the leading zero one can either use corresponding formatting (%05d in printf) or extract digits and output them one by one.
Forecast
Contest: Experimental Educational Round: VolBIT Formulas Blitz
Difficulty rating: 1300
Tags: math

The Department of economic development of IT City created a model of city development till year 2100.

To prepare report about growth perspectives it is required to get growth estimates from the model.

To get the growth estimates it is required to solve a quadratic equation. Since the Department of economic development of IT City creates realistic models only, that quadratic equation has a solution, moreover there are exactly two different real roots.

The greater of these roots corresponds to the optimistic scenario, the smaller one corresponds to the pessimistic one. Help to get these estimates, first the optimistic, then the pessimistic one.

Input format:
The only line of the input contains three integers a, b, c ( - 1000 ≤ a, b, c ≤ 1000) — the coefficients of ax2 + bx + c = 0 equation.

Output format:
In the first line output the greater of the equation roots, in the second line output the smaller one. Absolute or relative error should not be greater than 10 - 6.

Constraints:
Time limit: 0.5 s
Memory limit: 64.0 MB

Example input:
1 30 200

Example output:
-10.000000000000000
-20.000000000000000

Editorial:
There is nothing special in solving a quadratic equation but the problem has one catch. You should output the greater root first.
The simplest approach is to output max(x1, x2) first, then min(x1, x2).
Another approach is based upon the sign of a.
$$\frac{-b-\sqrt{b^2-4ac}}{2a} < \frac{-b+\sqrt{b^2-4ac}}{2a}$$ for a > 0 and $$\frac{-b-\sqrt{b^2-4ac}}{2a} > \frac{-b+\sqrt{b^2-4ac}}{2a}$$ for a < 0.
We can divide all coefficients by a, and then the first coefficient will be positive. But notice that division should be done in a floating point type and a should be divided last otherwise resulting a / a = 1 would not be able to divide b and c.
Area of a Star
Contest: Experimental Educational Round: VolBIT Formulas Blitz
Difficulty rating: 2100
Tags: geometry

It was decided in IT City to distinguish successes of local IT companies by awards in the form of stars covered with gold from one side. To order the stars it is necessary to estimate order cost that depends on the area of gold-plating. Write a program that can calculate the area of a star.

A "star" figure having n ≥ 5 corners where n is a prime number is constructed the following way. On the circle of radius r n points are selected so that the distances between the adjacent ones are equal. Then every point is connected by a segment with two maximally distant points. All areas bounded by the segments parts are the figure parts.

Input format:
The only line of the input contains two integers n (5 ≤ n < 109, n is prime) and r (1 ≤ r ≤ 109) — the number of the star corners and the radius of the circumcircle correspondingly.

Output format:
Output one number — the star area. The relative error of your answer should not be greater than 10 - 7.

Constraints:
Time limit: 0.5 s
Memory limit: 64.0 MB

Example input:
7 10

Example output:
108.395919545675

Editorial:
$$\angle COE = \frac{2\pi}{n}$$ where n in the number of the star corners because in a regular star all angles between corners are equal.
$$\angle BOA = \angle COD = \angle EOD = \frac{\angle COE}{2} = \frac{\pi}{n}$$ because of symmetry.
$$\angle CAE = \frac{\angle COE}{2} = \frac{\pi}{n}$$ because it is an inscribed angle.
$$\angle CAO = \angle EAO = \frac{\angle CAE}{2} = \frac{\pi}{2n}$$ because of symmetry.
So we know OA = r and $$\angle BAO = \angle CAO = \frac{\pi}{2n}$$ and $$\angle BOA = \frac{\pi}{n}$$. We can calculate the area of AOB triangle knowing the length of a side and two angles adjacent to it using formula $$\frac{OA^{2}}{2(\frac{1}{\tan \angle BAO}+\frac{1}{\tan \angle BOA})}=\frac{r^{2}}{2(\frac{1}{\tan \frac{\pi}{2n}}+\frac{1}{\tan \frac{\pi}{n}})}$$.
The whole star area is equal to 2n areas of AOB triangle because of symmetry. $$2 n \frac { r ^ { 2 } } { 2 ( \frac { 1 } { \tan \frac { \pi } { 2 n } } + \frac { 1 } { \tan \frac { \pi } { n } } ) } = \frac { n \cdot r ^ { 2 } } { ( \frac { 1 } { \tan \frac { \pi } { 2 n } } + \frac { 1 } { \tan \frac { \pi } { n } } ) }$$.
Game
Contest: Experimental Educational Round: VolBIT Formulas Blitz
Difficulty rating: 1200
Tags: games, math

There is a legend in the IT City college. A student that failed to answer all questions on the game theory exam is given one more chance by his professor. The student has to play a game with the professor.

The game is played on a square field consisting of n × n cells. Initially all cells are empty. On each turn a player chooses and paint an empty cell that has no common sides with previously painted cells. Adjacent corner of painted cells is allowed. On the next turn another player does the same, then the first one and so on. The player with no cells to paint on his turn loses.

The professor have chosen the field size n and allowed the student to choose to be the first or the second player in the game. What should the student choose to win the game? Both players play optimally.

Input format:
The only line of the input contains one integer n (1 ≤ n ≤ 1018) — the size of the field.

Output format:
Output number 1, if the player making the first turn wins when both players play optimally, otherwise print number 2.

Constraints:
Time limit: 0.5 s
Memory limit: 64.0 MB

Example input:
1

Example output:
1

Example input:
2

Example output:
2

Editorial:
For the field of an even size there is a winning strategy for the second player. Namely, to paint a cell that is symmetrical with respect to the center of the field to the cell painted by the first player on the previous turn. After each turn of the second player the field is centrosymmetrical and so there is always a cell that can be painted that is symmetrical with respect to the center of the field to any cell that the first player can choose to paint.
For the field of an odd size there is a winning strategy for the first player. Namely, on the first turn to paint the central cell, then to paint a cell that is symmetrical with respect to the center of the field to the cell painted by the second player on the previous turn. After each turn of the first player the field is centrosymmetrical and so there is always a cell that can be painted that is symmetrical with respect to the center of the field to any cell that the second player can choose to paint.
So for even n the answer is 2, for odd n the answer is 1. One of the possible formulas for the problem is $$2 - ( n \mod 2 )$$.
n can be up to 1018 so at least 64-bit integer type should be used to input it.
Compress String
Contest: Technocup 2019 - Final
Difficulty rating: 2100
Tags: strings

Suppose you are given a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters. You need to compress it using the smallest possible number of coins.

To compress the string, you have to represent $$$s$$$ as a concatenation of several non-empty strings: $$$s = t_{1} t_{2} \ldots t_{k}$$$. The $$$i$$$-th of these strings should be encoded with one of the two ways:

- if $$$|t_{i}| = 1$$$, meaning that the current string consists of a single character, you can encode it paying $$$a$$$ coins;
- if $$$t_{i}$$$ is a substring of $$$t_{1} t_{2} \ldots t_{i - 1}$$$, then you can encode it paying $$$b$$$ coins.

A string $$$x$$$ is a substring of a string $$$y$$$ if $$$x$$$ can be obtained from $$$y$$$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

So your task is to calculate the minimum possible number of coins you need to spend in order to compress the given string $$$s$$$.

Input format:
The first line contains three positive integers, separated by spaces: $$$n$$$, $$$a$$$ and $$$b$$$ ($$$1 \leq n, a, b \leq 5000$$$) — the length of the string, the cost to compress a one-character string and the cost to compress a string that appeared before.

The second line contains a single string $$$s$$$, consisting of $$$n$$$ lowercase English letters.

Output format:
Output a single integer — the smallest possible number of coins you need to spend to compress $$$s$$$.

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

Note:
In the first sample case, you can set $$$t_{1} =$$$ 'a', $$$t_{2} =$$$ 'b', $$$t_{3} =$$$ 'a' and pay $$$3 + 3 + 1 = 7$$$ coins, since $$$t_{3}$$$ is a substring of $$$t_{1}t_{2}$$$.

In the second sample, you just need to compress every character by itself.

In the third sample, you set $$$t_{1} = t_{2} =$$$ 'a', $$$t_{3} =$$$ 'aa' and pay $$$10 + 1 + 1 = 12$$$ coins, since $$$t_{2}$$$ is a substring of $$$t_{1}$$$ and $$$t_{3}$$$ is a substring of $$$t_{1} t_{2}$$$.

Example input:
3 3 1
aba

Example output:
7

Example input:
4 1 1
abcd

Example output:
4

Editorial:
Let's say that $$$dp[p]$$$ is the minimal cost to encode the prefix of $$$s$$$ with length $$$p$$$, the answer is $$$dp[n]$$$. If we want to encode the prefix with length $$$p$$$ then the last symbol in our encoded string either equals $$$s_p$$$, or represents some substring $$$s_{[l,p]}$$$ so that it occurs in the prefix of length $$$l - 1$$$. Therefore one can see that
$$$$$$dp[0] = 0,$$$$$$ $$$$$$dp[p] = \min\left(a + dp[p - 1], \min\left(b + dp[l - 1]\,\mid\,s_{[l, p]}\text{ is a substring of }s_{[1, l - 1]}\right)\right).$$$$$$
One way to implement this is to calculate this $$$dp$$$ forward and use hashes, but it may require some efforts to avoid collisions and fit into the time limit. Another way is to find for each $$$p$$$ all appropriate $$$l$$$'s by calculating z-function on the reverse of $$$s_{[1, p]}$$$. The total complexity in this case is $$$O\left(n^2\right)$$$.