preface

Blue Bridge Cup group B 2017 provincial competition blank filling question (C + +)

1, Title Description

A batch of precious metal raw materials are neatly stacked in the high-tech laboratory of Planet X.

The shape and size of each metal raw material are exactly the same, but the weight is different. Metal materials are strictly stacked into pyramids.

                             7 
                            5 8 
                           7 8 8 
                          9 2 7 2 
                         8 1 4 9 1 
                        8 1 8 8 4 1 
                       7 9 6 1 4 5 4 
                      5 6 5 5 6 9 5 6 
                     5 5 4 7 9 3 5 5 1 
                    7 5 7 9 7 4 7 3 3 1 
                   4 6 4 5 5 8 8 3 2 4 3 
                  1 1 3 3 1 6 6 5 5 4 4 2 
                 9 9 9 2 1 9 1 9 2 9 5 7 9 
                4 3 3 7 7 9 3 6 1 3 8 8 3 7 
               3 6 8 1 5 3 9 5 8 3 8 1 8 3 3 
              8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9 
             8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4 
            2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9 
           7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6 
          9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3 
         5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9 
        6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4 
       2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4 
      7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6 
     1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3 
    2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8 
   7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9 
  7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6 
 5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1 
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X 

The number represents the weight of the metal block (larger unit of measurement). XX on the bottom layer represents 3030 extremely high-precision electronic scales.

It is assumed that the weight of each raw material falls on the two metal blocks below very accurately. Finally, the weight of all metal blocks falls on the bottom electronic scale strictly and accurately.

The unit of measurement of the electronic scale is very small, so the number displayed is very large.

The staff found that the indication of the electronic scale with the smallest reading was 20864582312086458231

Please figure out: what is the indication of the electronic scale with the largest reading?

Operating limits

• Maximum running time: 1s
• Maximum operating memory: 128M

2, Train of thought

This topic can store these values by declaring a 30 * 30 array, and then accumulate the value of the array line by line from top to bottom to get the value on the final scale. Specifically, each item in each row is the accumulation of half of the left and right items in the previous row, which is mapped to the array, i-1 and i. if the column number of the current item is i, the items at both ends of the ending can be processed separately.

In addition, a small suggestion is that it is not recommended to declare an array from 0, including some topics in graph theory. When an array needs to be used, it is recommended to start with 1. This is not only convenient to traverse, but also not easy to make mistakes. It is a small skill.

The final answer is: 72665192664

3, Program code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	double a[100][100];
	for(int i=1;i<=29;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=2;i<=30;i++)
	{
		for(int j=1;j<=i;j++)
		{
			if(j==1) //Process the first element separately 
			{
				a[i][j]+=a[i-1][j]/2;   
			}
			else if(j==i)  //Process the last element separately
			{
				a[i][j]+=a[i-1][i-1]/2;
			} 
			else
			{
				a[i][j]+=a[i-1][j-1]/2+a[i-1][j]/2;
			}
		}
	}
	double max=0;
	double min=100000;
	for(int i=1;i<=30;i++)
	{
		if(max<a[30][i])
		{
			max=a[30][i];
		}
		if(min>a[30][i])
		{
			min=a[30][i];
		}
	}
	cout<<fixed<<setprecision(1)<<2086458231/min*max<<endl;  //Keep one decimal place 
	return 0;
}