The Famous Gauss You must know about Gauss, the famous mathematician. Back in late 1700’s, he was at elementary school. Gauss was asked to find the sum of the numbers from 1 to 100. The question was assigned as “busy work” by the teacher. He amazed his teacher with how quickly he found the sum of the integers from 1 to 100 to be 5050. Gauss recognized he had fifty pairs of numbers when he added the first and last number in the series, the second and second-last number in the series, and so on. For example: (1 + 100), (2 + 99), (3 + 98), ..., (50 + 51). Each pair has a sum of 101 and there are 50 pairs. History repeats itself. Jojo’s teacher assign a “busy work” to the students. The teacher believes that there will be no shortcut to finish this task in a minute. The teacher gives N integers A1, A2, ..., AN to the students. The teacher also gives Q questions. Each question contains two integers L and R asking the sum of all Ai where L <= Ai <= R. As a good friend of Jojo, help Jojo to amaze his teacher. Answer all the questions! Format Input There are T testcases. Every testcase consists of a line with an integers N followed by a line consists of N integers A1, A2, ..., AN as described above. Followed by a line consists of an integers Q and Q lines which each consists of two integers L and R as described above. Format Output Output T testcases with format “Case #X:”, where X indicates the testcase number and then followed by Q lines which each consists of an integers indicates the answer of each question. Constraints • 1 ≤ T ≤ 3 • 1 ≤ N, Q ≤ 30000 • 1 ≤ Ai, L, R ≤ 109 Sample Input (standard input) 3 6 3 2 1 3 5 1 3 3 3 2 3 1 5 5 4 5 6 7 8 7 4 4 4 5 4 6 4 7 4 8 4 9 3 8 5 11 12 13 14 15 3 1 10 16 20 1 20 Sample Output (standard output) Case #1: 6 8 15 Case #2: 4 9 15 22 30 30 30 Case #3: 0 0 65
The Famous Gauss
You must know about Gauss, the famous mathematician. Back in late 1700’s, he was at elementary school. Gauss was asked to find the sum of the numbers from 1 to 100. The question was assigned as “busy work” by the teacher. He amazed his teacher with how quickly he found the sum of the integers from 1 to 100 to be 5050. Gauss recognized he had fifty pairs of numbers when he added the first and last number in the series, the second and second-last number in the series, and so on. For example:
(1 + 100), (2 + 99), (3 + 98), ..., (50 + 51). Each pair has a sum of 101 and there are 50 pairs. History repeats itself. Jojo’s teacher assign a “busy work” to the students. The teacher believes that there will be no shortcut to finish this task in a minute. The teacher gives N integers A1, A2, ..., AN to the students. The teacher also gives Q questions. Each question contains two integers L and R asking the sum of all
Format Input
There are T testcases. Every testcase consists of a line with an integers N followed by a line consists of N integers A1, A2, ..., AN as described above. Followed by a line consists of an integers Q and Q lines which each consists of two integers L and R as described above.
Format Output
Output T testcases with format “Case #X:”, where X indicates the testcase number and then followed by Q lines which each consists of an integers indicates the answer of each question.
Constraints
• 1 ≤ T ≤ 3
• 1 ≤ N, Q ≤ 30000
• 1 ≤ Ai, L, R ≤ 109
Sample Input (standard input)
3
6
3 2 1 3 5 1
3
3 3
2 3
1 5
5
4 5 6 7 8
7
4 4
4 5
4 6
4 7
4 8
4 9
3 8
5
11 12 13 14 15
3
1 10
16 20
1 20
Sample Output (standard output)
Case #1:
6
8
15
Case #2:
4
9
15
22
30
30
30
Case #3:
0
0
65
Please use binary search and C language. Thx.
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 3 images
