Problem Description

A monarch rewards a loyal knight with gold coins based on a unique progressive payment system. The scheme is as follows:

• On the first day, the knight receives 1 gold coin.
• For the subsequent two days (Day 2 and Day 3), the knight receives 2 gold coins per day.
• Following that, for the next three days (Day 4, Day 5, and Day 6), the knight receives 3 gold coins per day.
• This pattern continues: after receiving N gold coins per day for N consecutive days, the knight will then receive N+1 gold coins per day for N+1 consecutive days.

The challenge is to calculate the total number of gold coins the knight has accumulated after exactly K days.

Input Format

A single positive integer K, representing the total number of days for which to calculate the gold accumulation (1 ≤ K ≤ 10000).

Output Format

A single positive integer, representing the total sum of gold coins received by the knight.

Example 1

Input:

6

Output:

14

Explanation:

Day 1: 1 coin

Day 2: 2 coins

Day 3: 2 coins

Day 4: 3 coins

Day 5: 3 coins

Day 6: 3 coins

Total = 1 + 2 + 2 + 3 + 3 + 3 = 14 coins.

Example 2

Input:

1000

Output:

29820

Constraints

1 ≤ K ≤ 10000

Solution Approach 1: Day-by-Day Simulation

This approach direct simulates the process described. We iterate through each day from 1 to K, accumulating gold coins. We need to keep track of the current payment amount per day and how many days remain in the current payment phase. Once a phase (e.g., N coins for N days) is completed, we transition to the next phase (N+1 coins for N+1 days).

Algorithm:

1. Initialize accumulatedGold = 0.
2. Initialize currentDailyRate = 1 (starting with 1 coin per day).
3. Initialize daysInCurrentPhase = 1 (this phase will last 1 day).
4. Loop from day = 0 to K-1:
   • Add currentDailyRate to accumulatedGold.
   • Decrement daysInCurrentPhase.
   • If daysInCurrentPhase becomes 0, it means the current paymant phase has ended:
     • Increment currentDailyRate for the next phase.
     • Set daysInCurrentPhase to the new currentDailyRate (as the next phase will last currentDailyRate days).
5. Output accumulatedGold.

This method has a time complexity of O(K) as it iterates K times.

C++ Implementation 1

#include <iostream>

   int main() {
       std::ios_base::sync_with_stdio(false);
       std::cin.tie(NULL);

       int totalDays;
       std::cin >> totalDays;

       long long totalGoldCollected = 0;
       int currentPayoutPerDay = 1;
       int daysRemainingForCurrentPayout = 1;

       for (int dayCounter = 0; dayCounter < totalDays; ++dayCounter) {
           totalGoldCollected += currentPayoutPerDay;
           daysRemainingForCurrentPayout--;

           if (daysRemainingForCurrentPayout == 0) {
               currentPayoutPerDay++;
               daysRemainingForCurrentPayout = currentPayoutPerDay;
           }
       }

       std::cout << totalGoldCollected << std::endl;
       return 0;
   }
   

Solution Approach 2: Block-Based Calculation

Instead of iterating day by day, we can calculate the total gold for entire "blocks" or "phases" of payment. A phase where the knight receives M coins per day for M days will contribute M * M gold coins. We can sum these full block contributions and then handle any remaining days at the end.

Algorithm:

1. Initialize totalCoins = 0.
2. Initialize daysAccumulated = 0 (total days processed so far).
3. Initialize dailyPaymentRate = 1 (current rate, also implies the duration of the current phase).
4. Loop while daysAccumulated + dailyPaymentRate is less than or equal to K:
   • Add dailyPaymentRate * dailyPaymentRate to totalCoins (total coins for this complete phase).
   • Add dailyPaymentRate to daysAccumulated.
   • Increment dailyPaymentRate for the next phase.
5. After the loop, if daysAccumulated is still less than K, it means there are some remaining days that constitute a partial phase:
   • Calculate remainingDays = K - daysAccumulated.
   • Add dailyPaymentRate * remainingDays to totalCoins.
6. Output totalCoins.

This approach is more efficient, with a time complexity of O(√K) because the dailyPaymentRate increases, and its sum of dailyPaymentRate determines daysAccumulated, so dailyPaymentRate goes up to aproximately sqrt(2K). For K=10000, sqrt(20000) is around 141 iterations, which is much faster than 10000 iterations.

C++ Implementation 2

#include <iostream>

   int main() {
       std::ios_base::sync_with_stdio(false);
       std::cin.tie(NULL);

       int targetTotalDays;
       std::cin >> targetTotalDays;

       long long finalGoldSum = 0;
       int daysProcessed = 0;
       int currentRateLevel = 1; // Represents the coins per day AND the duration of the phase

       // Accumulate gold for full payment blocks
       while (daysProcessed + currentRateLevel <= targetTotalDays) {
           finalGoldSum += (long long)currentRateLevel * currentRateLevel;
           daysProcessed += currentRateLevel;
           currentRateLevel++;
       }

       // Handle any remaining days that don't form a full block
       if (daysProcessed < targetTotalDays) {
           int leftoverDays = targetTotalDays - daysProcessed;
           finalGoldSum += (long long)currentRateLevel * leftoverDays;
       }

       std::cout << finalGoldSum << std::endl;
       return 0;
   }