#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

int generate_random_number(int min, int max);
bool simulation(int n_passengers);

int main(void)
{
    int n_passengers;
    int n_runs;

    printf("Enter the number of passengers: ");
    scanf("%d", &n_passengers);
    printf("Enter the number of runs: ");
    scanf("%d", &n_runs);
    
    int success_count = 0;
    for (int i = 0; i < n_runs; i++)
    {
        if (simulation(n_passengers))
        {
            success_count++;
        }
    }
    printf("Success rate: %lf%%\n", (double) success_count / (double) n_runs);

    return 0;
}

int generate_random_number(int min, int max)
{
    return rand() % (max - min + 1) + min;
}

bool simulation(int n_passengers)
{
    int passengers_on_board_order[n_passengers];
    for (int i = 0; i < n_passengers; i++)
    {
        passengers_on_board_order[i] = i;
    }

    // Shuffle the array by Fisher-Yates algorithm
    for (int i = 0; i < n_passengers; i++)
    {
        int j = generate_random_number(0, n_passengers - 1);
        int temp = passengers_on_board_order[i];
        passengers_on_board_order[i] = passengers_on_board_order[j];
        passengers_on_board_order[j] = temp;
    }

    bool *restrict seats_taken = malloc(n_passengers * sizeof(bool));
    for (int i = 0; i < n_passengers; i++)
    {
        seats_taken[i] = false;
    }

    /* First passenger */
    int random_seat = generate_random_number(0, n_passengers - 1);
    if (random_seat == passengers_on_board_order[n_passengers - 1])
    {
        goto failure;
    }
    seats_taken[random_seat] = true;

    /* Second to the second last passenger */
    for (int i = 1; i < (n_passengers - 1); i++)
    {
        bool take_random_seat = true;
        if (seats_taken[passengers_on_board_order[i]] == false)
        {
            if (generate_random_number(0, 2) != 0)
            {
                seats_taken[passengers_on_board_order[i]] = true;
                take_random_seat = false;
            }
        }

        if (take_random_seat)
        {
            int random_seat = generate_random_number(0, n_passengers - 1);
            while (seats_taken[random_seat] == true)
            {
                random_seat = generate_random_number(0, n_passengers - 1);
            }
            if (random_seat == passengers_on_board_order[(n_passengers - 1)])
            {
                goto failure;
            }
        }
    }

    free(seats_taken);
    return true;

failure:
    free(seats_taken);
    return false;
}

if (take_random_seat)
        {
            int random_seat = generate_random_number(0, n_passengers - 1);
            while (seats_taken[random_seat] == true)
            {
                random_seat = generate_random_number(0, n_passengers - 1);
            }
            if (random_seat == passengers_on_board_order[(n_passengers - 1)])
            {
                goto failure;
            }

            seats_taken[random_seat] = true;
        }

Enter the number of passengers: 3
Enter the number of runs: 50000000
Success rate: 38.879478%

Enter the number of passengers: 1000
Enter the number of runs: 500000
Success rate: 0.302200%