Brainstorming Quiz - Day 2 Solution

The approach to solving this problem involves a combination of mathematical reasoning and iterative computation using the Fibonacci sequence. Here's a step-by-step breakdown of the approach:

Answer: 148

---

1. Understanding the Ticket Distribution:

• Odd-positioned people (1st, 3rd, 5th, etc.) pay Rs 1 for their tickets.
• Even-positioned people (2nd, 4th, 6th, etc.) get tickets for free.
• There are 50 paid tickets available, meaning a maximum of 50 odd-positioned individuals pay for their tickets.

2. Calculating Total Collected Amount:

• The total amount collected is Rs 20,365,011,122.
• A part of this amount comes from the 50 paid tickets, each contributing Rs 1. Therefore, the total collected from paid tickets is Rs 50.
• The remaining amount (Rs 20,365,011,072) is collected through fines.

3. Fines Based on Fibonacci Sequence:

• The fine for each subsequent person is calculated based on the Fibonacci sequence:
  • The 0th person (the first in line) has a fine of Rs 0.
  • The 1st person (second in line) has a fine of Rs 1.
  • The 2nd person (third in line) has a fine of Rs 1.
  • The 3rd person (fourth in line) has a fine of Rs 2, and so on.
• The fine amount for each person follows the Fibonacci pattern, where each new fine is the sum of the previous two fines.

4. Iterative Process:

• Start by calculating the total amount collected from the paid tickets.
• Calculate the remaining amount (the fine amount) that needs to be collected to reach the total amount.
• Begin iterating through the sequence of people. For each person, the fine is determined using the Fibonacci sequence.
• After calculating each person's fine, subtract it from the remaining fine amount.
• Keep track of the number of people who received tickets, including both paid and free ticket holders.

5. Final Calculation:

• Once the total fine amount is collected, the program outputs the total number of people who received tickets.

#include <iostream>
using namespace std;

// Define constants for easy adjustments
#define MAX_PAID_TICKETS 50          // Number of paid tickets available
#define COLLECTED_AMOUNT 20365011122 // Total amount collected from fine and tickets

// Function to calculate the nth Fibonacci number iteratively
long long fibonacci(int n)
{
  // Base cases for Fibonacci sequence
  if (n == 0)
    return 0; // Fibonacci(0) is 0
  if (n == 1)
    return 1; // Fibonacci(1) is 1

  // Variables to hold the previous two Fibonacci numbers
  long long fib1 = 0, fib2 = 1, fib3 = 0;

  // Compute the nth Fibonacci number iteratively
  for (int i = 2; i <= n; i++)
  {
    fib3 = fib1 + fib2; // Fibonacci calculation (sum of the previous two numbers)
    fib1 = fib2;        // Update fib1 to the previous fib2
    fib2 = fib3;        // Update fib2 to the current fib3 (which is fib1 + fib2)
  }

  return fib3; // Return the nth Fibonacci number
}

int main()
{
  // Calculate the initial amount collected from the paid tickets, subtracting 1 because we will assume the position where the paid ticket finish and previous from that as the starting point for fibo series,
  long long total_amount_collected = MAX_PAID_TICKETS - 1;

  // Calculate the remaining amount to be collected through fines
  long long fine_amount = COLLECTED_AMOUNT - total_amount_collected;

  // Initialize the total number of people who received tickets , double of paid tickets available ie odd and even and we are subtracting 2 from it because as we told, fibo series will count the two subtracted users
  long long people_count = MAX_PAID_TICKETS * 2 - 2;

  // Start calculating fines
  long long position = 0;

  // Log the initial state
  cout << "Initial state: " << endl;
  cout << "Paid Tickets Collected: Rs " << total_amount_collected << endl;
  cout << "Fine Amount to be Collected: Rs " << fine_amount << endl;
  cout << "People Count: " << people_count << endl;
  cout << "---------------------------------" << endl;

  // Loop until the remaining fine amount is collected (when fine_amount becomes 0)
  while (fine_amount > 0)
  {
    // Calculate the fine for the current position based on Fibonacci sequence
    long long fine = fibonacci(position); // Fibonacci fine for the current person

    // Subtract the calculated fine from the remaining fine amount
    fine_amount -= fine;

    // Log the progress after each person's fine
    cout << "Position " << position + (MAX_PAID_TICKETS * 2 - 2) << ": Fine = Rs " << fine << ", Remaining Fine = Rs " << fine_amount << endl;

    // Increment the total number of people that received tickets
    people_count++;

    // Move to the next person and update the position
    position++;
  }

  // Output the total number of people who received tickets
  cout << "---------------------------------" << endl;
  cout << "Total number of people who got tickets: " << people_count << endl;

  return 0;
}

Thank You!