12. TOTALS AFTER DIVISION - SOLUTION
Note: 12th tasks from the website: Qualifications for district competitions
Instruction:
The task can be solved by first loading the array, then looping from the last to the starting position, determining the number of odd occurrences in the array to the right of that position and writing it to the auxiliary array.
Then, in another pass through the sequence, this time from left to right, the number of even numbers to the left and right of the current position, as well as the number of odd numbers to the left and right of the current position, are determined. To determine the number of even and odd numbers on the right, the written values in the auxiliary sequence are used.
The total number of pairs is the sum of the product of the even and odd values to the left and right of the current "i" position. For example. if we mark the requested value with num, and the auxiliary array with numOdd, the total number of elements with n, then num is calculated:
Then, in another pass through the sequence, this time from left to right, the number of even numbers to the left and right of the current position, as well as the number of odd numbers to the left and right of the current position, are determined. To determine the number of even and odd numbers on the right, the written values in the auxiliary sequence are used.
The total number of pairs is the sum of the product of the even and odd values to the left and right of the current "i" position. For example. if we mark the requested value with num, and the auxiliary array with numOdd, the total number of elements with n, then num is calculated:
numberOfOddRight=numOdd[i];
numberOfEvenRight=n-numOdd[i];
num= numberOfEvenLeft*numberOfOddRight + numberOfOddLeft*numberOfOddRight;
This follows from the fact that if the number is odd in the left sequence, it must be added to the odd number from the right sequence to get an even sum, and vice versa, if the number is even within the left sequence, it must be added to the even number from the right part.
When b is calculated it is compared to the current maximum and if it is higher that value becomes the maximum. Thus, by moving the i-th position that divides the sequence, to the right, to the end, the largest even sum of pairs will be obtained.
Solution:
#include < iostream >
using namespace std;
int main()
{
using namespace std;
int main()
{
int n;
cin >> n;
int a[n];
int numOdd[n];
int odd=0;
for(int i = 0;i < n;i++)
{
numOdd[n-1]=0;//number of odd ones to the right of position n-1
for(int i = n-1; i > 0; i--)
{
int oddL=0,num=0,eventRight=0,evenLeft=0;
int maxEven=0;
for(int i = 0;i < n;i++){
cout << maxEven << endl;
return 0;
}
cin >> n;
int a[n];
int numOdd[n];
int odd=0;
for(int i = 0;i < n;i++)
{
cin >> a[i];
}numOdd[n-1]=0;//number of odd ones to the right of position n-1
for(int i = n-1; i > 0; i--)
{
if(a[i] % 2 != 0){
if(i > 0){
}
odd++;
}if(i > 0){
numOdd[i-1]=odd;//the odd number to the right of the position i-1
}int oddL=0,num=0,eventRight=0,evenLeft=0;
int maxEven=0;
for(int i = 0;i < n;i++){
evenRight=n-(i+1)-numOdd[i];//the even number on the right
if(a[i] % 2 != 0) //the current number is odd
{
else //the current number is even
{
num=(evenLeft*evenRight)+(oddL*numLeft[i]); //the number of pairs if the array were to be split at the current position
if(num > maxEven)
{
}if(a[i] % 2 != 0) //the current number is odd
{
oddL++;
}else //the current number is even
{
evenLeft=i+1-oddL; //the number of even numbers on the left is obtained when
//the number of odd numbers on the left is subtracted from the total number of numbers on the left (i+1).
}//the number of odd numbers on the left is subtracted from the total number of numbers on the left (i+1).
num=(evenLeft*evenRight)+(oddL*numLeft[i]); //the number of pairs if the array were to be split at the current position
if(num > maxEven)
{
maxEven=num;
}cout << maxEven << endl;
return 0;
Return to the web page Preparation for district competitions