PREPARATION FOR THE NATIONAL COMPETITION IN INFORMATICS
|
This page is a guide for preparing the solution of tasks that appear in state competitions in computer science, for elementary schools. Also shown are simple examples that are an integral part of larger tasks.
If you have not previously prepared for the district competition, see the page Preparing for district competitions |
Figure 1: Preparation for the national competition in informatics
Image by Gerd Altmann from Pixabay
|
The National Competition in informatics in 2021
You can download tasks with solutions and test examples from the website of the Society of Mathematicians of Serbia:
dms.rs/informatika-osnovne-skole/
dms.rs/informatika-osnovne-skole/
1. Rainforest
Note: The task was taken from the website of the Society of Mathematicians of Serbia: dms.rs/informatika-osnovne-skole/
A miraculous table with 3 rows and 3 columns filled with numbers was found in the rainforest. The text of the riddle was found next to the table. The puzzle says: Form the first three-digit number based on the digits from the main diagonal of the table, starting from the top and going to the bottom of the table. Then form another three-digit number consisting of the digits in the side diagonal, also starting from top to bottom. The solution to the puzzle is the product of these two three-digit numbers. Write a program that loads the digits written on a spreadsheet and prints the product of two three-digit numbers that are formed in the manner described.
Explanation: The main diagonal of the table is formed by: the first digit of the first row, the middle digit of the second row and the last digit of the third row. The side diagonal is formed by: the last digit of the first row, the middle digit of the second row and the first
third row digit.
Input
In each of the three lines of the standard input, three digits are given, written without spaces.
Output
On standard output, the program must print one integer - the product of two three-digit number obtained in the manner described above.
Example 1
Input
123
456
789
Output
56763
Explanation of the example: The number formed by the digits on the main diagonal is 159. The number formed by the digits on the minor diagonal is 357. The product of these two numbers is 56763
A miraculous table with 3 rows and 3 columns filled with numbers was found in the rainforest. The text of the riddle was found next to the table. The puzzle says: Form the first three-digit number based on the digits from the main diagonal of the table, starting from the top and going to the bottom of the table. Then form another three-digit number consisting of the digits in the side diagonal, also starting from top to bottom. The solution to the puzzle is the product of these two three-digit numbers. Write a program that loads the digits written on a spreadsheet and prints the product of two three-digit numbers that are formed in the manner described.
Explanation: The main diagonal of the table is formed by: the first digit of the first row, the middle digit of the second row and the last digit of the third row. The side diagonal is formed by: the last digit of the first row, the middle digit of the second row and the first
third row digit.
Input
In each of the three lines of the standard input, three digits are given, written without spaces.
Output
On standard output, the program must print one integer - the product of two three-digit number obtained in the manner described above.
Example 1
Input
123
456
789
Output
56763
Explanation of the example: The number formed by the digits on the main diagonal is 159. The number formed by the digits on the minor diagonal is 357. The product of these two numbers is 56763
Analysis of the first task
In order to do this task, one of the possible ways of solving it is by using matrices and using nested loops. Given that these areas appear in the national competition, knowledge of these areas is recommended.
See more about matrices on the page: Two-dimensional arrays - matrix
Read more about nested loops on the page: Nested loops in C/C++
See more about matrices on the page: Two-dimensional arrays - matrix
Read more about nested loops on the page: Nested loops in C/C++
Before solving the task from the national competition, it is recommended to do the following examples first: example 1 and example 2
Example 1:
Enter 9 numbers in a 3*3 matrix. Print the values in the main and minor diagonals.
Example
Input:
1 2 3
4 5 6
7 8 9
Output
Main diagonal: 1 5 9
Side diagonal 3 5 7
Example
Input:
1 2 3
4 5 6
7 8 9
Output
Main diagonal: 1 5 9
Side diagonal 3 5 7
Solve the task according to the following algorithm:
- Use a two-dimensional array (matrix) to store data in 3 rows and 3 columns
- Enter matrix elements. Use nested for loops. The outer one should change rows, and the inner one should change columns
- Use nested for loops with the same control expressions to print array elements
- Use the if statement to check the condition for the main diagonal. Notice that for those elements the row and column are equal
- Use the if statement to check the condition for the side diagonal. Notice that for those elements the row and column are equal, if you change the columns from the last to the first
#include < iostream >
using namespace std;
int main()
{
using namespace std;
int main()
{
int A[3][3];
int X=0,Y=0;
//Changing rows
for(int i=0; i<3; i++)
{
int d=1000,d1=1000;
for(int i=0; i < 3; i++)
{
cout << (X*Y) << endl; /* result*/
return 0;
}int X=0,Y=0;
//Changing rows
for(int i=0; i<3; i++)
{
//Changing columns
for(int j=0; j<3; j++)
{
}for(int j=0; j<3; j++)
{
cin >> A[i][j];
}int d=1000,d1=1000;
for(int i=0; i < 3; i++)
{
//changing columns
for(int j=0; j < 3; j++)
{
cout << endl;
}for(int j=0; j < 3; j++)
{
int c=A[i][j];/* digit extracted from the matrix in the i-th row and j-th column. In cycles 1,5,9 */
if(i==j)
{
if(2-i==j)
{
}if(i==j)
{
d=d/10;/* 100,10,1 u ciklusima redom */
X=X+c*d; /* values 300,350,357 in cycles respectively */
}X=X+c*d; /* values 300,350,357 in cycles respectively */
if(2-i==j)
{
d1=d1/10; /*100,10,1 in cycles respectively */
Y=Y+c*d1;/* vrednosti 300,350,357 u ciklusima redom
}Y=Y+c*d1;/* vrednosti 300,350,357 u ciklusima redom
cout << endl;
cout << (X*Y) << endl; /* result*/
return 0;
Make a number from known digits
Example 2:
Enter 4 integers representing the digits of a four-digit number. Make a new number whose digits are in reverse order.
Example:
Input:
4
5
6
7
Output:
7654
Example:
Input:
4
5
6
7
Output:
7654
The last digit entered is the digit 1000, so it should be multiplied by 1000, the penultimate digit by 100, the third digit from the back by 10, etc. The number obtained is the sum of the mentioned products
#include < iostream >
using namespace std;
int main()
{
using namespace std;
int main()
{
int a,b,c,d,broj;
cin >> a >> b >> c >> d;
broj=1000*d + 100*c + 10*b + a;
cout << broj << endl;
return 0;
}cin >> a >> b >> c >> d;
broj=1000*d + 100*c + 10*b + a;
cout << broj << endl;
return 0;
2. The sum of squares of odd numbers
Note: The task was taken from the website of the Society of Mathematicians of Serbia: dms.rs/informatika-osnovne-skole/
Lenka wants to calculate the sums of the squares of the odd digits of several numbers. Help Lenka and write a program that loads one natural number less than a billion from the standard input and prints the sum of the squares of its odd digits on the standard output (if there are no such digits, we consider the sum to be zero). The square of a digit is equal to the product of that digit with itself. For example, the square of the digit 3 is
3, because 3×3=9
Example 1
Input
1234560
Output
35
Example 2
Input
11
Output
2
Example 3
Input
888
Output
0
Lenka wants to calculate the sums of the squares of the odd digits of several numbers. Help Lenka and write a program that loads one natural number less than a billion from the standard input and prints the sum of the squares of its odd digits on the standard output (if there are no such digits, we consider the sum to be zero). The square of a digit is equal to the product of that digit with itself. For example, the square of the digit 3 is
3, because 3×3=9
Example 1
Input
1234560
Output
35
Example 2
Input
11
Output
2
Example 3
Input
888
Output
0
Analysis of the second task
In order to extract digits from a number, it is necessary to use the operators % and /, i.e. dividing by some of the powers with base 10 or the remainder of dividing by these numbers. A similar example is covered in task 4 from the website Data and data types - additional examples
It also requires knowledge of loops and how to add numbers using a loops. A similar example is explained on the web page Additional examples for the loops topic (Task 3)
It also requires knowledge of loops and how to add numbers using a loops. A similar example is explained on the web page Additional examples for the loops topic (Task 3)
Solve the task according to the following algorithm:
- Enter an integer number
- Using loops(while) extract the last digit on the right from the rest of the number
- The rest of the number is that number before the loop starts, and inside the loop it is transformed by dividing by 10 and removing one digit
- The procedure is repeated until the remainder of the number is greater than zero
- Add the square of the selected digit to the current sum, increasing it gradually through the loop
- Do not forget that the sum is initialized to the value zero before the start of the loop
#include < iostream >
using namespace std;
int main()
{
using namespace std;
int main()
{
int num,x;
int sum=0;//sum, which initialized to zero
cin >> num;
x=num;
while( x > 0 ){
cout << sum << endl;
return 0;
}int sum=0;//sum, which initialized to zero
cin >> num;
x=num;
while( x > 0 ){
int c=x % 10;//digit on the right
x=x/10;//remove digit on the right side
if((c % 2) != 0){//is the this odd number?
}x=x/10;//remove digit on the right side
if((c % 2) != 0){//is the this odd number?
sum += c*c;//the sum of the squares of the numbers is formed
}cout << sum << endl;
return 0;
3. The magic sequence of numbers
Napomena: The task was taken from the Society of Mathematicians of Serbia: dms.rs/informatika-osnovne-skole/
Laza decided to make a magic series of numbers in the following way: Laza started to make a series from some given number and each subsequent member of the series is obtained by adding the number of all its divisors to the previous number. For example, if one member of the sequence is equal to 6, then the next member of the sequence is equal to 6 + 4 ie. 10, because there are exactly 4 divisors of the number 6 (these are the numbers 1, 2, 3, 6, respectively).
Write a program that loads from the standard input in the first line the first member of the sequence (0<a1≤10000) and in the second line a natural number N (0<N≤100), and prints the Nth member of Laza's sequence to the standard output.
Example 1
Input
2
4
Output
9
Explanation: a1=2, a2=4, a3=7, a4=9
Example 2
Input
3882
93
Output
4878
Laza decided to make a magic series of numbers in the following way: Laza started to make a series from some given number and each subsequent member of the series is obtained by adding the number of all its divisors to the previous number. For example, if one member of the sequence is equal to 6, then the next member of the sequence is equal to 6 + 4 ie. 10, because there are exactly 4 divisors of the number 6 (these are the numbers 1, 2, 3, 6, respectively).
Write a program that loads from the standard input in the first line the first member of the sequence (0<a1≤10000) and in the second line a natural number N (0<N≤100), and prints the Nth member of Laza's sequence to the standard output.
Example 1
Input
2
4
Output
9
Explanation: a1=2, a2=4, a3=7, a4=9
Example 2
Input
3882
93
Output
4878
Analysis of the third example
The task can be done by separating the procedure of determining the number of divisors for the entered number into a separate method.
Solving the task requires knowledge of:
Solving the task requires knowledge of:
The example can be done by separating the procedure of determining the number of divisors for the entered number into a separate method. In the main method, after entering the first member of the sequence, a loop of k repetitions would be formed, where k is the number of elements of the sequence and that number is also entered. In each cycle of the loop, the number of divisors of the current member of the array would be determined by calling an additional method (it can be done without using methods by writing the entire procedure for determining the number of divisors inside the loop). The resulting number of divisors would be used to calculate the next element in the sequence.
#include < iostream >
using namespace std;
/*The method that, for an entered number n, determines how many divisors there are*/
int numberOfDivisors(int n)
{
int main()
{
using namespace std;
/*The method that, for an entered number n, determines how many divisors there are*/
int numberOfDivisors(int n)
{
int num=0;//number of divisors
for(int i=1;i<=n;i++)
{
cout << endl;
return num;
}
for(int i=1;i<=n;i++)
{
if(n%i == 0)//tests for divisibility with the current value of variable "i"
{
}{
br++;//if it is divisible by "i", it increases the number of divisors by 1
cout << i << " ";
}cout << i << " ";
cout << endl;
return num;
int main()
{
int a1,numOfDiv=0,n;
cin >> a1 >> n;
int x=a1;//the current element of an array
for(int i=1; i
{
cout << x << endl;
return 0;
}cin >> a1 >> n;
int x=a1;//the current element of an array
for(int i=1; i
numOfDiv=numberOfDivisors(x);
x=x+numOfDiv;
cout << x << endl;
numOfDiv=0;
}x=x+numOfDiv;
cout << x << endl;
numOfDiv=0;
cout << x << endl;
return 0;
4. The place of the Kth occurrence of the number
Note: The task was taken from the Society of Mathematicians of Serbia: dms.rs/informatika-osnovne-skole/
Let's look at the following lines:
1
121
12321
1234321
123454321
............................
A sequence whose ordinal number is M (M=1, 2, 3, ...) is formed by writing the natural numbers in order from 1 to M, and then writing the numbers in the reverse direction from M-1 to 1. Now we form an infinite sequence by taking the first of the above lines and adding to it
the second row, then we add the third row and so on.
The beginning of the formed infinite series of numbers looks like this: 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 1 2 3 4 5 4 3 2 1 ...
The members of this series are numbered starting from one. Write a program that finds in which place the given number n occurs for the kth time.
Entrance
In a single line of standard input, two integers n and k, separated by one, are given
with a space character (0<n≤1000000, 0<k≤1000000).
Exit
On the standard output, the program must print the integer - the position of the kth occurrence
of n numbers in a sequence.
Example 1
Input
1 1
Output
1
Example 2
Input
2 2
Output
6
Example 3
Input
3 3
Output
14
Let's look at the following lines:
1
121
12321
1234321
123454321
............................
A sequence whose ordinal number is M (M=1, 2, 3, ...) is formed by writing the natural numbers in order from 1 to M, and then writing the numbers in the reverse direction from M-1 to 1. Now we form an infinite sequence by taking the first of the above lines and adding to it
the second row, then we add the third row and so on.
The beginning of the formed infinite series of numbers looks like this: 1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1 1 2 3 4 5 4 3 2 1 ...
The members of this series are numbered starting from one. Write a program that finds in which place the given number n occurs for the kth time.
Entrance
In a single line of standard input, two integers n and k, separated by one, are given
with a space character (0<n≤1000000, 0<k≤1000000).
Exit
On the standard output, the program must print the integer - the position of the kth occurrence
of n numbers in a sequence.
Example 1
Input
1 1
Output
1
Example 2
Input
2 2
Output
6
Example 3
Input
3 3
Output
14
Analysis of the fourth task
Solving the task requires prior knowledge of the following areas:
Let's observe the following rule. Let's analyze the number, the subarray where that number is in the middle of the array, the length of the subarray and the position of the last element at the end of the current subarray.
| Number | A new member is added to the array | The length of the subarray | Position at the end |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 2 | 1 2 1 | 3 | 4 |
| 3 | 1 2 3 2 1 | 5 | 9 |
| 4 | 1 2 3 4 3 2 1 | 7 | 7 |
| 5 | 1 2 3 4 5 4 3 2 1 | 9 | 9 |
| 6 | 1 2 3 4 5 6 5 4 3 2 1 | 11 | 20 |
Enter the number "n" and the number of required occurrences "k". Then through the loop do the following:
- Increase the number value (1st column in the table)
- Until the number reaches the value n, move only the length and position (3rd and 4th columns). Until then, there is certainly not a single occurrence of the number n.
- In the row (cycle) in which the counter has reached the value n, the first occurrence that is exactly in the middle of the substring has been reached.
- In the following rows, if there are more than two occurrences until reaching the k-th occurrence, in addition to changing the position and length according to the established rule, the number of occurrences should be increased by 2
- In the following lines, if it is less than or equal to two occurrences until the k-th occurrence is reached, we have 2 cases
- The first case is that there is only 1 more occurrence left, then the requested position is n places away from the last one remembered (4th column)
- Another case, if there are only 2 more occurrences left, then the requested position is (substring length + 1 -n) places away from the last one remembered (4th column), and this can be concluded by looking at the second column.
#include < iostream >
using namespace std;
int main()
{
using namespace std;
int main()
{
int n,k,pos,displ=0,num=0,appear=0;
cin>>n>>k;//n- number, k- number of occurrences of the number n
pos=0;
do
{
while(appear < k);
cout << pos << endl;
return 0;
}cin>>n>>k;//n- number, k- number of occurrences of the number n
pos=0;
do
{
num++;
/* until the number reaches n there is no occurrence */
/*displ is actually the length of the subarray. Eg for number 3, subarray
is 12321, so length is 5*/
if(num < n)
{
else if(num==n) /* starts counting */
{
else
{
}/* until the number reaches n there is no occurrence */
/*displ is actually the length of the subarray. Eg for number 3, subarray
is 12321, so length is 5*/
if(num < n)
{
if(num == 1)
{
else
{
pos=pos+displ;//position at the end of subarray
}{
displ += 1;//next displasment
}else
{
displ += 2;
}pos=pos+displ;//position at the end of subarray
else if(num==n) /* starts counting */
{
appear=1;/* The first appearance */
if(appear==k) /* case for n=1 */
{
displ+=2;//The length of subarray in the current cycle
pos=pos+displ;//New position
}if(appear==k) /* case for n=1 */
{
pos=pos+n;
break;
}break;
displ+=2;//The length of subarray in the current cycle
pos=pos+displ;//New position
else
{
if(appear < k-2) /*There are exactly 2 occurrences for each new subarray*/
{
else if(appear == k-2) /* two appearances remain */
{
else /* one more appearance remains */
{
}{
appear += 2;
displ += 2; /* the length of the substring is 2 more than the previous one */
pos=pos+displ; /* the position of the last digit is shifted by the length of the subarray */
}displ += 2; /* the length of the substring is 2 more than the previous one */
pos=pos+displ; /* the position of the last digit is shifted by the length of the subarray */
else if(appear == k-2) /* two appearances remain */
{
displ += 2;
pos=pos+displ; /* the position that would be at the end */
pos=pos+1-n; /* the second occurrence is n-1 away from the last */
break;
}pos=pos+displ; /* the position that would be at the end */
pos=pos+1-n; /* the second occurrence is n-1 away from the last */
break;
else /* one more appearance remains */
{
pos=pos + n;
break;
}break;
while(appear < k);
cout << pos << endl;
return 0;
National competition in informatics held in 2019
5. High students
Note: The assignment (6th grade) was taken from the Society of Mathematicians of Serbia: dms.rs/informatika-osnovne-skole/
The heights of all students of a school are known. Write a program that determines the tallest boy and the tallest girl in that school, determines who is taller and prints the difference in their heights.
Input
From the standard input, the number of students (5 ≤ 𝑛 ≤ 100) is entered, and then in each of the 𝑛 subsequent lines, data for one student. For each student, height (a whole number between 120 and 200) and gender (m for male and z for female) are entered, separated
one space. Assume that there is at least one boy and at least one girl.
Output
If the tallest girl is taller than the tallest boy, print z, a space, and then how much taller she is to standard output. If the tallest boy is taller than the tallest girl, print m, a space, and then how much taller he is to standard output. If they are the same height, print only "=".
Example
Input
5
152 z
174 m
165 z
172 m
170 z
Output
m 4
The heights of all students of a school are known. Write a program that determines the tallest boy and the tallest girl in that school, determines who is taller and prints the difference in their heights.
Input
From the standard input, the number of students (5 ≤ 𝑛 ≤ 100) is entered, and then in each of the 𝑛 subsequent lines, data for one student. For each student, height (a whole number between 120 and 200) and gender (m for male and z for female) are entered, separated
one space. Assume that there is at least one boy and at least one girl.
Output
If the tallest girl is taller than the tallest boy, print z, a space, and then how much taller she is to standard output. If the tallest boy is taller than the tallest girl, print m, a space, and then how much taller he is to standard output. If they are the same height, print only "=".
Example
Input
5
152 z
174 m
165 z
172 m
170 z
Output
m 4
Enter the number n and create a loop that has n repetitions. Then through the loop do the following:
- Enter data from one input line, height and gender. Use char variable for gender
- Check whether the gender is male or female. Determine the maximum height for men, and especially for women.
Compare the maximum heights determined previously and print the requested message
#include < iostream >
using namespace std;
int main()
{
using namespace std;
int main()
{
int n,m=0,f=0;
cin >> n;
for(int i=0; i
{
/*compare the highest male and the highest female height*/
if(m>f)
{
else if(m == f)
{
else
{
return 0;
}cin >> n;
for(int i=0; i
int h;/*person height*/
char g; /*gender*/
cin >> h;
cin >> g;
if(g=='m') /*it is checked whether the gender is male */
{
else if(g == 'f') /* if the gender is equal to female */
{
}char g; /*gender*/
cin >> h;
cin >> g;
if(g=='m') /*it is checked whether the gender is male */
{
/* The maximum height for men is determined */
if(h > m)
{
}if(h > m)
{
m=h;
}else if(g == 'f') /* if the gender is equal to female */
{
/*The maximum height for women is determined*/
if(h > f)
{
}if(h > f)
{
f=h;
}/*compare the highest male and the highest female height*/
if(m>f)
{
cout << "m " << (m-f) << endl;
}else if(m == f)
{
cout << "=" << endl;
}else
{
cout << "f " << (f-m) << endl;
}return 0;
6. Book
Note: The assignment (6th grade) was taken from the Society of Mathematicians of Serbia: dms.rs/informatika-osnovne-skole/
The length of 𝑛 chapters of a book is given by the sequence 𝑎. The element 𝑎0 is the number of pages for the first chapter, the element 𝑎1 for the second, and so on. It is necessary to divide the book into two parts, so that the total number of pages in those two parts are the least different. Division is done after one of the chapters. If there are two possible divisions with the same smallest difference, the division is made after the earlier of the two chapters (so that the first part is shorter). Write a program that determines after which chapter the division should be performed.
Input
The first line of standard input contains the natural number 𝑛 (1 < 𝑛 ≤ 50000). In the next 𝑛 lines there is one natural number (between 1 and 1000), the numbers represent the page numbers of each chapter.
Output
On the standard output, show in one line the sequential number of chapters (chapters are counted from zero) after which the book should be divided.
Example
Input
5
100
120
50
150
70
Output
1
When the division is made after chapter number 1 (that is the second chapter), then the first part of the book contains 220 and the second 270 pages, which gives the smallest possible difference of 50 pages.
If the division were to be made after chapter number 2 (that is the third chapter), the first part would contain 270 pages, and the second 220, which would also be a difference of 50. be shorter so the solution is 1 (division is made after chapter number 1).
The length of 𝑛 chapters of a book is given by the sequence 𝑎. The element 𝑎0 is the number of pages for the first chapter, the element 𝑎1 for the second, and so on. It is necessary to divide the book into two parts, so that the total number of pages in those two parts are the least different. Division is done after one of the chapters. If there are two possible divisions with the same smallest difference, the division is made after the earlier of the two chapters (so that the first part is shorter). Write a program that determines after which chapter the division should be performed.
Input
The first line of standard input contains the natural number 𝑛 (1 < 𝑛 ≤ 50000). In the next 𝑛 lines there is one natural number (between 1 and 1000), the numbers represent the page numbers of each chapter.
Output
On the standard output, show in one line the sequential number of chapters (chapters are counted from zero) after which the book should be divided.
Example
Input
5
100
120
50
150
70
Output
1
When the division is made after chapter number 1 (that is the second chapter), then the first part of the book contains 220 and the second 270 pages, which gives the smallest possible difference of 50 pages.
If the division were to be made after chapter number 2 (that is the third chapter), the first part would contain 270 pages, and the second 220, which would also be a difference of 50. be shorter so the solution is 1 (division is made after chapter number 1).
Task analysis
If we were to mark the chapters with indexes from 0 to n, then we could see 4 arrays. The first is the number of books per chapter. It is normally an array that is entered. The second array is the number of pages, which is obtained by adding the number of pages of all chapters, up to the observed one, on the left. The third array represents the sum of the pages of all the remaining chapters, from the current chapter to the end of the book, i.e. to the right of the current chapter. We get the fourth array if we subtract the elements of the 2nd array from the 3rd. Let's look at it in the following table:
| 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 100 | 120 | 50 | 150 | 70 |
| 100 | 220 | 270 | 420 | 490 |
| 390 | 270 | 220 | 70 | 0 |
| 290 | 50 | -50 | -350 | -490 |
Therefore, it is necessary to find the smallest difference in the number of books to the right and left of the end of the current chapter, which practically means the smallest number by absolute value in the 4th series. It should also be noted that the smallest value can only be the first to the left of the transition from positive to negative values, or the first to the right. later those values increase in absolute value. So it is the value in the column with index 1 and 2. Since they are equal in absolute value, the value on the left is taken.
Solve the task according to the following algorithm:
- Enter the chapter number
- Using a loop (for) enter an array whose elements are the number of pages per chapter, in the example given in the table, these are the numbers in the first row.
- Form an array from the sum of the entered elements of the previous array on the left
- Form an array formed by the sum of the loaded elements of the previous array on the right. Change the column index from last to first. These are the numbers in the 3rd row.
- Create the 4th row, as the difference of the 3rd and 2nd row elements
- In the same cycle, look for the minimum value of the difference
- When you reach an element that has a negative difference, stop the cycle
#include < iostream >
using namespace std;
int main()
{
using namespace std;
int main()
{
int n,s=0,minR;
cin >> n;
int a[n],l[n],r[n];
for(int i = 0; i < n; i++)
{
minR=s; /* The largest possible difference is equal to the sum of all elements*/
s=0;
for(int i=n-1; i>=0; i--)
{
int dif;
int ind=0;
for(int i=0; i < n; i++)
{
cout << ind << endl;
return 0;
}cin >> n;
int a[n],l[n],r[n];
for(int i = 0; i < n; i++)
{
cin >> a[i];
s=s+a[i];
l[i]=s;
}s=s+a[i];
l[i]=s;
minR=s; /* The largest possible difference is equal to the sum of all elements*/
s=0;
for(int i=n-1; i>=0; i--)
{
r[i]=s;
s=s+a[i];
}s=s+a[i];
int dif;
int ind=0;
for(int i=0; i < n; i++)
{
dif=r[i]-l[i]; /* the difference between the left and right parts of the book in relation to the end of the current chapter */
/* each subsequent difference will be greater */
if(dif < 0)
{
/* if a smaller difference is encountered, it is remembered as minimal */
if(dif < minR)
{
}/* each subsequent difference will be greater */
if(dif < 0)
{
minR=(abs(dif) < minR) ? abs(dif):minR;
ind=(abs(dif)
break;
}ind=(abs(dif)
/* if a smaller difference is encountered, it is remembered as minimal */
if(dif < minR)
{
minR=dif;
}cout << ind << endl;
return 0;
7. Growing numbers
Note: The assignment (6th grade) was taken from the Society of Mathematicians of Serbia: dms.rs/informatika-osnovne-skole/
Write a program that finds among the entered numbers those whose digits are strictly increasing, looking from the digit of the highest weight (the first digit from the left).
Write a program that finds among the entered numbers those whose digits are strictly increasing, looking from the digit of the highest weight (the first digit from the left).
Input
The number n (1 ≤ n ≤ 5000) is loaded from the standard input, followed by n natural numbers greater than or equal to 10 and less than or equal to 109
, each in a separate row.
Output
Print the requested numbers with increasing digits, each in a separate line, to the standard output.
Example
Input
3
123
222
321
output
123
Print the requested numbers with increasing digits, each in a separate line, to the standard output.
Example
Input
3
123
222
321
output
123
Solve the task according to the following algorithm:
- Enter an integer
- Determine how many digits there are. This can be done either with a while loop or by using the log10 function from the cmath header. See a more detailed explanation on the page Preparation for district competitions
- Open loop, preferably do-while
- Inside loop:
- Highlight the number on the left
- Shorten the number by that digit by dividing by the power of 10 whose exponent is 1 less than the number of digits of the rest of the number. For example. If the number is 12345, the digit 1 should be extracted, then divide the number by 104, so that the number in the next cycle will be 2345
- Check if the current digit is in ascending order with the previous digit
- The current digit will be the previous one in the next cycle
- If it is the first cycle, save the current digit as the previous one for the next cycle and immediately move to the next cycle
- If the previous and current digits are not in ascending order, state that the order is not ascending by setting the logical variable to false and terminate the cycles
- If the boolean variable that checks if the ascending order is true, print the number
- To change the number being examined, use a loop so that the second loop that separates the digits is nested
#include < iostream >
#include< cmath >
using namespace std;
int main()
{
#include< cmath >
using namespace std;
int main()
{
int n,numDig=0;
cin >> n;
int number[n];
//Entering
for(int i=0; i < n; i++)
{
//analysis
for(int i=0; i < n; i++)
{
return 0;
}cin >> n;
int number[n];
//Entering
for(int i=0; i < n; i++)
{
cin >> number[i];
}//analysis
for(int i=0; i < n; i++)
{
numDig=(int)log10(number[i])+1; /* Calculating the number of digits */
/*examines whether it is in ascending order*/
bool growing=true; /* is assumed to be in ascending order */
int d=(int)pow(10,numDig-1); /* initial divisor */
int p,j=0; /* previous digit, control variable for do-while loop (shift by digits) */
int a=number[i]; /* the number from which the digits will be removed on the left, initially equal to the entered number */
do
{
if(growing)
{
}/*examines whether it is in ascending order*/
bool growing=true; /* is assumed to be in ascending order */
int d=(int)pow(10,numDig-1); /* initial divisor */
int p,j=0; /* previous digit, control variable for do-while loop (shift by digits) */
int a=number[i]; /* the number from which the digits will be removed on the left, initially equal to the entered number */
do
{
int c=a/d; /* the figure on the left */
a=a % d; /* subtracts the digit from the left side with the current number a. Eg From 123, the number becomes 23 */
d /= 10; /* d=d/10 */
if(j==0) /* first cycle */
{
/* checks ascending order */
if(c <= p)
{
p=c; /* the current digit becomes a transition for the next cycle */
j++; /* increases the number of cycles by 1 */
}
while(d >= 1);a=a % d; /* subtracts the digit from the left side with the current number a. Eg From 123, the number becomes 23 */
d /= 10; /* d=d/10 */
if(j==0) /* first cycle */
{
p=c;
j++;
continue; /* transition to the next cycle */
}j++;
continue; /* transition to the next cycle */
/* checks ascending order */
if(c <= p)
{
growing=false;
break;
}break;
p=c; /* the current digit becomes a transition for the next cycle */
j++; /* increases the number of cycles by 1 */
if(growing)
{
cout << number[i] << endl;
}return 0;
8. Height difference
Note: The task (6th grade) was taken from the Society of Mathematicians of Serbia: dms.rs/informatika-osnovne-skole/
In a school, actors are chosen for a school play in which the characters they play have a big difference in height. Write a program that determines how many ways we can choose two actors from the class so that their height difference is equal to a given number 𝑟.
Input
From the standard input, a positive natural number 𝑟 (1 ≤ 𝑟 ≤ 1000) is entered first, in
in the next row number of students 𝑛 (1 ≤ 𝑛 ≤ 50000), and after that in the next 𝑛 rows
the height of each student (a number between 1 and 100000).
Output
Print the number of pairs that can be formed to the standard output.
Example 1
Input
10
5
150
160
165
170
175
Output
3
It is possible to make pairs from the first and second child (150, 160), from the second and fourth child (160, 170) and from the third and fifth child (165, 175).
Example 2
Input
23
5
157
180
157
162
134
Output
4
It is possible to make pairs from the first and second child (157, 180), from the fifth and first (134, 157), from the second and third (157, 180) and from the fifth and third child (134, 157).
Note
In 20 out of 25 test examples, all children will be different heights.
In a school, actors are chosen for a school play in which the characters they play have a big difference in height. Write a program that determines how many ways we can choose two actors from the class so that their height difference is equal to a given number 𝑟.
Input
From the standard input, a positive natural number 𝑟 (1 ≤ 𝑟 ≤ 1000) is entered first, in
in the next row number of students 𝑛 (1 ≤ 𝑛 ≤ 50000), and after that in the next 𝑛 rows
the height of each student (a number between 1 and 100000).
Output
Print the number of pairs that can be formed to the standard output.
Example 1
Input
10
5
150
160
165
170
175
Output
3
It is possible to make pairs from the first and second child (150, 160), from the second and fourth child (160, 170) and from the third and fifth child (165, 175).
Example 2
Input
23
5
157
180
157
162
134
Output
4
It is possible to make pairs from the first and second child (157, 180), from the fifth and first (134, 157), from the second and third (157, 180) and from the fifth and third child (134, 157).
Note
In 20 out of 25 test examples, all children will be different heights.
Task analysis
If the heights are loaded as an array, it should be sorted first. In order to make all combinations of pairs and compare the height difference of those pairs with the given one, on the one hand, you need to change the first element of the sequence, i.e. the height of the first child within the pair, and on the other hand, for the fixed value of the first height, change the second value in the pair. Two loops can be used for this, one nested inside the other. Both loops can change values linearly, from beginning to end, or one linearly, while the other Binary Search, which would be more efficient.
Solve the task according to the following algorithm:
- Enter two integers, the required difference and the number of children.
- Enter a range of children's heights
- Open two loops, one nested inside the other
- Sort the array in ascending order.
- Form the height difference in the loop and compare it with the given one.
- If the difference is equal to the given one, increase the required number of pairs by 1
- Iteratively, through the inner loop, change the second height within pairs of heights until the height difference is either not found or until a greater difference than the given one is reached, and then break the inner loop, because each subsequent difference would be even greater
- After exiting the loop, print the requested number of pairs
#include < iostream >
#include< algorithm >
using namespace std;
int main()
{
#include< algorithm >
using namespace std;
int main()
{
int r,n,b=0;
cin >> r >> n;
int h[n]; //An array of heights
//ucitavanje
for(int i=0; i < n; i++)
{
/*Sorting an array of heights*/
sort(v,v+n);
/*Formation of different height pairs and examination */
for(int i=0; i < n-1; i++)
{
cout << b << endl;
return 0;
}cin >> r >> n;
int h[n]; //An array of heights
//ucitavanje
for(int i=0; i < n; i++)
{
cin >> h[i];
}/*Sorting an array of heights*/
sort(v,v+n);
/*Formation of different height pairs and examination */
for(int i=0; i < n-1; i++)
{
for(int j=i+1; j < n; j++)
{
}{
int diff=h[j]-h[i];/* height difference */
if(diff==r) /* If the height difference is equal to the given one */
{
else if(diff> r ) /*If the difference is greater than the default, the other changes are interrupted
height in a pair, because each subsequent difference is greater*/
{
}if(diff==r) /* If the height difference is equal to the given one */
{
b++; /* Increases the number of matches found by 1 */
}else if(diff> r ) /*If the difference is greater than the default, the other changes are interrupted
height in a pair, because each subsequent difference is greater*/
{
break;
}cout << b << endl;
return 0;
A more efficient solution with binary search
Solve the task according to the following algorithm:
- Enter two integers, the required difference and the number of children.
- Enter a range of children's heights
- Open two loops, one nested inside the other
- Sort the array in ascending order.
- Form the height difference in the loop and compare it with the given one.
- If the difference is equal to the given one, increase the required number of pairs by 1
- The inner loop changes the second height by looking for the one whose difference with the first height is equal to the given one. Search using the binary search algorithm. Therefore, change the far left and far right positions of the observed array.
This subarray is initially equal to the whole array, which means that the far left and far right positions are initially the bottom positions of the whole array.
Inside the cycle, the middle position is first determined .Then the difference of the array element at that, middle position and the height of the first child within the current pair is found. If that difference is exactly the one given, the number of found pairs increases by 1.
It should be checked if there are other values with the same difference, e.g. if there are more children with the same height.
If not, then further check whether the requested difference is in the left or right half of the current subarray and accordingly move the rightmost or leftmost position of the subarray in the next cycle. - After exiting the loop, print the requested number of pairs
#include < iostream >
#include< algorithm >
using namespace std;
int main()
{
#include< algorithm >
using namespace std;
int main()
{
int dif,n,b=0;
cin >> dif >> n;//dif-the difference that is sought,n-number of children
int h[n]; //the array of heights
//ucitavanje
for(int i=0; i < n; i++)
{
/*Sorting an array of heights*/
sort(h,h+n);
/*Formiranje različitih parova visina i ispitivanje */
for(int i=0; i < n-1; i++)
{
cout << b << endl;
return 0;
}cin >> dif >> n;//dif-the difference that is sought,n-number of children
int h[n]; //the array of heights
//ucitavanje
for(int i=0; i < n; i++)
{
cin >> h[i];
}/*Sorting an array of heights*/
sort(h,h+n);
/*Formiranje različitih parova visina i ispitivanje */
for(int i=0; i < n-1; i++)
{
int l=i+1,r=n-1; /* the search array is from position i+1 to n-1, l-left,r-right */
while(l <= r) /* The cycle continues as long as the left position is less than or equal to the right position */
{
}while(l <= r) /* The cycle continues as long as the left position is less than or equal to the right position */
{
int mid=(l+r)/2; /* mean interval position[l,r] */
int hDiff=h[mid]-h[i]; /* height difference */
/* If the difference is equal to diff, a new partition is found whose height difference is equal to the given one */
if(hDiff == dif)
{
else if(dif
{
else if(dif > hDiff) /* If the expected difference is greater than the actual difference, the expected value is in the right half */
{
}int hDiff=h[mid]-h[i]; /* height difference */
/* If the difference is equal to diff, a new partition is found whose height difference is equal to the given one */
if(hDiff == dif)
{
b++; /* the number of pairs is increased by 1 */
int k=mid+1;
while(h[k]==h[mid])
{
k=mid-1;
while(h[k]==h[mid])
{
break;
}int k=mid+1;
while(h[k]==h[mid])
{
b++;
k++;
}k++;
k=mid-1;
while(h[k]==h[mid])
{
b++;
k--;
}k--;
break;
else if(dif
r=mid-1; /*the right limit for a new search is the first position to the left of the mean*/
}else if(dif > hDiff) /* If the expected difference is greater than the actual difference, the expected value is in the right half */
{
l=mid+1; /* the left limit for a new search is the first position to the right of the mean */
}cout << b << endl;
return 0;