---

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

struct Tovar {
    char name[50];
    int price;
    int day;
};

const int N = 7;
const int M = 10;

int hash(int key, int m) {
    return key % m;
}

void genRandomSteps(int steps[], int m, int size) {
    for (int i = 0; i < size; i++) {
        steps[i] = 1 + rand() % (m - 1);
    }
}

void addToHashTable(Tovar* table, int* status, Tovar item, int m, int steps[]) {
    int base = hash(item.price, m);
    int i = base;
    int p = 0;
    while (status[i] == 1) {
        p++;
        i = (base + steps[p % m]) % m;
        if (p > m * 2) {
            std::cerr << "Tablica perepolnena\n";
            return;
        }
    }
    table[i] = item;
    status[i] = 1;
}

int searchInHashTable(Tovar* table, int* status, int key, int m, int steps[]) {
    int base = hash(key, m);
    int i = base;
    int p = 0;
    while (status[i] != 0) {
        if (status[i] == 1 && table[i].price == key) return i;
        p++;
        i = (base + steps[p % m]) % m;
        if (p > m * 2) break;
    }
    return -1;
}

int main() {
    std::srand(static_cast<unsigned>(std::time(nullptr)));

    Tovar tovars[N];
    std::cout << "Vvedite dannye o " << N << " tovarah (nazvanie, cena, den_vypuska):\n";
    for (int i = 0; i < N; i++) {
        std::cin >> tovars[i].name >> tovars[i].price >> tovars[i].day;
    }

    int randomSteps[M];
    genRandomSteps(randomSteps, M, M);

    Tovar hashTable[M];
    int status[M];
    for (int i = 0; i < M; i++) status[i] = 0;

    for (int i = 0; i < N; i++) {
        addToHashTable(hashTable, status, tovars[i], M, randomSteps);
    }

    std::cout << "\nIshodnyj massiv:\n";
    for (int i = 0; i < N; i++) {
        std::cout << tovars[i].name << " " << tovars[i].price << " " << tovars[i].day << std::endl;
    }

    std::cout << "\nHesh-tablica (proizvolnaya adresaciya, M=" << M << "):\n";
    for (int i = 0; i < M; i++) {
        std::cout << "H[" << i << "] = ";
        if (status[i] == 0) std::cout << "svobodno\n";
        else std::cout << hashTable[i].name << " " << hashTable[i].price << " " << hashTable[i].day << std::endl;
    }

    std::cout << "\nPoisk po klyuchu (cena). Dlya vyhoda vvedite -1:\n";
    int key;
    while (true) {
        std::cout << "Vvedite cenu: ";
        if (!(std::cin >> key)) {
            std::cin.clear();
            std::cin.ignore(10000, '\n');
            std::cout << "Oshibka vvoda\n";
            continue;
        }
        if (key == -1) break;
        int idx = searchInHashTable(hashTable, status, key, M, randomSteps);
        if (idx == -1) {
            std::cout << "Net elementa\n";
        } else {
            std::cout << "Najdeno: " << hashTable[idx].name << " "
                      << hashTable[idx].price << " " << hashTable[idx].day << std::endl;
        }
    }
    return 0;
}