Дадена е двострано поврзана листа чии што јазли содржат по еден природен број. Листата треба да се подели на две резултантни листи, т.ш. во првата листа треба да се сместат сите јазли кои содржат броеви помали или еднакви на просекот на листата, а во втората сите јазли кои содржат броеви поголеми од просекот на листата. Јазлите во резултантните листи се додаваат според обратен редослед од оној по кој по кој се појавуваат во дадената листа (т.е. прво се започнува со разгледување на последниот јазол од влезната листа и се додава во соодветната резултантна листа, па претпоследниот итн...).

Во првиот ред од влезот е даден бројот на јазли во листата, а во вториот ред се дадени броевите од кои се составени јазлите по редослед во листата. Во првиот ред од излезот треба да се испечатат јазлите по редослед од првата резултантна листа (броеви помали или еднакви на просекот на листата), во вториот ред од втората (броеви поголеми од просекот на листата) .

Име на класа (за Java): PodeliListaProsek

Делумно решение: Задачата се смета за делумно решена доколку се поминати 7 тест примери.

Забелешка: При реализација на задачите МОРА да се користат дадените структури, а не да користат помошни структури како низи или сл.

#include<stdio.h>
#include<malloc.h>

//Implementacijata na dvojnata lista e so jazel vodich

typedef struct element{
        int info;
        struct element *llink, *rlink;
}node;

node * novaDvojna()
{
      node *v = (node *)malloc(sizeof(node));
      v -> llink = v;
      v -> rlink = v;
      return v;
}

void dodadi(node **pok_v, int broj){
    //dodavanja na broj na kraj na dvojnata lista
    node *temp;
    temp=(node *)malloc(sizeof(node));
    temp->info=broj;
    temp -> llink = (*pok_v) -> llink;
    temp -> rlink = *pok_v;
    (*pok_v) -> llink -> rlink = temp;
    (*pok_v) -> llink = temp;
}

void podeli(node *l, node *lpomali, node *lpogolemi){

    int brojac=0,prosek=0;
    node *k=NULL;
    k=l;
    l=l->llink;
    while(l!=k)
    {
        prosek+=l->info;
        brojac++;
        l=l->llink;
    }
    prosek/=brojac;
    l=l->llink;
    while(l!=k)
    {

        if(l->info<=prosek)
        {
              dodadi(&lpomali,l->info);
        }
        else if(l->info>prosek)
        {
            dodadi(&lpogolemi,l->info);
        }

        l=l->llink;

    }
}

int main(){
    node *lista=NULL, *pomali=NULL, *pogolemi=NULL;
    int i,n,info;

    lista=novaDvojna();
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
       scanf ("%d", &info);
       dodadi(&lista,info);
    }

    pomali=novaDvojna();
    pogolemi=novaDvojna();

    podeli(lista, pomali, pogolemi) ;

    //Pechatenje na pomali i ednakvi od prosekot
    node *p=pomali->rlink;
    while (pomali != p)
    {
        printf ("%d", p->info);
        if(p->rlink!=pomali) printf (" ");
        p=p->rlink;
    }
    printf ("\n");

    //Pechatenje na pogolemi od prosekot
    p=pogolemi->rlink;
    while (pogolemi != p)
    {
        printf ("%d", p->info);
        if(p->rlink!=pogolemi) printf (" ");
        p=p->rlink;
    }
    printf ("\n");

    return 0;
}
Sample input
5
4 2 1 5 3
Sample output
3 1 2
5 4