[NOIP2015 Popularization Group] Golden Coins
Background to the topic
NOIP2015 Popular Group T1
Title Description
The king gave gold coins as wages to loyal knights. On the first day, the knight receives one gold coin; on the next two days (the second and third days), he receives two gold coins per day; on the next three days (the fourth, fifth, and sixth days), he receives three gold coins per day; and on the next four days (the seventh, eighth, ninth, and tenth days), he receives four gold coins per day ......; and this pattern of payrolls continues in this manner: when After receiving n gold coins per day for n consecutive days, the knight will receive n+1 gold coins per day for n+1 consecutive days.
Calculate how many gold coins the knight has earned in the first k days.
input format
A positive integer k, denoting the number of days for which gold coins are issued.
output format
A positive integer, the number of gold coins received by the knight.
Sample #1
Sample Input #1
6
Sample Output #1
14
Sample #2
Sample Input #2
1000
Sample Output #2
29820
draw attention to sth.
[Sample 1 Description
The knight receives one gold coin on the first day; two gold coins per day on the second and third days; and three gold coins per day on the fourth, fifth and sixth days. Therefore, the total number of coins received is 1+2+2+3+3+3=14 coins.
For 100% of the data, 1<k<10^4.
This is a question that we can do a simulation of, obviously, if an array is used to store the gold coins of day k, the values of this array are 1,2,2,3,3,3,3,4,4,4,4,4 .....
If the total number of days is n, we can use a double loop to assign values to the array, the outer loop condition for the length of the array is less than n, and the inner loop k times (k is initialized to 1), so that we can achieve the above 1,2,2,3,3,3 ..... This effect
Finally, traversing the array again and accumulating the elements of the array, we get the answer
The C++ code is as follows:
#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> result;
int k = 1;
while (()<n) {
for (int i = 1; i <= k; i++) result.push_back(k);
k++;
}
int sum = 0;
for (int i = 0; i < n; i++) {
sum += result[i];
}
cout << sum;
return 0;
}