ZeroJudge C164: Golden Coins

The king pays loyal knights in gold coins. On the first day, a knight receives one coin; then, for the next two days (the second and third days), they receive two coins each day. This pattern continues, with the knight receiving one additional coin each day for the following consecutive days, forming an increasing sequence. This payment scheme persists: after receiving N coins for N consecutive days, the knight will receive N+1 coins for the next consecutive N+1 days.

Please calculate the total amount of gold coins the knight has earned in the previous K days.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The input file consists of a single line containing a positive integer K, representing the number of days for which gold coins will be awarded.The output file consists of a single line containing a positive integer, representing the total number of gold coins received by the knight.
614
100029820

Thought Process

Record daily gold coin amounts: Store the daily gold coin amounts in a data structure (e.g., array, list).
Outer loop (0 to 1,000,000):
Initialize count: Declare a variable count and set its initial value to 1. This represents the current amount of gold coins to be distributed. Inner loop (0 to count-1):
Push back count: Add the current value of count to a Vector (an ordered collection of elements). This represents the gold coins distributed on a specific day.
Update count and index:
Increment count: After the inner loop, increment count by 1. This increases the amount of gold coins to be distributed for subsequent days. Update index: Increment the outer loop index (i) by count. This ensures that the inner loop iterates over the correct number of elements.

Iterate through Vector:
For loop: Execute a for loop from 0 to K-1, where K is the number of days for which gold coins were awarded.
Initialize sum variable:
Declare ans: Declare a variable named ans and initialize it to 0. This variable will store the cumulative sum of gold coins.
Accumulate gold coins:
Add Vector element: Within the for loop, add the ith element of the previously declared Vector to the value of ans. This effectively sums up the gold coins for each day.

Sample Code-ZeroJudge C164: Golden Coins

#include <iostream>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, count = 1, ans = 0;
    cin >> N;
    vector<int>num;
    for (int i = 0; i<1000000; i++) {
        for (int j = 0; j<count; j++) num.push_back(count);
        i += count;
        count++;
    }
    for (int i = 0; i<N; i++) ans += num[i];
    cout << ans << "\n";
}

//ZeroJudge C164
//Dr. SeanXD

Comments