PAT Advanced 1104 Sum Of Number Segments

Overview

PAT advanced 1104 Sum of Number Segments can be solved by using formula i * a[i] * (N - i + 1) where i is from 1 to N to calculate the sum.

PAT Advenced 1104 Sum of Number Segments Problem

Given a sequence of positive numbers, a segment is defined to be a consecutive subsequence. For example, given the sequence {0.1, 0.2, 0.3, 0.4}, we have 10 segments: (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4).

Now given a sequence, you are supposed to find the sum of all the numbers in all the segments. For the previous example, the sum of all the 10 segments is 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N, the size of the sequence which is no more than 105. The next line contains N positive numbers in the sequence, each no more than 1.0, separated by a space.

Output Specification:

For each test case, print in one line the sum of all the numbers in all the segments, accurate up to 2 decimal places.

Sample Input:

4
0.1 0.2 0.3 0.4 

Sample Output:

5.00

PAT Advenced 1104 Sum of Number Segments Algorithm

Following the description of the problem, we can find the pattern and the formula to calculate the sum by listing the segments of small number n, and we know the final sum equals

SUM_OVER{i x a[i] x (N - i + 1)} where i = 1, 2..., N

The following C++ code is accepted by PAT OJ to solve this 1104 Sum of Number Segments problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>

int main() {
	int n;
	double a;
	double sum = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%lf", &a);
		int j = i + 1;
		sum += j * a * (n - j + 1);
	}
	printf("%0.2f", sum);
	return 0;
}

Summary

I gave the formula: SUM_OVER{i x a[i] x (N - i + 1)} where i = 1, 2…, N to calculate the sum of number segments, this is online linear time algorithm.

Written on June 19, 2016