#include <stdio.h> #define MIN(a,b) (((a)<(b))?(a):(b)) #define MAX(a,b) (((a)>(b))?(a):(b)) const int C=200001, Inf=1000000001; struct triple{ int value; int bottle; int full; }; int iF=0, jF=0, V0, V1, V2; int res[C], dp[C][3][2]; //dp - C value, empty/full, 1/2 bool exists[C][3][2]; triple F[7*C]; void insert_to_F(int a, int b, int c, int resa){ int bottle=-1, value=c; bool full=false; if (a == V0){ bottle = 0; full = true; } if (a == 0){ bottle = 0; full = false; } if (b == V1){ bottle = 1; full = true; } if (b == 0){ bottle = 1; full = false; } if (c == V2){ bottle = 2; full = true; value = b; } if (c == 0){ bottle = 2; full = false; value = b; } if (!exists[value][bottle][full]){ dp[value][bottle][full]=resa+1; exists[value][bottle][full]=true; F[jF] = {value, bottle, full}; jF++; } } void apply_transforms(int a, int b, int c, int value){ int d0 = V0-a, d1=V1-b, d2=V2-c; //lanie w B insert_to_F(MAX(0, a-d1), MIN(V1, a+b), c, value); insert_to_F(a, MIN(V1, b+c), MAX(0, c-d1), value); //lanie w c insert_to_F(a, MAX(0, b-d2), MIN(V2, b+c), value); insert_to_F(MAX(0, a-d2), b, MIN(V2, c+a), value); //lanie w a insert_to_F(MIN(V0, a+c), b, MAX(0, c-d0), value); insert_to_F(MIN(V0, a+b), MAX(0, b-d0), c, value); } int main(){ int i, j, ij, d0, d1, d2, j1, j2, sum=0; scanf ("%d %d %d", &V0, &V1, &V2); scanf ("%d %d %d", &d0, &d1, &d2); sum = d0+d1+d2; for (i=0; i<=V2; i++) res[i] = Inf; for (i=0; i<=V2; i++){ res[i]=Inf; for (j1=0; j1<3; j1++){ for (j2=0; j2<2; j2++){ dp[i][j1][j2] = Inf; exists[i][j1][j2] = false; } } } res[d0] = res[d1] = res[d2] = 0; //Transform 1: insert to FIFO apply_transforms(d0, d1, d2, 0); triple a; int v_a, v_b, v_c; for (iF = 0; iF<jF; iF++){ a = F[iF]; if (a.bottle == 0){ if (a.full) v_a = V0; else v_a = 0; v_b = sum-a.value-v_a; v_c = a.value; } else if (a.bottle == 1){ if (a.full) v_b = V1; else v_b = 0; v_a = sum-a.value-v_b; v_c = a.value; } else if (a.bottle == 2){ if (a.full) v_c = V2; else v_c = 0; v_a = sum - a.value - v_c; v_b = a.value; } if (res[v_a] == Inf) res[v_a] = dp[a.value][a.bottle][a.full]; if (res[v_b] == Inf) res[v_b] = dp[a.value][a.bottle][a.full]; if (res[v_c] == Inf) res[v_c] = dp[a.value][a.bottle][a.full]; apply_transforms(v_a, v_b, v_c, dp[a.value][a.bottle][a.full]); } for (i=0; i<=V2; i++){ if (res[i] != Inf) printf ("%d ", res[i]); else printf ("%d ", -1); } printf ("\n"); return 0;}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 | #include <stdio.h> #define MIN(a,b) (((a)<(b))?(a):(b)) #define MAX(a,b) (((a)>(b))?(a):(b)) const int C=200001, Inf=1000000001; struct triple{ int value; int bottle; int full; }; int iF=0, jF=0, V0, V1, V2; int res[C], dp[C][3][2]; //dp - C value, empty/full, 1/2 bool exists[C][3][2]; triple F[7*C]; void insert_to_F(int a, int b, int c, int resa){ int bottle=-1, value=c; bool full=false; if (a == V0){ bottle = 0; full = true; } if (a == 0){ bottle = 0; full = false; } if (b == V1){ bottle = 1; full = true; } if (b == 0){ bottle = 1; full = false; } if (c == V2){ bottle = 2; full = true; value = b; } if (c == 0){ bottle = 2; full = false; value = b; } if (!exists[value][bottle][full]){ dp[value][bottle][full]=resa+1; exists[value][bottle][full]=true; F[jF] = {value, bottle, full}; jF++; } } void apply_transforms(int a, int b, int c, int value){ int d0 = V0-a, d1=V1-b, d2=V2-c; //lanie w B insert_to_F(MAX(0, a-d1), MIN(V1, a+b), c, value); insert_to_F(a, MIN(V1, b+c), MAX(0, c-d1), value); //lanie w c insert_to_F(a, MAX(0, b-d2), MIN(V2, b+c), value); insert_to_F(MAX(0, a-d2), b, MIN(V2, c+a), value); //lanie w a insert_to_F(MIN(V0, a+c), b, MAX(0, c-d0), value); insert_to_F(MIN(V0, a+b), MAX(0, b-d0), c, value); } int main(){ int i, j, ij, d0, d1, d2, j1, j2, sum=0; scanf ("%d %d %d", &V0, &V1, &V2); scanf ("%d %d %d", &d0, &d1, &d2); sum = d0+d1+d2; for (i=0; i<=V2; i++) res[i] = Inf; for (i=0; i<=V2; i++){ res[i]=Inf; for (j1=0; j1<3; j1++){ for (j2=0; j2<2; j2++){ dp[i][j1][j2] = Inf; exists[i][j1][j2] = false; } } } res[d0] = res[d1] = res[d2] = 0; //Transform 1: insert to FIFO apply_transforms(d0, d1, d2, 0); triple a; int v_a, v_b, v_c; for (iF = 0; iF<jF; iF++){ a = F[iF]; if (a.bottle == 0){ if (a.full) v_a = V0; else v_a = 0; v_b = sum-a.value-v_a; v_c = a.value; } else if (a.bottle == 1){ if (a.full) v_b = V1; else v_b = 0; v_a = sum-a.value-v_b; v_c = a.value; } else if (a.bottle == 2){ if (a.full) v_c = V2; else v_c = 0; v_a = sum - a.value - v_c; v_b = a.value; } if (res[v_a] == Inf) res[v_a] = dp[a.value][a.bottle][a.full]; if (res[v_b] == Inf) res[v_b] = dp[a.value][a.bottle][a.full]; if (res[v_c] == Inf) res[v_c] = dp[a.value][a.bottle][a.full]; apply_transforms(v_a, v_b, v_c, dp[a.value][a.bottle][a.full]); } for (i=0; i<=V2; i++){ if (res[i] != Inf) printf ("%d ", res[i]); else printf ("%d ", -1); } printf ("\n"); return 0;} |