Formula derivation

ID 31788. spinners again

ID 26980. Paper for the Olympics

ID 26979. logical conclusions

ID 21900. circle line

In the city where friends Andrei and Boris live, the subway consists of a single ring line along which n stations numbered from 1 to n are located at equal distances from each other. The section of the metro line between two neighboring stations is called a span.

Trains on the Circle Line move both clockwise and counterclockwise, so in order to get from one station to another, a passenger can choose the direction in which they need to travel fewer hauls. The minimum number of hauls that you need to travel to get from one station to another, we call the distance between stations.

Friends noticed that the following condition is fulfilled: if you think of some station X and write out two numbers for it: Da — distance from the station where Andrey lives to station X and Db — distance from the station where Boris lives to station X, then the resulting pair of numbers [Da, Db] will uniquely define station X.

For example, if n = 4, Andrey lives at station 1, and Boris lives at station 2, then station 1 is given by the pair [0, 1], station 2 — pair [1, 0], station 3 — pair [2, 1] and station 4 — pair [1, 2].

Their classmate Sergei lives in a nearby town and does not know which stations Andrei and Boris live at. To find friends, he became interested in how many options for pairs of stations A, B exist, such that if Andrey lives at station A, and Boris — at station B, then the above condition is met.

It is required to write a program that, by the number of stations n on the ring line, determines the required number of options.

Input file format
The first line of the input file contains a single integer n (3 ≤ n ≤ 40 000).
Output file format
The output file must contain a single number — desired number of options.

Examples of input and output files

ID 21886. hall selection

For the opening ceremony of the Olympiad in Informatics, the organizers are looking for a suitable hall. The hall should have the shape of a rectangle, the length of each side of which is a positive integer.
In order for all participants of the ceremony to fit in the hall, and at the same time it does not look too empty, the area of ​​\u200b\u200bthe hall should be between A and B square meters, inclusive.
In order to place posters on the walls of the hall telling about the successes of schoolchildren at the Olympiads, but at the same time not to create the feeling that there are too few successes, the perimeter of the hall should be between C and D meters, inclusive.
Before making the final choice, the organizers of the Olympiad decided to look at one hall of each suitable size. Halls with dimensions Y × Z and Z.times. Y are considered the same. In order to understand the amount of work required to view the halls, the organizers asked how many different halls satisfy the above restrictions. It is required to write a program that, given A, B, C and D, determines the number of different halls, the area of ​​\u200b\u200bwhich is in the range from A to B, and the perimeter — from C to D, inclusive.

Input file format
The input file contains four space-separated integers: A, B, C, and D (1<=A<=B<=10⁹ , 4<=C<=D<=10⁹ ).
Output file format
The output file must contain a single number — desired number of halls.

Input:
2 10 4 8
Output:
3

Explanations for the example
In the example, the halls of the following sizes satisfy the constraints: 1 x times; 2.1 x 3.2 x 2

ID 32971. Comet Barmaley

ID 32977. Elections in USA

ID 33144. Two dimensions

ID 31789. Not about spinners

The program should output a single number – the number of rectangles that can be cut from a given sheet of paper (the entire sheet is also considered one of the possible rectangles).
 

Input	Output	Note
2 2	9
3 1	6

 

ID 27061. Formula - 3

Write a program that calculates the y value.

ID 27060. Formula - 4

Write a program that calculates the value of y.

Examples

ID 27059. Formula - 5

Write a program that calculates the value of y.

Examples

ID 27058. Formula - 6

Write a program that calculates the value of y.

Examples

ID 33593. Laces

A shoe factory is about to start producing an elite model of boots. The holes for lacing will be arranged in two rows, the distance between the rows is  a, and the distance between the holes in the row b. The number of holes in each row is N. Lacing should take place in an elite way “up, horizontally to another row, up, horizontally, etc.” (see picture). In addition, in order for the laces to be tied with an elite bow, the length of the free end of the lace must be l. What is the lace length for these boots?
Forbidden to use if, while, for, repeat-until statements (Pascal)

Input: The program takes as input four natural numbers a, b, l and N.

ID 33525. Street

On one side of the street there are houses with odd numbers (1, 3, 5, …), on the other side – with even (2, 4, 6, …). House number 1 is located opposite house number 2, & nbsp; house number 3 – opposite house number 4, etc. You need to walk one minute along the street to the neighboring house, no matter which side of the street it is on (that is, from house number 1 you need to walk one minute both to house number 3 and to house number 4). There is no need to go to the house opposite.



Gromozeka went outside from house number A and must reach house number B. Determine how many minutes he needs to walk along the street.

It is forbidden to use any algorithmic constructs to solve this problem. You can only use arithmetic operations (without using built-in functions).

Input data
The program receives as input two distinct positive integers A and B not exceeding 2×10⁹, – house numbers.

Imprint
The program should output a single number – desired number of minutes.

Examples

ID 23575. Perimeter of a triangle

Two integers are entered from the keyboard - the legs of a right-angled triangle. Write a program to determine the perimeter of such a triangle.
 

Example

ID 23574. Triangle hypotenuse

Two integers are entered from the keyboard - the legs of a right-angled triangle. Write a program to determine the hypotenuse of such a triangle.
 

Example

ID 33649. The perimeter of a rectangle and the length of the diagonal

Two integers are entered from the keyboard - the sides of the rectangle. Write a program to find its perimeter and the length of the diagonal. Print the perimeter of the rectangle in the first line, and the length of its diagonal in the second line.
 

Example

ID 31924. Elevator

ID 33580. *Baker king

King wants to become a baker and lead a simple lifestyle.
The royal kitchen is covered with a kitchen apron, which is divided into squares with side A see. King wants to hang a picture of his family on the apron. He knows the point at which the lower left corner of the painting is in contact, as well as the width and height of the painting itself. And then he wanted to know the number of squares that would be partially or completely covered by the picture.

Input format
The first line contains the number A - the side of one square of the kitchen apron.
The second and third lines - the numbers X and Y - are the coordinates of the lower left corner of the picture.
The fourth and fifth lines - the numbers W and H - the width and height of the picture.
The axis OX is directed to the right, the axis OY is directed up.
The lower left corner of one of the squares of the kitchen apron is at the origin. All numbers are integers not exceeding 2 × 10⁹, numbers A, W, H are positive, numbers X and Y are positive or equal to 0.

Output format 
Output one number - the number of tiles completely or partially covered by the picture.
A square is considered a closed picture if the intersection of the picture and the square has a non-zero area, that is, touching the picture and the square is not considered overlapping.
 

Example

Description

Side of the square (side of the cell in the figure) A = 10.
The lower left corner of the picture has coordinates (15, 5), the picture has a width of 35 cm and a height of 20 cm.
The painting completely or partially covers 12 squares

ID 33692. Полоски радуги

В школе  № 2007 на уроке информатики в системе SilverTests Васе попалась следующая задача: «В  младшей группе одного объединённого детского сада воспитательница  изучала с детишками  порядок цветов радуги. Она отыскала семь соответствующих цветных мелков и начала рисовать полоски, не нарушая последовательности цветов.  Начала она с красной полоски. Когда доходила до фиолетовой полоски, опять рисовала  красную. Воспитательница  успела нарисовать N полосок, когда у неё закончились  мелки. Напишите программу, которая вычисляет количество полосок каждого цвета».  Вася взялся писать программу, но тут обнаружилось, что на клавиатуре отсутствует клавиша с буквой  «i». Помогите Васе написать программу с учётом этого обстоятельства.

Входные данные: Вводится одно целое положительное число N > 0.
Выходные данные: Выведите ответ на задачу.

Если в коде программы встречается буква «i» система выдаст сообщение:  Использование запрещенных операторов
 
Примеры

ID 37015. Arrow match

The program receives two integers n, m, each in a separate line \(0<n<=12, 0< =m<60\) , indicating a point in time "n hours m minutes". Determine the smallest number of full minutes that must elapse before the hour and minute hands on the dial coincide, not necessarily at some division. Do not use real arithmetic.

The task must be solved without using conditional operators (including without the ternary operator ?: in C++) and/or loops. In addition, you cannot use comparison operations and the logical (boolean) data type.

Examples

ID 38468. Even odd

Masha loves even numbers, and Misha – odd. Therefore, they are always happy if they meet numbers they like.
Today they met all integers from A to B inclusive. Masha decided to calculate the sum of all even numbers from A to B, and Misha – the sum of all the odd ones, after which they began to argue who got the sum more. Help them – find the difference
between Masha's sum and Misha's sum.
The program receives as input two positive integers A and B, not exceeding 2×10⁹.
The program should output a single number – the difference between the sum of even numbers and the sum of odd numbers from A to B.

Examples

ID 38478. Purchase

The pen cost K rubles. On September 1, the cost of a pen increased by exactly P percent. Determine how many pens you can buy for S rubles after the rise in price.
The program receives three positive integers as input. The first number is K – the cost of the pen in rubles before the rise in price. Second number P – pen price increase
in percentages. Third number S – available amount of money. The numbers K and S do not exceed 10⁷ , the number P does not exceed 100.
 

Examples

ID 38504. Between A and B

You are given non-negative integers a and b (a<=b) and a positive integer x. How many integers from a to b inclusive are divisible by x?

Input
One line contains three numbers a, b and x (\(0<=a<=b<=10^{18}\), \(1<=x<=10^{18}\)).

Imprint
Display the answer to the problem.
 

Examples

ID 38555. Turtle

The turtle crawls on the floor, which is laid with square tiles with side A see. The start of the Turtle's path is at  X. The turtle managed to crawl a distance of D cm before the owner picked it up. Determine how many cells (partially or whole) the Turtle managed to crawl through.

Input
The first line contains the number A – side length of one tile. The second line contains the number X - the coordinate of the point from which the Turtle started its journey. The third line - the number D - the distance that the Turtle crawled. The OX axis is directed to the right. The last tile in the row on which the Turtle is crawling is at the origin. All numbers are integers not exceeding \(2\cdot10^9 \), numbers A, D – positive, number X – positive or equal to 0.

Imprint
Output one number – the number of tiles that the Turtle has fully or partially crawled through.
It is considered that the Turtle has crawled through the tile if the conditionally drawn line of the Turtle's path has a non-zero length, that is, the touch of the path line and the edge of the tile is not considered.

Examples

#	Input	Output	Explanation
1	10 15 35	4	Tile side (cell side in the picture) A = 10. The turtle started at X = 15 and passed 35. The turtle has completely or partially passed 4 tiles.

ID 38578. Time left

Gromozeka loves programming competitions. Today he will take part in the competition in STCoder. This site uses a 24-hour clock. For example, 21:00. referred to as «21 o'clock».
The current time is A hours and the competition will start exactly in B hours. Determine the start time of the competition? Give your answer in 24-hour format.

Input
The input string contains two integers A and B (\(0<=A,B<=23\)) separated by one space.

Imprint
Print the contest start hour in 24-hour format.
 

Examples

ID 38629. minimization

There is a sequence of length N: A1, A2, ..., AN. Initially, this sequence is a permutation of 1, 2, ..., N. In this sequence, Alice can perform the following operation:
1) select K consecutive elements in sequence;
2) then replace the value of each selected element with the minimum value among the selected elements.
Alice wants to equalize all the elements in this sequence by repeating the above operation a number of times.
Find the minimum number of necessary operations.
It can be proved that, under the constraints of this problem, this goal is always achievable.

Input
The first line specifies two integers N and K (2<=K<=N<=100000). The second line specifies a sequence of integers A1, A2, ..., AN - permutation of numbers from 1 to N (each number in the sequence is different, 1<=A_i <=N).

Imprint
Print the minimum number of required operations.
 

Examples

ID 38667. Acceleration Dunno

Dunno was trained by Toropyzhka to walk faster. Before training, he walked a path of S meters in t1 seconds. After training Dunno's speed increased by P%. Write a program that determines which path (in meters) Dunno will walk in t2 seconds after training with Toropyzhka.

Input
Four integers as input: S (1<=S<=100), t1(1<=t ₁<=100), P (1<=P<=100)  and t 2 (1<=t₂<=100).

Imprint
Print one number - the answer to the problem.
 

Example

ID 38668. Cars of Vintik and Shpuntik

Vintik and Shpuntin tested new cars. The distance around the Flower City was covered by Vintik's car in t1 seconds, the speedometer showed the speed of V m/s all the way. Shpuntik's car covered the same distance around the Flower City in t2 seconds, while Shpuntik's speedometer was broken. Help Shpuntik determine how fast (in m/s) he was driving.

Input
Input 3 integers:  t1(1<=t₁<=100), V< /code>(1<=V<=100)  and t2 (1<=t2 <=100).

Imprint
Print one number - the answer to the problem.
 

Example

ID 38762. Rock-Paper-Scissors. Without scissors

Dunno and his friend Gunka are playing a game. The game consists of N moves. On each turn, each player plays one of the two gestures, Rock and Paper, as in Rock-Paper-Scissors, under the following conditions:
- After each move
(number of times the player played Paper) <= (number of times the player played Rock).
- The score of each player is calculated by the formula:
(number of turns the player wins) - (number of turns the player loses),
where the result of each move is determined by the rules of "rock-paper-scissors".

For those unfamiliar with the Rock-Paper-Tailing game, if one player plays Rock and the other plays Paper, the last player wins and the first player loses. If both players play with the same gesture, the round is considered a draw and neither player wins or loses.

Using a magic wand Dunno was able to foresee the gesture that Gunka would use in each of the N moves before the start of the game. Plan out Dunno's gestures at every turn to maximize his score.
The gesture that Gunka will play on each move is specified by the s string. If i-th (1 <= i <= N) character in s is equal to g, then Gunka will play "Stone" on ith move. Similarly, if the i-th (1 <= i <= N) character s in p, Gunka will play Paper on < code>i-th move.

Input
The input is one string s  of length N. Each character in the string s is g or p >. The gestures represented by s satisfy the game condition.

Imprint
Print the maximum possible score of Dunno.
 

Examples

ID 39383. white cells

The checkered field consists of white cells. The field size is H rows and W columns. You need to select h rows and w columns and fill in all the cells contained in those rows or columns. How many white cells will remain after painting?

Input
The first line contains 2 numbers: H and W (1 <= H, W <= 20). The second line contains 2 numbers:  h and  w (1 <= h <= H, 1 <= w <= W).

Imprint
Print the answer to the problem.
 

Examples

ID 39505. watch tree

Farmer John's new barn consists of N rooms (2 ≤ N ≤ 2500), consecutively numbered 1 x hellip; N, and N x minus; 1 corridors. Each corridor connects a pair of rooms in such a way that it is possible to go from one room to any through a series of corridors.
Each room in the barn has a round clock on the wall with the standard 1…12 on the front. However, this clock has only one hand, which always points exactly to one of the integers (it never points between two of those numbers).

Cow Besi wants to synchronize all the clocks in the barn so that they all point to the number 12. But with her cow thinking, every time she enters the room, she moves the hand forward one position. For example, if the arrow was pointing at 5, Besie will move the hand to 6. If the clock was pointing to 12, she will move the hand to 1. If Besie enters the room multiple times, she will move the hand each time she enters.

Determine the numbers of rooms in which Besie can start the journey through the barn to set all arrows to 12. Note that Besie does not move the arrow in the starting room at the beginning of the path and moves each time she enters it. The arrows themselves do not move. Besi entering the corridor must reach the end and enter the room at the end of the corridor. She can't turn back inside the hallway to re-enter the room she left.

Input
The first line of input contains N. The next line contains N integers, each in the range 1*12, indicating the initial positions of the arrows in each room. Each of the following N−1 lines describes a corridor with two integers a and b, each in the range 1…N, and the numbers of the rooms connected by this corridor.

Imprint
Print the numbers of the rooms Besi can start in to set all clocks to 12.

Examples

4
11 10 11 11
12
2 3
24

ID 39513. Triangles - 2

Farmer John wants to create a triangular pasture for his cows.
There are N fence posts (3 ≤ N ≤ 10⁵) as different (X₁,Y₁)…(X< sub>N,Y_N) points on the farm map. He can choose three of them to form the vertices of a triangular pasture, but so that one of the sides is parallel to the x-axis and the other is parallel to the y-axis.

What is the sum of the areas of all possible pastures that a FD can form?

Input
The first line contains N.
Each of the following N lines contains two integers Xi and Yi, each in the interval −10⁴…10⁴ inclusive, describing the position of the post.

Imprint
Since the sum of areas may not be an integer and very large, print the remainder after dividing twice the sum of areas by 10⁹+7.

Examples

4
0 0
0 1
10
1 2

ID 39514. One-two-three-four-five cow change

N cows (1 ≤ N ≤ 10⁵) Farmer John stand in a row. The i-th cow on the left has label i (1 ≤ i ≤ N).
FD gave the cows M pairs of integers s (L₁,R₁)…(L_M,R_M), where 1 ≤ M≤ 100. Then he told the cows to repeat exactly K (1 ≤ K ≤ 10⁹) times the process of M steps:

For every i from 1 to M:
The sequence of cows in positions Li…Ri on the left reverses their order.
Print the labels of all cows from left to right for each i, (1 ≤ i ≤ N) after the process is completed.

Input
The first line contains the numbers N, M, K. For each 1 ≤ i≤ M string i+1 contains L_i and R_i, two integers in the interval 1…N, where L_i<R_i.

Imprint
On the i-th line of the output, print the i-th element of the array after executing all instructions K times.

Examples

7 2 2
25
3 7

1
2
4
3
5
7
6

ID 27221. Bovine Genomics #2

ID 39515. three four five cow change

The N  cows (1 ≤ N ≤ 100) of Farmer John are lined up. The i-th cow on the left has label i, for all 1≤i≤N.
The FD ordered the cows to repeat exactly K (1 ≤ K ≤10⁹) times the following two-step process:

The sequence of cows at positions A1…A2 on the left reverses their order (1≤A₁<A₂≤N).
Then the sequence of cows at positions B1…B2 on the left reverses their order (1≤B₁<B₂≤N).
Output the resulting order of cows for all i 1 ≤ i≤ N after running this process exactly K times.


Input
The first line contains N and K. The second line contains A₁ and A₂, the third line contains B₁ and B_{2.
Imprint
On the i-th line print the label of the i-th cow on the left after the process of all exchanges is completed.}

Examples

7 2
25
3 7

1
2
4
3
5
7
6

ID 39517. triangles

Farmer John wants to create a triangular pasture for his cows.
There are N fence posts in total (3 ≤ N ≤ 100) as distinct (X₁,Y₁)…(X_N, Y_N) points on the farm map. He can choose three of them to form the vertices of a triangular pasture, but so that one of the sides is parallel to the x-axis and the other is parallel to the y-axis.

What is the sum of the areas of all possible pastures that a FD can form?

Input
The first line contains N.
Each of the following N lines contains two integers Xi and Yi, each in the interval −10⁴…10⁴ inclusive, describing the position of the post.

Imprint
Since the sum of areas may not be an integer and very large, print the remainder after dividing twice the sum of areas by 10⁹+7.

Examples

4
0 0
0 1
10
1 2

ID 39535. hungry pawn

Gromozeka respects chessboard games. Gromozeka has a hungry pawn on a regular 8x8 board. A hungry pawn eats some opponent’s piece every move (i.e. it can move diagonally forward 1 square to the right or left, it cannot move back). Gromozeka, without looking at the board, learned to determine whether a hungry pawn can move from one square of the board to another. It is impossible to turn into a queen to a hungry pawn.
Write a program with which you could also easily check Gromozeka.

Input
The program receives as input two cells of the chessboard in chess notation. First, the cell where the hungry pawn stands, and then, after a gap, the cell where the hungry pawn must go.

Imprint
Print the word YES (in capital letters) if a hungry pawn can move from the first cell to the second, and NO otherwise.
The board has a size of 8x8, the verticals are numbered in small Latin letters from a to h, the horizontals are numbered from 1 to 8. The starting and ending cells do not match.
 

Examples

ID 39551. Cows in a stall

Farmer John has N cows (1 ≤ N ≤ 20) with heights a₁…a_N. His barn has N stalls with maximum heights b₁…b_N (so for example b₅=17 means no cows with a height more than 17 can be placed in a stall 5). In how many different ways can the FD place the cows into the stalls so that the height constraint is met for each stall.

Input
The first line contains N. The second line contains N numbers a₁, a₂,…,a_N separated by single spaces. The third line contains N numbers b₁,b₂,…,b_N separated by single spaces. All values ​​are integers in the interval [1,10⁹].

Imprint
The number of ways the FD can place cows in the stalls so that the height limit is satisfied for each stall. Note that the answer can be very large, so it requires a 64-bit integer variable such as "long long" in C++.

Examples

4
1 2 3 4
2 4 3 4

ID 39560. More weird photos

Farmer John is photographing N of his cows (2≤N≤1000).
Each cow has an integer - "Breed ID" in the range 1*100. FD split all cows into disjoint groups (in other words, put each cow in exactly one group) and then arrange the groups so that the sum of the "Breed ID" cows in the first group were even, in the second - odd, etc., alternating even and odd.

What is the maximum number of groups that a FD can form?

Input
The first line of input contains the number N. The next line contains N space-separated integers representing the "breed ID".
Imprint
The maximum possible number of groups in the PD photo. It can be proved that there will always be at least one group.

Examples

7
1 3 5 7 9 11 13

7
11 2 17 13 1 15 3

ID 39669. double string hash

You are given t queries, in each of which you are given a string s consisting of lowercase Latin letters, a number p and a number mod.
For each query, compute a polynomial hash modulo base p of the string that is the string s, where each letter is duplicated. That is, if s = "isaac", then you need to calculate the hash from the string "iissaaaacc".

Input:
The first line contains the number t - the number of requests.
Then there are t lines, each containing space-separated s (1 <= |s| <= 20), p (1 <= p <= 10⁵) and mod ( 1 <= mod <= 10⁸).

Output:
Print the responses to the queries, each on a separate line.

Example:
 

ID 41227. powerful array

There is an array of natural numbers a₁, a₂, ..., a_n. Consider some of its subarrays a_l, a_l + 1, ..., a_r, where 1 ≤ l ≤ r ≤ n, and for each natural number s denote by K_s the number of occurrences of the number s in this subarray. Let's call the cardinality of a subarray the sum of the products K_s·K_s·s over all distinct integers s. Since the number of different numbers in the array is finite, the sum contains only a finite number of non-zero terms.

It is necessary to calculate the cardinalities of each of the t given subarrays.

Input
The first line contains two integers n and t (1 ≤ n, t ≤ 200000) — the length of the array and the number of requests, respectively.
The second line contains n natural numbers ai (1 ≤ a_i ≤ 10⁶) — array elements.
The next t lines contain two positive integers l and r (1 ≤ l ≤ r ≤ n) — indexes of the left and right ends of the corresponding subarray.

Imprint
Print t lines, where the i-th line contains the only natural number — cardinality of the i-th query subarray.

Examples:
 

ID 41230. Laboratory tables

At the Department of "Applied Informatics" University N in the new academic year recruited three groups of first-year students. For practical exercises, it is necessary to equip a new audience with laboratory tables. No more than four students can sit at each such table, and all students must be from the same group. The audience has the opportunity to simultaneously accommodate students from three groups at once.
Determine the minimum number of tables to be purchased.

Input
The program receives as input three natural numbers (one number per line): the number of students in each of the three groups.

Imprint
Print the answer to the problem.
 

Examples

ID 41231. Time difference

The values ​​of two points of time belonging to the same day are given: hours, minutes and seconds for each of the points of time. It is known that the second moment of time came not earlier than the first. Determine how many seconds have elapsed between two points in time.

Input
The program receives three integers as input — hours, minutes, seconds representing the first point in time and three integers representing the second point in time.

Imprint
Print the number of seconds between these times.
 
 

Examples

1
1
1
2
2
2

3661

1
2
thirty
1
3
20

50

ID 39242. Cookie machine

The biscuit machine produces B biscuits at the following times: A seconds, 2A seconds, 3A seconds and every subsequent multiple of A seconds after power on. Determine how many cookies the machine will have produced by time T+0.5 seconds after power on.

Input
The program takes as input one string containing three numbers A, B and T.  1 <= A, B, T <= 20, A <= T. All numbers are positive integers.

Imprint
Print one number - the answer to the problem.
 

Examples