---

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

using namespace std;

struct Sportsman {
    string surname;
    int points;
    int place;
};

int hashFunc(int key, int M) {
    return key % M;
}

void sv_add(Sportsman person, int m, Sportsman H[], int status[]) {
    int key = person.points;
    int i = hashFunc(key, m);
    int p = 1;
    
    while (status[i] == 1 && p < m) {
        i = (hashFunc(key, m) + p * p) % m;
        p++;
    }
    
    if (status[i] != 1) {
        H[i] = person;
        status[i] = 1;
    }
}

int sv_search(int key, int m, Sportsman H[], int status[]) {
    int start = hashFunc(key, m);
    int i = start;
    int p = 1;
    
    if (status[i] == 1 && H[i].points == key) return i;
    
    while (p < m) {
        i = (start + p * p) % m;
        if (status[i] == 1 && H[i].points == key) return i;
        if (status[i] == 0) break;
        p++;
    }
    return -1;
}

string randomSurname() {
    string surnames[] = {"Иванов", "Петров", "Сидоров", "Кузнецов", "Смирнов"};
    return surnames[rand() % 5];
}

int randomPoints() {
    return 10 + rand() % 91;  // Новый диапазон: 10-100
}

int randomPlace() {
    return 1 + rand() % 15;  // 1-15 место
}

void printHashTable(Sportsman H[], int status[], int m) {
    cout << "\n=== Хеш-таблица (квадратичная адресация) ===" << endl;
    for (int i = 0; i < m; i++) {
        if (status[i] == 1) {
            cout << "H[" << setw(2) << i << "] -> " << H[i].surname 
                 << " | очки: " << H[i].points 
                 << " | место: " << H[i].place << endl;
        } else {
            cout << "H[" << setw(2) << i << "] -> СВОБОДНО" << endl;
        }
    }
}

int main() {
    srand(time(NULL));
    
    const int n = 9;
    const int M = 15;
    
    Sportsman sportsmen[n];
    cout << "=== ВАРИАНТ B9: Квадратичная адресация (ключ - количество очков) ===" << endl;
    cout << "Сгенерированный массив спортсменов (" << n << " элементов):" << endl;
    cout << "------------------------------------------------------------------------" << endl;
    for (int i = 0; i < n; i++) {
        sportsmen[i].points = randomPoints();
        sportsmen[i].surname = randomSurname();
        sportsmen[i].place = randomPlace();
        cout << "[" << i << "] " << sportsmen[i].surname 
             << " | очки: " << sportsmen[i].points 
             << " | место: " << sportsmen[i].place
             << " (hash = " << (sportsmen[i].points % M) << ")" << endl;
    }
    cout << "------------------------------------------------------------------------" << endl;
    
    Sportsman H[M];
    int status[M];
    for (int i = 0; i < M; i++) status[i] = 0;
    
    for (int i = 0; i < n; i++) sv_add(sportsmen[i], M, H, status);
    
    printHashTable(H, status, M);
    
    cout << "\n=== ПОИСК СПОРТСМЕНА ===" << endl;
    int searchPoints;
    cout << "Введите количество очков для поиска (10-100): ";
    cin >> searchPoints;
    
    int position = sv_search(searchPoints, M, H, status);
    
    if (position != -1) {
        cout << "\n✅ Спортсмен с " << searchPoints << " очками НАЙДЕН!" << endl;
        cout << "Позиция в хеш-таблице: H[" << position << "]" << endl;
        cout << "\n--- ВСЕ ПОЛЯ СТРУКТУРЫ ---" << endl;
        cout << "Фамилия:           " << H[position].surname << endl;
        cout << "Количество очков:  " << H[position].points << endl;
        cout << "Занятое место:     " << H[position].place << endl;
    } else {
        cout << "\n❌ Спортсмен с " << searchPoints << " очками НЕ НАЙДЕН в хеш-таблице!" << endl;
    }
    
    return 0;
}