[shkola] 'Dyzdovnata' zadacha

On Saturday 22 March 2003 19:47, you wrote:
>Ami kakvo da ti kaza za subject-a ... pisha s 0.5 cps(chars per
>second)... bavna mi e konzolata , plus tova po default na taia posta mi
>e Emacs-a a s nego hic ne se razbiram ... glupavo zivotno..

Ami shto ne si smenish default-a. Ako imat mutt probvaj s nego. Mutt rulez.
Samo da podkaram fetchmail + exim i shte mina na mutt ;-).

>Btw ako niakoi ia reshi pishete kakvo vi e reshenieto . Az mislih dnes s
>flow da ia napravia, ama mislia che ne e podhodiasto zatova ia napravih
>po drug nachin... pishete kakav e vashiat..ivo mai glavno kam tebe tova

Abe ne znam kolko raboti no eto moeto 'reshenie'. Polovinata kod prosto
poddyrza edna piramida (oshte se chudq shto ne go napravih po drug nachin).
Inache ideqta e linejno obhozdane ot naj-visokiq vryh nadulo kato ottichash
vodata.

P.S. Ako se napravi s dinamichna pamet za ulicite shte moze da se podkara i za
dosta po-golemi danni. V momenta max 10000 nodes, 1000 edges per node. Prosto
nishto ne spomena za ogranicheniq.

-- 
Rangel Dokov


#include <stdio.h>

#define MAXN            10000
#define MAXK            1000

int hight[MAXN];
double water[MAXN];
struct edge {
        int count;
        int hight;
        int peers[MAXK];
} edges[MAXN];
int nodes;

int heap[MAXN];
int heap_cmp(int a, int b);
void push(int number);
int pop();

int heap_cmp(int a, int b) {
        if (hight[a] > hight[b])
                return -1;

        return 1;
}

void push(int number) {
        int cpos;
        int tmp;

        cpos = heap[0];
        heap[0]++;
        heap[cpos] = number;

        while (cpos > 1) {
                if (heap_cmp(heap[cpos], heap[cpos/2]) == -1) {
                        tmp = heap[cpos];
                        heap[cpos] = heap[cpos/2];
                        heap[cpos/2] = tmp;
                        cpos = cpos/2;
                } else
                        break;
        }
}

int pop() {
        int retv;
        int cpos;
        int tmp;

        if (heap[0] <= 1)
                return -1;

        retv = heap[1];
        heap[0]--;
        heap[1] = heap[heap[0]];
        cpos = 2;

        while (cpos < heap[0]) {
                if ((cpos + 1 < heap[0]) && (heap_cmp(heap[cpos], heap[cpos+1]) 
== 1))
                        cpos++;

                if (heap_cmp(cpos/2, cpos) == 1) {
                        tmp = heap[cpos];
                        heap[cpos] = heap[cpos/2];
                        heap[cpos/2] = tmp;
                } else
                        break;

                cpos *= 2;
        }

        return retv;
}

void add_edge(int from, int to) {

        if (edges[from].count && edges[from].hight < hight[to])
                return;

        if (edges[from].hight == hight[to]) {
                edges[from].peers[edges[from].count] = to;
                edges[from].count++;
        } else {
                edges[from].count = 1;
                edges[from].peers[0] = to;
                edges[from].hight = hight[to];
        }
}

int main() {
        int i;
        int tmp1, tmp2, tmp3;
        int edgec;
        int curr;

        heap[0] = 1; // heap initialization ;-)

        scanf("%d %d", &nodes, &edgec);
        for (i = 1; i <= nodes; i++) {
                scanf("%d", &hight[i]);
                push(i);
        }

        for (i = 0; i < edgec; i++) {
                scanf("%d %d %d", &tmp1, &tmp2, &tmp3);
                if (hight[tmp1] == hight[tmp2]) {
                        water[tmp1] += tmp3/2.0;
                        water[tmp2] += tmp3/2.0;
                        continue;
                }
                if (hight[tmp1] < hight[tmp2]) {
                        add_edge(tmp2, tmp1);
                        water[tmp1] += tmp3;
                } else {
                        add_edge(tmp1, tmp2);
                        water[tmp2] += tmp3;
                }
        }

        while ((curr = pop()) != -1) {
                for (i = 0; i < edges[curr].count; i++) {
                        tmp1 = edges[curr].peers[i];
                        water[tmp1] += water[curr]/(double)edges[curr].count;
                        water[curr] = 0;
                }
        }

        for (i = 0; i < nodes; i++)
                if (water[i])
                        printf("%d %.4f\n", i, water[i]);

        return 0;
}

Other related posts: