| Problem description | | Progress |
|
Темы:
USE - computational tasks
A set of points with integer coordinates is given on the plane. It is necessary to find the maximum possible area of a non-degenerate (that is, having a non-zero area) triangle, one vertex of which is located at the origin of coordinates, and the other two lie on the bisectors of the angles formed by the coordinate axes, and moreover, they belong to the given set. If such a triangle does not exist, an appropriate message should be displayed. Write a time and memory efficient program to solve this problem.
A program is considered efficient in time if the increase in the number of points by k times increases the running time by no more than k times. A program is considered memory efficient if the memory size for storing all the necessary data does not depend on the number of points and does not exceed 1 kilobyte. Before the text of the program, briefly describe the solution algorithm and indicate
programming language and its version.
Input
The first line specifies N – the number of points in the given set. Each of the following lines contains two integers – coordinates of the next point.
Output
If the desired triangle exists, the program should print a single number: the maximum possible area of the triangle that satisfies the conditions. If the required triangle does not exist, the program should print the message: "No solution".
| Input |
Output |
|
3
6 6
-8 8
9 7
|
48 |
| |
![]()
|
|
Темы:
USE - computational tasks
The input of the program is a sequence of N natural numbers, each of which is not greater than 10000. It is required to output the digits occurring in these numbers in non-decreasing order of their frequency of occurrence. If some digits occur the same number of times, they are displayed in descending order.
Input
The input to the program is a natural number N (\(N <= 10000\)), and then N< /code> natural numbers, each of which does not exceed 10000.
Imprint
Output the digits that occur in these numbers, in non-decreasing order of their frequency of occurrence.
Examples
| # |
Input |
Output |
| 1 |
3
456
20
3452
|
6 3 0 5 4 2 |
| |
![]()
|
|
Темы:
USE - computational tasks
Let's call the length of a number the number of digits in its decimal notation. For example, the length of 2017 is 4, and the length of 7 is 1. Given a set of N non-negative integers, each less than 109.
It is necessary to determine the numbers of what length are least likely (but not less than once) in this set and how many numbers of this length are in it. If numbers of different lengths occur equally often (and less frequently than numbers of any other length), choose the shorter length.
Write a time and memory efficient program to solve this problem.
Description of input and output data
The first line of the input specifies the number of numbers N (\(1 <= N <= 10000\)). Each of the following N lines contains one non-negative number not exceeding 109.
Sample input:
5
12
417
125
327
4801
Sample output for the example input above:
2 1
In this set, numbers of length 2 and 4 are least often (once 1 each).
| |
![]()
|
Темы:
USE - computational tasks
A set of points with integer coordinates is given on the plane. It is necessary to find a triangle of the largest area with vertices at these points, one of whose sides lies on the OX axis. Write a memory and time efficient program that will solve this problem. The size of the memory that the program uses should not depend on the length of the passed number sequence.
The first line is a single positive integer – number of points N. Each of the following N lines contains two – first the x coordinate, then the y coordinate of the next point.
The program should output a single number – the maximum area of a triangle that satisfies the conditions of the problem. If no such triangle exists, the program should output zero.
Sample input:
6
0 0
2 0
3 3
5 5
-6 -6
1 2
Example output for the example input above:
6
| |
![]()
|
Темы:
USE - computational tasks
Father Frost and the Snow Maiden come to children's matinees with a bag of sweets. Santa Claus divides the sweets equally among all the children present (there are never more than 100 children at a matinee), and gives the remaining sweets to the Snow Maiden. The Snow Maiden each time writes down the number of sweets received in a notebook. If the sweets are divided among all the children without a trace, the Snow Maiden receives nothing and does not write anything down. When the matinees were over, Santa Claus became interested in what number the Snow Maiden wrote down most often.
Father Frost and Snow Maiden – magicians, so the number of N matinees they have attended can be very large.
Write a program that will solve this problem. Before the text of the program, briefly describe the algorithm for solving the problem, indicate the programming language used and its version. It is desirable that the program be efficient both in terms of running time and in terms of memory used.
A program will be considered memory efficient if the memory used does not depend on the size of the input data (that is, the number of matinees). A program will be considered time efficient if the increase in the size of the input data N by t times (t – any number) does not increase its running time more than t times.
Input
The first line contains a single positive integer – number of matinees N. Each of the following N lines contains two integers: D – the number of children who came to the next matinee; K – the number of sweets in Santa Claus's bag on this matinee.
The following relationships are guaranteed: \(1 <= N <= 10000\), \(1 <= D <= 100\) (for each D), \(D <= K < = 1000\) (for each pair D, K)
Output
The program should output a single number – the one that the Snow Maiden wrote down most often. If several numbers were written equally often, you need to print the larger of them. If the Snow Maiden has never recorded anything, print zero.
Examples
| # |
Input |
Output |
| 1 |
7
10 58
15 315
20408
100 1000
32 63
32 63
11 121
|
31 |
| |
![]()
|
|
Темы:
USE - computational tasks
The input of the program is a sequence of N natural integers, each of which is not greater than 1000. It is required to determine whether it is possible to write all significant digits of the hexadecimal notation of these numbers so that the resulting the line was symmetrical (read the same way both from left to right and from right to left).
If it is impossible to compose the required string, then the program should display the number 0, and if possible, then display the number 1.
Input
The input to the program is a natural number N (\(N <= 100000\)), and then N natural numbers, each of which does not exceed 10000.
Sample input
3
13
22
32
Example output for the given example input:
0
The numbers D, 1, 6, 2, 0 cannot form a symmetrical string.
Sample input:
4
186
68
171
14
Example output for the given example input:
1
The numbers A, B, 4, 4, A, B, D can form a symmetrical string
Write a time and memory efficient program that solves the problem.
| |
![]()
|
Темы:
USE - computational tasks
On Voskhod satellite installed a device designed to measure solar activity. Every minute the device transmits a non-negative integer number – the amount of solar radiation energy received in the last minute, measured in arbitrary units. The time during which the transmission takes place can be neglected.
It is necessary to find in the given series of readings of the device the maximum even product of two readings, between the moments of transmission of which at least 9 minutes have passed. If such a product cannot be obtained, the answer is considered equal to –1. The amount of energy received by the device per minute does not exceed 1000 conventional units. The total number of instrument readings in a series does not exceed 10,000.
Problem A (2 points).
Write a program in any programming language to solve the given problem, in which the input data will be stored in an array, after which all possible pairs of elements will be checked.
Problem B (4 points).
Write a program to solve the problem that is both time and memory efficient (or at least one of those characteristics).
Input
The first line specifies the number N – the total number of instrument readings. It is guaranteed that \(N > 9\). Each of the following N lines specifies one non-negative integer – another reading of the instrument.
Imprint
The program should output one number – the work described in the condition.
Examples
| # |
Input |
Output |
| 1 |
11
12
45
5
3
17
23
21
20
19
12
26
|
1170 |
| |
![]()
|
|
Темы:
USE - computational tasks
A set of points with integer coordinates is specified on the plane. It is necessary to find the minimum possible area of a non-degenerate (that is, having a non-zero area) triangle, one of whose vertices is located at the origin, and the other two lie on the bisectors of the angles formed by the coordinate axes, and at the same time belong to a given set. If such a triangle does not exist, print "NO".
Write a time and memory efficient program to solve this problem.
A program is considered efficient in time if, with an increase in the number of points by a factor of k, the running time increases by no more than k times.
A program is considered memory efficient if the size of the memory to store all the necessary data does not depend on the number of points and does not exceed 1 kilobyte.
Before the text of the program, briefly describe the solution algorithm, indicate the programming language and its version.
Input
The first line specifies N – the number of points in the given set.
The following lines each contain two integers – coordinates of the next point.
Output
If the required triangle exists, the program should print a single number: the minimum possible area of the triangle that satisfies the conditions. If the required triangle does not exist, the program should print the message: «NO».
Examples
| # |
Input |
Output |
| 1 |
3
6 6
-8 8
9 7
|
48 |
| |
![]()
|
|
Темы:
USE - computational tasks
From digital sensors, the computer receives information about the characteristics of the physical process. The result of each measurement is an integer.
You are invited to write an efficient, including memory-used, program that will output the third largest (counting from the minimum) value of the measurement. If multiple dimensions have the same values, they are counted as one dimension. If the value you are looking for does not exist (for example, when all dimension values are equal), then you need to print the character "#". Please note that the number of measurements can be very large.
The input to the program in the first line is the total number of N measurement values.
Each of the following N lines contains an integer. It is guaranteed that \(N>0\), i.e. there is always at least one dimension.
Examples
| # |
Input |
Output |
| 1 |
5
100
10
100
10
100
| # |
| |
![]()
|
Темы:
USE - computational tasks
The input of the program is a sequence of N natural numbers. You need to choose an arbitrary number of numbers from them so that their sum is maximum and not divisible by 4.
As a result, the program should display the number of selected numbers and their sum. If it is impossible to get the required amount, 0 should be returned as an answer.
Input
The input to the program is a natural number N (\(N <= 1000\)), and then N< /code> natural numbers, each of which does not exceed 10000.
Output
The program should output two numbers: first, the number of selected numbers, and then their sum.
Examples
| # |
Input |
Output |
| 1 |
3
1
2
1
|
2 3 |
| |
![]()
|
Темы:
USE - computational tasks
Given a set of N integers. It is necessary to determine the number of elements that have values that are not equal to the value of the maximum element from this set.
Write a time and memory efficient program to solve this problem. The program is considered efficient in time if the increase in the number of initial numbers N by k times increases the running time of the program by no more than k times. A program is considered memory efficient if the memory required to store program variables does not exceed one kilobyte and does not increase with increasing N.
Input
The first line of the input specifies the number of numbers N (\(1 <= 𝑁 <=100 000\)). In each of the subsequent 𝑁 lines contains one integer not exceeding 1000 modulo.
Output
Output one number - the answer to the problem
Examples
| # |
Input |
Output |
| 1 |
5
7
-5
9
8
9
|
3 |
In the given set of 5 numbers, there are three elements — 7, –5 and 8, whose values are not equal to the value of the maximum element of this set — 9.
| |
![]()
|
|
Темы:
USE - computational tasks
The radio telescope is trying to receive and analyze signals from space. Various noises are translated into a sequence of a real non-negative number, specified with an accuracy of 1 digit after the decimal point. In order to describe different parts of space, it was decided to characterize the data received from one region by a number equal to the maximum product that can be obtained by multiplying the values of the signals coming from this region. That is, it is required to choose such a non-empty subset of signals (it can include both one signal and all received signals), the product of values of which will be maximum. If there are several such subsets, then you can choose any of them.
Write an efficient program, including in terms of memory used, that will process the results of the experiment, finding the required subset. There can be a lot of signals, but it cannot be less than three. All signals are different.
Before the text of the program, briefly describe the algorithm you use to solve the problem.
Input
The number of signals N is given as input to the program in the first line. Each of the following N lines contains one real number with an accuracy of 1 digit after the decimal point. All numbers are different.
Imprint
The program should display in ascending order the numbers of signals, the product of which will characterize the given series. Signals are numbered starting from one.
Examples
| # |
Input |
Output |
| 1 |
5
12.3
0.1
100.2
0.3
1.4 |
1 3 5 |
| |
![]()
|
|
Темы:
USE - computational tasks
The communication channel transmits data as a sequence of positive integers. The number of numbers is not known in advance, but not less than two. The sign of the end of the data is the number 0. After the data, a control value is transmitted. It is equal to the maximum possible product of two numbers from the passed set, which is divisible by 7, but not divisible by 49. If such a product cannot be obtained, the control value is considered equal to 1.
Write an efficient program, including from memory, that will simulate the process of receiving data. The program should enter all the numbers and the control value, and print a summary report including the number of numbers received, the control value received, the calculated control value, and a match output.
Before the text of the program, briefly describe the algorithm for solving the problem, indicate the programming language used and its version.
Input
Each line of the input data contains one integer. First there are lines with basic data – positive numbers, then the number 0 (a sign of the end of the data), in the last line – control value.
Imprint
The program should output a report in the form shown below in the example.
Examples
| # |
Input |
Output |
| 1 |
6
7
8
9
0
64 |
input: 4
reference value: 64
calculated value: 63
values false |
The last line may contain values true depending on the result
| |
![]()
|
|
Темы:
USE - computational tasks
A long-term experiment is being conducted in the physics laboratory to study the Earth's gravitational field. Every minute a positive integer number – is transmitted to the laboratory via the communication channel. the current reading of the Sigma 2015 instrument. The number of transmitted numbers in the series is known and does not exceed 100,000. All numbers do not exceed 10,000. The time during which the transmission takes place can be neglected. You need to calculate the "beta value" a series of instrument readings – the minimum even product of two readings, between the moments of transmission of which at least 6 minutes have elapsed. If such a product cannot be obtained, the answer is considered to be -1.
Write a program to solve the given problem that is both time and memory efficient (or at least one of those characteristics).
Input
The first line contains the number N – the total number of instrument readings. It is guaranteed that \(N>6\). Each of the following N lines specifies one positive integer – another reading of the device.
Output
The program should output one number - the product described in the condition, or -1 if such a product cannot be obtained.
Examples
| # |
Input |
Output |
| 1 |
12
45
5
3
1
7
23
21
20
19
18
1
7 |
18 |
| |
![]()
|
Темы:
USE - computational tasks
There is a data set consisting of pairs of positive integers. For each pair of numbers, the value A – greatest common divisor.
Write a time- and memory-efficient program that will determine which A value is most common. If multiple A values occur the same maximum number of times, output them in descending order.
A program is considered time efficient if the program execution time is proportional to the number of N pairs, i.e. when N increases by k times the running time of the program should increase no more than k times.
A program is considered memory efficient if the amount of memory used in the program to store data does not depend on the number N and does not exceed 100 kilobytes.
Input
The input to the program in the first line is the number of N pairs (\(1 <= N <= 100000\)). Each of the following N lines contains two natural numbers not exceeding 1000.
Input
Output the answer to the problem
Examples
| # |
Input |
Output |
| 1 |
6
1 3
5 15
6 9
5 4
3 3
36 40
|
3 1 |
| |
![]()
|
|
Темы:
USE - computational tasks
There is a data set consisting of triples of natural numbers. It is necessary to choose two numbers from each triple so that the sum of all the chosen numbers is a multiple of 4 and at the same time is the maximum possible. If it is impossible to get the required amount, return 0 as an answer.
Input
The input to the program in the first line is the number of triples N (\(1 <= N <= 100000\)). Each of the following N lines contains three natural numbers not exceeding 10,000.
Imprint
Output the answer to the problem
Examples
| # |
Input |
Output |
| 1 |
6
8 3 4
4 8 12
9 5 6
2 8 3
12 3 5
1 4 12
|
88 |
| |
![]()
|
Темы:
USE - computational tasks
There is a data set consisting of triples of natural numbers. It is necessary to choose exactly one number from each triple so that the sum of all the chosen numbers is not a multiple of 4 and at the same time is the maximum possible. If it is impossible to get the required amount, return 0 as an answer.
Write an efficient program that solves the problem.
Input
The input to the program in the first line is the number of triples N (\(1 <= N <= 100000\)). Each of the following N lines contains three natural numbers not exceeding 10,000.
Imprint
Output the answer to the problem
Examples
| # |
Input |
Output |
| 1 |
6
1 3 2
5 12 12
6 8 12
5 4 12
3 3 12
1 1 13
|
63 |
| |
![]()
|
Темы:
USE - computational tasks
On Voskhod satellite installed a device designed to measure solar activity. Every minute the device transmits a natural number – the amount of solar radiation energy received in the last minute, measured in arbitrary units. The time during which the transfer occurs can be neglected. It is necessary to find in a given series the number of pairs of such readings of the device, the product of which is a multiple of 6 and between the moments of transmission of which at least three minutes have passed. The amount of energy received by the device per minute does not exceed 1000 conventional units. The total number of instrument readings in a series does not exceed 10,000.
Problem A (2 points). Write, in any programming language, a program to solve the problem, in which the input data will be stored in an array, after which all possible pairs of elements are checked.
Problem B (4 points). Write a program to solve the given problem that is both time and memory efficient (or at least one of these characteristics) .
Input
The first line specifies the number N – the total number of instrument readings. It is guaranteed that \(N>3\). Each of the following N lines contains one natural number – another reading of the device.
Examples
| # |
Input |
Output |
| 1 |
5
6
2
4
1
3
|
3 |
In the given set of 5 numbers, there are three pairs (6, 3), (2, 3) and (6, 1) that satisfy the condition of the problem.
| |
![]()
|
|
Темы:
Dynamic programming
USE - computational tasks
The input of the program is a natural number N, and then N integers. It is necessary to determine the maximum sum of adjacent elements of the sequence. N does not exceed 1000000, each element of the sequence does not exceed 100 in absolute value.
Examples
| # |
Input |
Output |
| 1 |
9
-2
1
-3
4
-1
2
1
-5
4
|
6 |
Explanations: for a given sequence of numbers (-2 1 -3 4 -1 2 1 -5 4), the largest sum can be obtained for an adjacent sequence of elements: 4 -1 2 1.
The decision for 2 points is awarded when the program passes 50% of the tests, 3 points - when the program passes 75% of the tests.
| |
![]()
|
|
Темы:
USE - computational tasks
The input of the program is a natural number N, and then N integers. It is necessary to determine the maximum product of adjacent elements of the sequence. N does not exceed 10000, each element of the sequence does not exceed 100 in absolute value.
Examples
| # |
Input |
Output |
| 1 |
7
2
3
-2
-3
-1
4
6
|
72 |
Explanations: the largest product can be obtained for the sequence -3 -1 4 6.
| |
![]()
|
|
Темы:
USE - computational tasks
The input of the program is a sequence of N integers (\(N>1\)) . It is necessary to find such a set of numbers from the given series that their sum will be even and maximum. Number of numbers in set k (\(1 <= k <= N\)).
Input
The first line of the input specifies the number of numbers N (\(2 <= N <= 10000\)). Each of the following N lines contains a single integer in the range of –100 to 100.
Imprint
Output one number: the maximum even sum.
Examples
| # |
Input |
Output |
| 1 |
8
-5
-13
15
-9
-3
-6
-10
-8 |
12 |
| |
![]()
|
Темы:
USE - computational tasks
Given a set of N natural numbers. It is necessary to determine the number of pairs of elements (ai, aj) of this set in which 1 <= i < j <= N and the product of the elements is a multiple of 6.
Write a time and memory efficient program to solve this problem.
Input
The first line of the input specifies the number of numbers N (\(1 < N <= 100000\)). Each of the following N lines contains one natural number not exceeding 1000.
Imprint
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
4
7
5
6
12
|
5 |
In the given set of 4 numbers, there are five pairs (7, 6), (5, 6), (7, 12), (5, 12), (6, 12), the product of whose elements is a multiple of 6.
| |
![]()
|
Темы:
USE - computational tasks
Given a set of N natural numbers. It is necessary to determine the number of pairs of elements (ai, aj) of this set, in which \(1 < i < j < N\) and the sum of the elements is a multiple of 12.
Write a time and memory efficient program to solve this problem.
Input data
The first line of the input specifies the number of numbers N (\(1 < N <= 10000\)). Each of the following N lines contains one natural number not exceeding 1000.
Imprint data
Output the answer to the problem
Examples
| # |
Input |
Output |
| 1 |
5
7
5
6
12
24
|
2 |
In the given set of 5 numbers, there are two pairs (7, 5) and (12, 24) whose sum of elements is a multiple of 12.
| |
![]()
|
|
Темы:
USE - computational tasks
Given N pairs of numbers. From each pair, you need to choose one number so that the sum of the selected numbers is the largest possible and is not divisible by 4. In the first line, enter the number N, which does not exceed 100,000.
If there are no such numbers, output "NO".
The input is the number of pairs, then the pairs themselves.
Input
The first line specifies the number of pairs. The following lines contain the pairs themselves. Modulo numbers do not exceed 30,000.
Imprint
Output the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
6
1 2
4 9
3 5
7 2
4 4
2 2
|
29 |
| |
![]()
|
|
Темы:
USE - computational tasks
Given N pairs of numbers. From each pair, you need to choose one so that the sum of the selected numbers is the smallest possible and is not divisible by 4. In the first line, enter the number N, not exceeding 100,000.
If there are no such numbers, output "no".
The input is first the number of pairs, then the pairs themselves. Modulo numbers do not exceed 30,000.
Examples
| # |
Input |
Output |
| 1 |
6
10 10
17
25
4 5
6 9
13 13
| 37 |
| |
![]()
|
Темы:
USE - computational tasks
The input of the program is a sequence of natural numbers A. The number of elements in the sequence is greater than 7. It is necessary to determine the number of such pairs of elements of the sequence Ai and Aj ,\( j - i > 4\), where i and j – the numbers of the elements of the sequence, where the sum of the numbers in each of these pairs is a multiple of 3.
Write a program to solve the problem that is both time and memory efficient (or at least one of those characteristics).
Input
In each line of the input one natural number is written, not exceeding 30000. Numeric input ends in zero.
Imprint
As an answer, the program should output a single number – the number of pairs of elements that satisfy the condition.
Examples
| # |
Input |
Output |
| 1 |
10
12
81
2
7
33
99
21
11
121
10
0
|
6 |
| |
![]()
|
Темы:
USE - computational tasks
The input of the program is a sequence of N positive integers. All pairs of different elements of the sequence are considered (the elements of a pair do not have to be side by side in the sequence, the order of the elements in the pair is not important).
It is necessary to determine the number of pairs, the sum of which is a multiple of 3, and the product is a multiple of 5. The number N and then the N numbers themselves are input to the algorithm.
Input
The first line of the input specifies the number of numbers N (\(1 < N <= 10000\)). Each of the following N lines contains one natural number not exceeding 10000.
Imprint
As a result, the program should display one number: the number of pairs found.
Examples
| # |
Input |
Output |
| 1 |
10
1
2
3
4
5
6
7
8
9
10 |
6 |
Found pairs for example: {(1;5) (2;10) (4;5) (5;7) (5;10) (8;10)}
| |
![]()
|
Темы:
USE - computational tasks
The input of the program is a sequence of N positive integers. All pairs of different elements of the sequence are considered (the elements of a pair do not have to be side by side in the sequence, the order of the elements in the pair is unimportant).
It is necessary to determine the minimum sum of an arbitrary pair of numbers and the number of pairs with the sum equal to the minimum.
Input
The first line of the input specifies the number of numbers N (\(1 < N <= 10000\)).
Each of the following N lines contains one natural number not exceeding 10000.
Imprint
As a result, the program should display two numbers: the found minimum sum and the number of pairs with the sum equal to the minimum.
Examples
| # |
Input |
Output |
| 1 |
10
1
2
3
1
2
3
1
2
3
1
|
2 6 |
| 2 |
5
2
2
1
2
2
|
3 4 |
| |
![]()
|
Темы:
USE - computational tasks
Given a set of N natural numbers. It is necessary to determine the number of pairs of elements (ai, aj) of this set, in which \(1 <= i < j <= N\) and the product of the elements is a multiple of 14.
Write a time and memory efficient program to solve this problem.
Input data
The first line of the input specifies the number of numbers N (\(1 < N <= 10000\)). Each of the following N lines contains one natural number not exceeding 1000.
Imprint data
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
5
14
7
7
2
19 |
6 |
| |
![]()
|
|
Темы:
USE - computational tasks
The input of the program is a sequence of N positive integers, all numbers in the sequence are different. All pairs of distinct elements are considered sequences (the elements of a pair do not have to be side by side in the sequence, the order of the elements in the pair is not important). It is necessary to determine the number of pairs for which the product of elements is divisible by 26.
Input
The first line of the input specifies the number of numbers N (\(1 < N <= 100000\)). Each of the following N lines contains one positive integer not exceeding 10,000.
Imprint
As a result, the program should print one number: the number of pairs in which the product of elements is a multiple of 26.
Examples
| # |
Input |
Output |
| 1 |
4
2
6
13
39
|
4 |
Explanation. From the four given numbers, 6 pairwise products can be made: 2*6, 2*13, 2*39, 6*13, 6*39, 13*39 (results: 12, 26, 78, 78, 234, 507). Of these, 4 works are divided into 26 (2*13=26; 2*39=78; 6*13=78; 6*39=234).
| |
![]()
|
Темы:
USE - computational tasks
The input of the program is a natural number N ( \(N<= 100000\)), and then N lines, each containing one integer. It is necessary to count the number of pairs of numbers whose indices differ by at least three and the product is a multiple of 29.
Write a memory and time efficient program.
Examples
| # |
Input |
Output |
| 1 |
6
29
7
8
29
4
5 |
3 |
| |
![]()
|
|
Темы:
USE - computational tasks
The input of the program is a sequence of N positive integers, all numbers in the sequence are different. All pairs of different elements of the sequence are considered, located at a distance of at least 4 (the difference in the indices of the elements of the pair must be 4 or more, the order of the elements in the pair is unimportant). It is necessary to determine the maximum sum of a pair of numbers divisible by 112, while the first element of the pair must be greater than the second (\(a[i] > a[j]\), \(i < j\)).
Input
The first line of the input specifies the number of numbers N (\(5 <= N <= 1000\)). Each of the following N lines contains one positive integer not exceeding 10,000.
Input
The program should print one number in the first line: the maximum sum of a pair of elements located in the sequence at a distance of at least 4, in which the sum of the elements is a multiple of 112, and in the second line – numbers that form a pair, separated by a space. If there are no suitable pairs, you need to print a single number –1.
Examples
| # |
Input |
Output |
| 1 |
7
119
62
343
50
48
105
274 |
224
119 105
|
| |
![]()
|
|
Темы:
USE - computational tasks
The input of the program is a sequence of N positive integers. All pairs of different elements of the sequence are considered (the elements of a pair do not have to be side by side in the sequence, the order of the elements in the pair is unimportant). It is necessary to determine the maximum sum of the elements of a pair so that the sums of the elements of the pair and their indices are a multiple of 3. If such a sum is not found, output "–1". Element numbering starts from 1.
Write a memory and time efficient program.
Input
The first line of the input specifies the number of numbers N ( \(1 < N <= 100000\)). Each of the following N lines contains one natural number not exceeding 10000.
Imprint
As a result, the program should output one number: the maximum sum of a pair that is a multiple of three with the sum of the indices that is a multiple of three, or " –1" if no such pair was found.
Examples
| # |
Input |
Output |
Comment |
| 1 |
10
1 2 3 4 5 6 7 8 9 10
|
18 |
found pair: (a[8]=8; a[10]=10) |
| 2 |
23
36 16 15 15 17 16 14 15 47 22 27 29 35 23 39 29 15
25 16 35 28 45 26
|
75 |
pair found: (a[9]=47; a[21]=28) |
Note: in the examples, array elements are placed on a single line to save space and improve readability. In the tests themselves for the task, all elements are located one number per line.
| |
![]()
|
Темы:
USE - computational tasks
The input of the program is a sequence of N non-negative integers. All pairs of different elements of the sequence are considered (the elements of a pair do not have to be side by side in the sequence, the order of the elements in the pair is not important). Find the maximum sum of an arbitrary pair of non-zero elements of a sequence. The found sum must be a multiple of three and there must be zero elements between the elements of the pair. If there is no such pair, print 0.
Input
The first line of the input specifies the number of numbers N (\(1 < N <= 10000\)). Each of the following N lines contains one non-negative integer not exceeding 10000.
Input
As a result, the program should output a single number, the number of pairs found.
Examples
| # |
Input |
Output |
| 1 |
7
1
0
2
0
5
0
8 |
9 |
| |
![]()
|
|
Темы:
USE - computational tasks
You are given a sequence N of positive integers. All pairs of elements of the sequence are considered, located at a distance of at least 8 from each other (the difference in the indices of the elements must be 8 or more). It is necessary to determine the maximum sum of such a pair.
Write a time and memory efficient program to solve this problem.
Input
The first line of the input specifies the number of numbers N (\(9 <= N <= 100000\)). Each of the following N lines contains one natural number not exceeding 10000.
Input
Print the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
10
1
3
5
4
6
7
9
10
12
11 |
14 |
Explanation. From 10 numbers, you can make 3 pairs that satisfy the condition. These will be elements with indices 1 and 9, 1 and 10, 2 and 10. For a given set of numbers, we get pairs (1, 12), (1, 11), (3, 11). The maximum sum of numbers in these pairs is 14.
| |
![]()
|
|
Темы:
Remains
USE - computational tasks
Anna Nikolaevna has N boxes of sweets. The i-th box contains Ai the number of sweets. Anna Nikolaevna takes sweets from several consecutive boxes and evenly distributes them < code>M children. Find the number of pairs (l, r) that satisfy the following conditions:
- l and r are integers and satisfy the condition 1<=l<=r<=N;
- Al + Al+1 +< /code> ... + Ar is divisible by M.
Input
The program receives two lines as input. The first line contains two integers N (1<=N<=105) and M (2<=M<=109). The second line contains N numbers Ai (1<=Ai<=109< /sup>, 1<=i<=N).
Imprint
Print the number of pairs (l, r) that satisfy the conditions. Note that the number may not correspond to a 32-bit integer type.
Examples
| # |
Input |
Output |
| 1 |
3 2
4 1 5
| 3 |
| 2 |
13 17
29 7 5 7 9 51 7 13 8 55 42 9 81
| 6 |
| |
![]()
|
|
Темы:
USE - computational tasks
You are given a sequence of N natural numbers. All its continuous subsequences are considered, such that the sum of the elements of each of them is a multiple of k = 43. Find among them a subsequence with the maximum sum, determine its length. If there are several such subsequences, in the answer indicate the number of elements of the shortest of them.
Input
Given two input files (file A and file B), each containing in the first line, the number of numbers N (1<= N <= 10,000,000). Each of the following N lines contains one natural number not exceeding 10 000.
An example of the organization of source data in the input file:
7
21
13
9
19
17
26
95
In this set, you can select the sequences 21+13+9 (the sum of 43) and 17+26 (the sum of 43 ). The shortest one, 17 + 26, is 2 long. For the specified, the program should output the number 2.
Warning: do not use brute-force algorithm to process file B, which calculates the sum of all possible options, as the program written in such an algorithm will run too long.
| |
![]()
|
|
Темы:
USE - computational tasks
Given a sequence of N natural numbers. It is known that the sum of all numbers in the sequence does not exceed 109. All its continuous subsequences are considered, in which the number of even numbers is a multiple of K = 8. Find the largest sum of such a subsequence.
Input
Given two input files (file A and file B), each containing in the first line, the number of numbers N (1 <= N <= 1,000,000). Each of the following N lines contains one natural number not exceeding 1000.
An example of the organization of source data in the input file (for К=4):
6
9
16
4
12
10
18
In this set, you can select the sequences 9+16+4+12+10 (sum 51) and 4+12+10+18 (sum 44).
Response(for K = 4): 51.
Warning: do not use brute-force algorithm to process file B, which calculates the sum of all possible options, as the program written in such an algorithm will run too long.
| |
![]()
|
|
Темы:
USE - computational tasks
Given a sequence of N natural numbers. It is known that the sum of all numbers in the sequence does not exceed 109. All its continuous subsequences are considered, in which the number of odd numbers is a multiple of K = 7. Find the largest sum of such a subsequence.
Input
Given two input files (file A and file B), each containing in the first line, the number of numbers N (1 <= N <= 1,000,000). Each of the following N lines contains one natural number not exceeding 1000.
An example of the organization of source data in the input file (for К=4):
6
8
17
3
13
11
21
In this set, you can select the sequences 8+17+3+13+11 (sum 52) and 3+13+11+21 (sum 48).
Answer(for K = 4): 52.
Warning: do not use brute-force algorithm to process file B, which calculates the sum of all possible options, as the program written in such an algorithm will run too long.
| |
![]()
|
|
Темы:
USE - computational tasks
Given a sequence of N numbers. It is known that the sum of all numbers in the sequence does not exceed 109. All its continuous subsequences are considered, in which the number of positive numbers is a multiple of K = 11. Find the largest sum of such a subsequence.
Input
Given two input files (file A and file B), each containing in the first line, the number of numbers N (1 <= N <= 1,000,000). Each of the following N lines contains one number, modulo not exceeding 1000.
An example of the organization of source data in the input file (for K=3):
6
-1
2
3
-5
18
12
In this set, you can select the sequences -1+2+3+(-5)+18 (the sum of 17) and 3+(-5)+ 18+12 (sum 28).
Answer(for K = 3): 28.
Warning: do not use brute-force algorithm to process file B, which calculates the sum of all possible options, as the program written in such an algorithm will run too long.
| |
![]()
|
|
Темы:
USE - computational tasks
Given a sequence of N numbers. All its continuous subsequences are considered, in which the number of negative numbers does not exceed C. Find among them a subsequence with the maximum sum, length L.
Input
Given two input files (file A and file B), each of which contains the first line feeds 3 numbers: the number of numbers N (1 <= N <= 1 000 000), L< /code> and C (\(1 <= L, C <= N <= 1,000,000\)). Each of the following N lines contains a single number not exceeding 1000 modulo.
An example of the organization of source data in the input file (for L = 3 and C = 3):
5 3 3
1
-1
2
-2
3
Several sequences can be selected in this set, but with a maximum sum of 3 it will be: 2+(-2)+3.
Answer(for С = 3 and L = 3): 3. ;
In your answer, indicate two numbers: first, the value of the required amount for file A, then for file B.
Warning: do not use brute-force algorithm to process file B, which calculates the sum of all possible options, as the program written in such an algorithm will run too long.
| |
![]()
|
|
Темы:
USE - computational tasks
Given a sequence of N numbers. All its continuous subsequences are considered, in which the number of positive numbers does not exceed C. Find among them the subsequence with the maximum sum, of length L.
Input
Given two input files (file A and file B), each of which contains the first line feeds 3 numbers: the number of numbers N (1 <= N <= 1 000 000), L< /code> and C (\(1 <= L, C <= N <= 1,000,000\)). Each of the following N lines contains a single number not exceeding 1000 modulo.
An example of the organization of source data in the input file (for L = 3 and C = 1):
5 3 1
1
-1
-5
-2
3
You can select multiple sequences in this set, but with a maximum sum of -4 it will be: -5+(-2)+3.
Answer(for C = 3 and L = 1): -4.
In your answer, indicate two numbers on one line separated by a space: first, the value of the required amount for file A, then for file B.
Warning: File B should not be processed by a brute-force algorithm that calculates the sum of all possible options, as the program written in such an algorithm will run too long.
| |
![]()
|
|
Темы:
USE - computational tasks
City M has a ring road N kilometers long with traffic in both directions. At each kilometer of the road there are garbage collection points of a certain capacity. Within the ring road, in one of the garbage collection points, they are going to install a waste processing plant in such a way that the cost of garbage delivery is minimal. The cost of garbage delivery is calculated as the capacity of the collection point multiplied by the distance from the collection point to the waste processing plant. If the waste processing plant is located near the collection point, the distance is considered to be zero. Containers are numbered from 1 to N.
Which waste collection point should be next to a waste recycling plant?
Description of input data
Given two input files (file A and file B), each containing (2 <= N <= 109) numbers. The first number N is the number of garbage containers. The following N numbers are the number of kilograms of garbage that is produced at the point.
Output Description
One number is the number of the garbage container next to which the recycling plant should be located.
In your answer, write two numbers on one line separated by a space: the answer for file A and the answer for file B.
Example of input data organization:
6
8
20
5
13
7
19
For this example, the answer is 6 (7*1 + 13*2 + 5*3 + 20*2 + 8*1 + 19*0).
| |
![]()
|
|
Темы:
USE - computational tasks
A long-term experiment is being conducted in the physics laboratory to study the Earth's gravitational field. Every minute a positive integer number – is transmitted to the laboratory via the communication channel. the current reading of the Gamma 2022 instrument. The number of transmitted numbers in the series is known and does not exceed 100,000. All numbers do not exceed 10,000. The time during which the transmission takes place can be neglected. You need to calculate the "gamma value" a series of instrument readings – the maximum even product of two readings, between the moments of transmission of which at least 10 minutes have passed. If such a product cannot be obtained, the answer is considered to be -1.
Write a program to solve the given problem that is both time and memory efficient (or at least one of those characteristics).
Input
The first line contains the number N – the total number of instrument readings. It is guaranteed that \(N > 10\). Each of the following N lines specifies one positive integer – another reading of the device.
Imprint
The program should output one number - the product described in the condition, or -1 if such a product cannot be obtained.
Examples
| # |
Input |
Output |
| 1 |
15
45
5
3
1
7
23
21
20
19
18
1
7
2
12
7 |
540 |
| |
![]()
|
|
Темы:
USE - computational tasks
A long-term experiment is being conducted in the physics laboratory to study the Earth's gravitational field. Every minute a positive integer number – is transmitted to the laboratory via the communication channel. the current reading of the Gamma 2022 instrument. The number of transmitted numbers in the series is known and does not exceed 100,000. All numbers do not exceed 10,000. The time during which the transmission takes place can be neglected. You need to calculate the "gamma value" a series of instrument readings – the minimum odd product of two readings, between the moments of transmission of which at least 6 minutes have elapsed. If such a product cannot be obtained, the answer is considered to be -1.
Write a program to solve the given problem that is both time and memory efficient (or at least one of those characteristics).
Input
The first line contains the number N – the total number of instrument readings. It is guaranteed that \(N>6\). Each of the following N lines specifies one positive integer – another reading of the device.
Output
The program should output one number - the product described in the condition, or -1 if such a product cannot be obtained.
Examples
| # |
Input |
Output |
| 1 |
12
45
5
3
1
7
23
21
20
19
18
1
7 |
1 |
| |
![]()
|