---

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime> 

using namespace std;

const int MAX_SIZE = 100;


struct Stack {
    int data[MAX_SIZE];
    int top; // индекс вершины (-1 = пустой)

    Stack() : top(-1) {}

    bool isEmpty() { return top == -1; }
    bool isFull() { return top == MAX_SIZE - 1; }

    void push(int val) {
        if (!isFull()) data[++top] = val;
    }

    int pop() {
        if (!isEmpty()) return data[top--];
        return -1; // стек пуст
    }

    int peek() {
        if (!isEmpty()) return data[top];
        return -1;
    }
};


struct Queue {
    int data[MAX_SIZE];
    int head; // индекс начала
    int tail; // индекс конца
    int size;

    Queue() : head(0), tail(0), size(0) {}

    bool isEmpty() { return size == 0; }
    bool isFull() { return size == MAX_SIZE; }

    void enqueue(int val) {
        if (!isFull()) {
            data[tail] = val;
            tail = (tail + 1) % MAX_SIZE; // кольцевой буфер
            size++;
        }
    }

    int dequeue() {
        if (!isEmpty()) {
            int val = data[head];
            head = (head + 1) % MAX_SIZE;
            size--;
            return val;
        }
        return -1; // очередь пуста
    }

    int front() {
        if (!isEmpty()) return data[head];
        return -1;
    }
};

struct Deque {
    int data[MAX_SIZE];
    int head;
    int tail;
    int size;

    Deque() : head(0), tail(0), size(0) {}

    bool isEmpty() { return size == 0; }
    bool isFull() { return size == MAX_SIZE; }

    // Добавить спереди
    void pushFront(int val) {
        if (!isFull()) {
            head = (head - 1 + MAX_SIZE) % MAX_SIZE;
            data[head] = val;
            size++;
        }
    }

    // Добавить сзади
    void pushBack(int val) {
        if (!isFull()) {
            data[tail] = val;
            tail = (tail + 1) % MAX_SIZE;
            size++;
        }
    }

    // Удалить спереди
    int popFront() {
        if (!isEmpty()) {
            int val = data[head];
            head = (head + 1) % MAX_SIZE;
            size--;
            return val;
        }
        return -1;
    }

    // Удалить сзади
    int popBack() {
        if (!isEmpty()) {
            tail = (tail - 1 + MAX_SIZE) % MAX_SIZE;
            size--;
            return data[tail];
        }
        return -1;
    }

    int peekFront() {
        if (!isEmpty()) return data[head];
        return -1;
    }

    int peekBack() {
        if (!isEmpty()) return data[(tail - 1 + MAX_SIZE) % MAX_SIZE];
        return -1;
    }
};
// 2
string studentNames[] = {
    "Леха", "Маша", "Ваня", "Аня", "Даня",
    "Оля", "Серега", "Наташа", "Андрей", "Егор",
    "Паша", "Юля", "Миша", "Света", "Артем"
};

string ticketNames[] = {
    "Билет №1 (Массивы)", "Билет №2 (Списки)", "Билет №3 (Деревья)",
    "Билет №4 (Графы)",   "Билет №5 (Сортировки)", "Билет №6 (Рекурсия)",
    "Билет №7 (ООП)",     "Билет №8 (Паттерны)",
};

string taskNames[] = {
    "Задача А: написать BFS", "Задача Б: реализовать стек",
    "Задача В: обойти дерево", "Задача Г: найти минимум",
    "Задача Д: написать сортировку", "Задача Е: найти цикл в графе",
};

const int NUM_TICKETS = 8;
const int NUM_TASKS = 6;
const int NUM_NAMES = 15;


// Очередь студентов на пересдачу [i]
Queue waitingQueue;

// Очередь студентов,которые взяли билет и отвечают
Queue answeringQueue;

// Дек билетов у преподавателя
Deque ticketDeque;

// Стопка задач штек
Stack taskStack;

int nextStudentId = 0;

string studentList[MAX_SIZE];

int studentTicket[MAX_SIZE]; // индекс билета

int studentTask[MAX_SIZE];   // индекс задачи

int studentAttempts[MAX_SIZE];

int passedCount = 0;
// Добавить нового студента в очередь на пересдачу
void addNewStudent() {
    if (nextStudentId >= MAX_SIZE) return;
    int id = nextStudentId++;
    studentList[id] = studentNames[id % NUM_NAMES];
    studentAttempts[id] = 0;
    waitingQueue.enqueue(id);
    cout << "Новый студент пришёл на пересдачу: "
        << studentList[id] << " (ID=" << id << ")\n";
}

// Студент берёт билет и задачу, переходит в очередь отвечающих
void studentTakesTicket() {
    if (waitingQueue.isEmpty()) {
        cout << "Очередь на пересдачу пуста.\n";
        return;
    }
    if (ticketDeque.isEmpty() || taskStack.isEmpty()) {
        cout << "Нет билетов или задач!\n";
        return;
    }

    int id = waitingQueue.dequeue();
    studentAttempts[id]++;

    // Берём билет из дека (чётные попытки — снизу, нечётные — сверху)
    int ticketIdx;
    if (studentAttempts[id] % 2 == 1) {
        ticketIdx = ticketDeque.popFront(); // сверху
        cout << "  --> " << studentList[id]
            << " берёт билет СВЕРХУ: " << ticketNames[ticketIdx] << "\n";
    }
    else {
        ticketIdx = ticketDeque.popBack(); // снизу
        cout << "  --> " << studentList[id]
            << " берёт билет СНИЗУ: " << ticketNames[ticketIdx] << "\n";
    }

    // Берём задачу из стека (сверху)
    int taskIdx = taskStack.pop();
    cout << "  --> " << studentList[id]
        << " берёт задачу: " << taskNames[taskIdx] << "\n";

    studentTicket[id] = ticketIdx;
    studentTask[id] = taskIdx;

    answeringQueue.enqueue(id);
}

// Студент отвечает: 60% шанс сдать
void studentAnswers() {
    if (answeringQueue.isEmpty()) {
        cout << "Очередь отвечающих пуста.\n";
        return;
    }

    int id = answeringQueue.dequeue();
    int ticketIdx = studentTicket[id];
    int taskIdx = studentTask[id];

    bool passed = (rand() % 10) < 6; // 60% вероятность сдать

    cout << studentList[id]
        << " отвечает на " << ticketNames[ticketIdx]
        << " + " << taskNames[taskIdx] << "\n";

    // Возвращаем билет и задачу обратно
    ticketDeque.pushBack(ticketIdx);
    taskStack.push(taskIdx);
    cout << "  Билет и задача возвращены.\n";

    if (passed) {
        passedCount++;
        cout << "  [СДАЛ] " << studentList[id]
            << " успешно сдал экзамен! (попытка " << studentAttempts[id] << ")\n";
    }
    else {
        cout << "  [НЕ СДАЛ] " << studentList[id]
            << " не сдал. Возвращается в очередь. (попытка "
            << studentAttempts[id] << ")\n";
        waitingQueue.enqueue(id); // обратно в конец очереди
    }
}

// Инициализация билетов и задач
void initTicketsAndTasks() {
    // Заполняем дек билетами
    for (int i = 0; i < NUM_TICKETS; i++)
        ticketDeque.pushBack(i);

    // Заполняем стек задачами
    for (int i = 0; i < NUM_TASKS; i++)
        taskStack.push(i);
}

// Вывод состояния симуляции
void printState(int step) {
    cout << "\n=== Состояние после шага " << step << " ===\n";
    cout << "  Ожидают пересдачи: " << waitingQueue.size << " студ.\n";
    cout << "  Отвечают сейчас:   " << answeringQueue.size << " студ.\n";
    cout << "  Билетов в деке:    " << ticketDeque.size << "\n";
    cout << "  Задач в стопке:    " << taskStack.top + 1 << "\n";
    cout << "  Сдали экзамен:     " << passedCount << " студ.\n";
}
int main() {
    setlocale(LC_ALL, "RU");
    srand((unsigned)time(nullptr));
    cout << "СИМУЛЯЦИЯ ПЕРЕСДАЧИ ЭКЗАМЕНОВ\n";

    // Инициализация
    initTicketsAndTasks();

    // Добавляем первых 5 студентов
    cout << "<<< Начальное заполнение очереди >>>\n";
    for (int i = 0; i < 5; i++)
        addNewStudent();

    // Симуляция: 10 шагов
    for (int step = 1; step <= 10; step++) {
        cout << "\n<<< Шаг >>>" << step << " ---\n";

        // Иногда добавляем нового студента (40% шанс)
        if (rand() % 10 < 4)
            addNewStudent();

        // Студент из очереди берёт билет и задачу
        cout << "[Берут задание]\n";
        studentTakesTicket();

        // Студент из очереди отвечающих отвечает
        cout << "[Отвечают]\n";
        studentAnswers();

        printState(step);
    }

    cout << "\n========================================\n";
    cout << "  ИТОГ: сдали экзамен " << passedCount << " студентов.\n";
    cout << "  Ещё в очереди: " << waitingQueue.size + answeringQueue.size << " студентов.\n";
    cout << "========================================\n";

    return 0;
}