/*
Задача 2.2 ПРЕЛИВАНЕ
 
Разполагаме с три съда, съответно с вместимост a, b и c литра (a, b и c са цели
положителни числа, ненадминаващи 200). Първият и вторият съд са празни, а
третият е напълнен догоре с вода. Разрешено е да преливаме неколкократно
(нула, един или повечe пъти) от един съд в друг, но понеже не разполагаме с
никакви мерки, може само да напълваме догоре съда в който наливаме или да
изпразваме докрай съда от който преливаме, когато това е възможно. Не е
разрешено да изливаме вода извън съдовете. 

Напишете програма FILL.EXE, която пресмята какво най-малко сумарно количество
течност трябва да бъде прелято така, че в поне един от съдовете да се получи
зададено количество течност d литра (d е цяло положително число, ненадминаващо 200).
Ако не е възможно да се получи по указания начин количеството d, Вашата програма
трябва да намери най-близкото до d по-малко неотрицателно цяло число литри d',
което е възможно да се получи вместо d и да пресметне за него минималното количество
прелята течност.

Входните данни се четат от стандартния вход като четири цели положителни числа
a, b, c и d, разделени с по един интервал. Резултатът трябва да бъде изведен на
стандартния изход като двойка цели неотрицателни числа, разделени с един интервал –
първото от тези числа трябва да е равно на намереното минимално количество прелята
течност, а второто трябва да е равно на d, ако за него е възможно да се осъществи
описаното преливане, или да е равно на намерената от Вашата програма по-малка
възможна стойност d'.



РЕШЕНИЕ
от Иван Анев

Знаейки първоначалното количество вода и големината на трите кофи, всяко моментно
състояние може еднозначно да се опише чрез количеството вода в две от кофите. Така
лесно се забелязва, че максималния брой различни състояния, при максимална големина
на всички кофи и максимално начално количество вода е 20100. От начина на преливане
и от теорията на числата (която няма да излагаме тук), може да се забележи, че не
всички състояния са постижими от началното състояние.

Нека имаме насочен граф, където върховете са различните състояния на водата в кофите,
а дъгите са между върхове, такива че от едното състояние може с едно преливане да се
стигне до другото. Нека дъгите имат тежест равна на количеството преляна вода. В така
получения граф ние се интересуваме от най-кратките пътища от началния връх до всички
останали. После ще намерим състоянията, които ни интересуват и ще изберем това, което
удовлетворява най-точно изискванията на задачата.

Ако се използва най-разпространената реализация на алгоритъма на Дейкстра, времето за
изпълнение ще бъде пропорционално на квадрата на броят на достижимите състояния. При,
което не е напълно ясно дали няма случай, в който броят на тези позиции е прекалено голям
и дали ще ни стигне отпуснатото време. Може да се приложи и реализация на Дейкстра, която
използва структурата пирамида (heap), тогава няма да има съмнения относно необходимото време
за изпълнение на програмата.

За повече информация за реализациите на алгоритъма на Дейкстра може да намерите в съответната
литература.
*/


/*
NAME: Ivan Anev
PROG: fill
LANG: C
*/

#include <stdio.h>
#include <limits.h>

#define MAXV 65536
#define MAXS 256

#undef min
#undef max

int k[MAXV], hp[MAXV];
int heap[MAXV], heapsize;
int a, b, c, d;
int afill, ad;

void readf(void);
void solve(void);
void writef(void);

int main(void) {
        readf();
        solve();
        writef();

        return 0;
}

void readf(void) {
        scanf("%d%d%d%d", &a, &b, &c, &d);
}

void solve(void) {
        int cd, x, y, z, i, p;

        int code(int a, int b);
        void decode(int code, int *a, int *b);
        void add(int v);
        int top(void);
        int min(int a, int b);
        int max(int a, int b);
        void relax(int nc, int c, int p);

        for (i = 0; i < MAXV; ++i) {
                k[i] = INT_MAX;
                hp[i] = -1;
        }

        cd = code(0, 0);
        k[cd] = 0;
        add(cd);
        ad = -1;
        while (heapsize > 0) {
                cd = top();
                decode(cd, &x, &y);
                z = c - x - y;
                if (x == d || y == d || z == d) {
                        afill = k[cd];
                        ad = d;
                        break;
                }
                if (x < d && x > ad) {
                        afill = k[cd];
                        ad = x;
                }
                if (y < d && y > ad) {
                        afill = k[cd];
                        ad = y;
                }
                if (z < d && z > ad) {
                        afill = k[cd];
                        ad = z;
                }

                p = min(a - x, y);
                relax(code(x + p, y - p), cd, p);
                p = min(x, b - y);
                relax(code(x - p, y + p), cd, p);
                p = min(a - x, z);
                relax(code(x + p, y), cd, p);
                p = min(x, c - z);
                relax(code(x - p, y), cd, p);
                p = min(b - y, z);
                relax(code(x, y + p), cd, p);
                p = min(y, c - z);
                relax(code(x, y - p), cd, p);
        }
}

void writef(void) {
        printf("%d %d\n", afill, ad);
}

void relax(int nc, int c, int p) {
        void add(int v);
        void moveup(int v);

        if (hp[nc] == -1) {
                k[nc] = k[c] + p;
                add(nc);
        }
        else if (k[nc] > k[c] + p) {
                k[nc] = k[c] + p;
                moveup(hp[nc]);
        }
}

int top(void) {
        int r;

        void movedown(int v);

        r = heap[0];
        heap[0] = heap[--heapsize];
        hp[heap[0]] = 0;
        movedown(0);

        return r;
}

void add(int v) {
        void moveup(int v);

        heap[heapsize] = v;
        hp[v] = heapsize;
        moveup(heapsize++);
}

void moveup(int v) {
        int t, p;

        t = heap[v];
        while (v > 0) {
                p = (v - 1) / 2;
                if (k[heap[p]] > k[t]) {
                        heap[v] = heap[p];
                        hp[heap[v]] = v;
                        v = p;
                }
                else
                        break;
        }
        heap[v] = t;
        hp[t] = v;
}

void movedown(int v) {
        int t, c;

        t = heap[v];
        while ((c = 2 * v + 1) < heapsize) {
                if (c + 1 < heapsize && k[heap[c]] > k[heap[c+1]])
                        ++c;
                if (k[heap[c]] < k[t]) {
                        heap[v] = heap[c];
                        hp[heap[v]] = v;
                        v = c;
                }
                else
                        break;
        }
        heap[v] = t;
        hp[t] = v;
}

int code(int a, int b) {
        return (a * MAXS + b);
}

void decode(int code, int *a, int *b) {
        *a = code / MAXS;
        *b = code % MAXS;
}

int min(int a, int b) {
        return ((a < b) ? a : b);
}

int max(int a, int b) {
        return ((a > b) ? a : b);
}