#include <iostream>
//kje gi koristime samo potrebnite funkcii od standardniot namespace.
using std::cout;
using std::cin;
using std::endl;

struct jazol {//definirame struktura jazol
    int info;//so integer info bidejkji rabotime so celobrojni podatoci
    jazol *link;//i pokazuvac kon naredniot jazol
};

struct EPList {//definirame struktura edinecno povrzana lista
    jazol *head;//pocetniot jazol
    void init();
    void create(int);
    void addFirst(int);
    void addLast(int);
    void printList();
    void deleteList();
    void addBefore(jazol*, int);
};

void EPList::init() {//funkcija za inicijalizacija so koja go postavuvame "glavniot" jazol na NULL
    head = NULL;
}

void EPList::create(int x) {//funkcija za kreiranje na prviot jazol vo listata
    head = new jazol;//bidejkji head ne pokazuva kon nisto(NULL), dinamicki alocirame nov jazol i sega head kje pokazuva kon adresata na toj jazol, sekogash treba da alocirame memorija koga pravime nov jazol
    head->info = x;//vo info poleto kaj sto pokazuva head kje go zapisheme vlezniot argument
    head->link = NULL;//bidejkji samo head e edinstveniot element znaci nemame drugi elementi i link poleto vo koe ni stoi adresata na naredniot element kje bide NULL
}

void EPList::addFirst(int x) {//funcija so koja dodavame element na pocetokot na listata
    jazol *pom = new jazol;//dinamicki alocirame nov jazol
    pom->info = x;//kje go zapisheme vlezniot argument vo info poleto na noviot pom jazol
    pom->link = head;//link poleto kje go popolnime so prviot jazol
    head = pom;//i prviot jazol kje go postavime na toj nov jazol so sto toj stanuva prv
}

void EPList::addLast(int x) {//funcija za dodavanje na jazol kon kraj na lista
    jazol *pom = new jazol;//dinamicki go alocirame noviot jazol
    pom->info = x;//kje go zapisheme vlezniot argument vo info poleto na noviot pom jazol
    pom->link = NULL;//bidejkji ponatamu nema elementi link kje pokazuva kon NULL
    if (head != NULL) {//proveruvame dokolku listata e prazna
        if (head->link == NULL) {//so ova proveruvame ako ima samo eden element
            head->link = pom;//togas naredniot jazol kje bide pom
        } else {//ako nema samo eden element
            jazol *dvizi = head;//definirame nov jazol so pomos na koj kje se dvizime vo listata i go inicijalizirame na prviot jazol
            while (dvizi->link != NULL)//i so ovoj ciklus kje odime se dodeka ne stigneme do posledniot jazol
                dvizi = dvizi->link;
            dvizi->link = pom;//i sega posledniot jazol kje pokazuva kon noviot jazol
        }
    }
}

void EPList::printList() {// funkcija za pecatejne na lista
    jazol *pom = head;//pomosen jazol so koj kje se dvizime
    cout << "Elementi na lista:" << endl;
    while (pom != NULL) {//dodeka ne e prazna
        cout << pom->info << '\t';//pecati go info poleto na jazolot na koj sto pokazuva pom
        pom = pom->link;//pomesti go pom na naredniot jazol
    }
    cout << endl;
}

void EPList::deleteList() {//funcija za brishenje na lista
    jazol *pom = head;//pomosen jazol so koj kje briseme
    while (head != NULL) {//se dodeka head ne ni e NULL, odnosno se dodeka listata ima elementi
        if (head->link == NULL) {//tuka proveruvame dali imame samo eden element ako imame samo toj treba da go izbrisheme
            delete head;
            head = NULL;
        } else {
            pom = head;//go postavuvame pom na prviot jazol
            head = head->link;//prviot jazol go postavuvame da pokazuva na narendiot
            delete pom;//i go brisheme pomoshniot jazol
        }
    }
}

void EPList::addBefore(jazol *j, int x) {//so ovaa funcija dodavame jazol pred jazolot kako vlezen argument
    if (j == head) {//ako jazolot pred koj sto dodavame e prviot jazol na listata znaci treba da dodademe jazol na pocetokot na listata
        addFirst(x);
    } else {
        jazol *dvizi = head;
        while (dvizi->link != j)//se dvizime se dodeka ne stigneme do elementot predhodnik na jazolot pred koj sto treba da dodademe
            dvizi = dvizi->link;
        jazol *pom = new jazol;//dinamicki alocirame nov jazol
        pom->info = x;//soodvetno go popolnuvame so vtoriot vlezen argument
        pom->link = dvizi->link;//noviot jazol kje pokazuva kon jazolot pred koj sto sme dodale nov jazol
        dvizi->link = pom;//a jazolot sto bil pred nego sega kje pokazuva kon noviot
    }
}

void foo(EPList &lista, int n) {
    int i;
    jazol *dvizi = lista.head;//jazol so pomos na koj kje se dvizime niz listata
    while (dvizi != NULL) {//se dvizime se do krajot na listata
        for (i = 0; i < n - 1; i++) {//so ovoj for ciklus dodavame tocno n-1 pat elementi so info pole rezultat na celobrojnoto delenje na info poleto na koe se naogja dvizi i brojot na elementi koi treba da gi dodademe(n)
            lista.addBefore(dvizi, dvizi->info / n);//elementite gi dodavame pred dvizi
        }
        dvizi->info = dvizi->info / n;//info poleto na dvizi isto taka kje go smenime so celobrojnoto delenje na vrednosta sto se naogjala predhodno i n, i zaradi ova gore vo for ciklusit ne iterirame do n
        dvizi = dvizi->link;//i dvizi kje go pomestime na naredniot jazol
    }

}

int main() {

    EPList lista;
    int n;

    lista.init();
    lista.create(17);
    lista.addFirst(12);
    lista.addLast(7);
    lista.addLast(2);

    lista.printList();

    cout << "Vnesi n->";
    cin >> n;

    foo(lista, n);

    lista.printList();

    lista.deleteList();

    return 0;
}