3 / 13
May 2021

Hi guys,

I’m stuck on TSHPATH/SHPATH problems. Got WA with many attempts. I’ve checked my code for boundary cases and large input, I’ve also checked this code on the similar problems (uva-judge uva-929, uva-1112, uva-10986) and everything was fine. Need any help/test cases.

I use dijsktra + priority queue. Priority queue code was copy-pasted from Sedgwick’s book. Thank you!

Code:

#undef NDEBUG
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <assert.h>

struct PQi {
    int d;
    int N;
    int* pq;
    int* qp;
    int* a;
};

void pq_fixUp(struct PQi* self, int k);
void pq_exch(struct PQi* self, int i, int j);
void pq_fixDown(struct PQi* self, int k, int n);

void pq_init(struct PQi* self, int N, int* keys, int d) {
    self->d = d;
    self->N = 0;
    self->a = keys;
    self->pq = malloc((N+1)*sizeof(int));
    self->qp = malloc((N+1)*sizeof(int));
}

void pq_destroy(struct PQi* self) {
    free(self->pq);
    free(self->qp);
}

void pq_insert(struct PQi* self, int v) {
    self->pq[++(self->N)] = v;
    self->qp[v] = self->N;
    pq_fixUp(self, self->N);
}

int pq_getmin(struct PQi* self) {
    pq_exch(self, 1, self->N);
    pq_fixDown(self, 1, self->N-1);
    return self->pq[self->N--];
}

void pq_lower(struct PQi* self, int k) {
    pq_fixUp(self, self->qp[k]);
}

void pq_exch(struct PQi* self, int i, int j) {
    int t;
    t = self->pq[i]; self->pq[i] = self->pq[j]; self->pq[j] = t;
    self->qp[self->pq[i]] = i;
    self->qp[self->pq[j]] = j;
}

void pq_fixUp(struct PQi* self, int k) {
    int* a = self->a;
    int d = self->d;
    int* pq = self->pq;
    while ((k > 1) && (a[pq[(k+d-2)/d]] > a[pq[k]])) {
        pq_exch(self, k, (k+d-2)/d);
        k = (k+d-2)/d;
    }
}

void pq_fixDown(struct PQi* self, int k, int n) {
    int d = self->d;
    int* pq = self->pq;
    int* a = self->a;
    int i, j;
    while ((j = (d*(k-1)+2)) <= n) {
        for (i = j+1; i<j+d && i <= n; i=i+1) {
            if (a[pq[j]] > a[pq[i]]) {
                j = i;
            }
        }
        if (!(a[pq[k]] > a[pq[j]])) {
            break;
        }
        pq_exch(self, k, j);
        k = j;
    }
}

void pq_info(struct PQi* self) {
    printf("info\n");
    printf("pq:\n");
    for (int i = 1; i <= self->N; i=i+1) {
        printf("%d ", self->pq[i]);
    }
    printf("qp:\n");
    for (int i = 1; i <= self->N; i=i+1) {
        printf("%d ", self->pq[i]);
    }
    printf("end of info\n");
}

void pq_test() {
    struct PQi pq;
    int keys[] = {0 /*unused*/,1,2,3,4,5,5,4,3,2,1};
    pq_init(&pq, 200, keys, 2);
    for (int i = 1; i<=10; i=i+1) {
        printf("insert %d\n", i);
        pq_insert(&pq, i);
        pq_info(&pq);
    }
    for (int i = 1; i<=6; i=i+1) {
        int m = pq_getmin(&pq);
        printf("min => %d\n", m);
    }
}

int find_index(char* id2name, int n, char* name) {
    for (int i = 1; i<=n; i=i+1) {
        if (!strcmp(&id2name[i*20], name)) {
            return i;
        }
    }
    return -200000;
}

int find_mincost(int*W, int*Links, int*Sizes, int n, int rs, int i1, int i2) {
    struct PQi pq;
    int* R;
    int* P;
    int IntMax = INT_MAX - 200000;
    int i,j1,j,kMin,res,wt;
    R = malloc((n+1)*sizeof(int));
    P = malloc((n+1)*sizeof(int));
    for (int i = 1; i<=n; i=i+1) {
        P[i] = 1;
        R[i] = IntMax;
    }

    for (i = 1; i <= Sizes[i1]; i=i+1) {
        R[Links[i1*rs+i]] = W[i1*rs+i];
    }
    
    R[i1] = 0;
    pq_init(&pq, n+1, R, 2);

    for (i=1; i<=n; i=i+1) {
        pq_insert(&pq, i);
    }
    kMin = pq_getmin(&pq);
    assert(kMin == i1);
    R[i1] = 0;
    P[i1] = 0;

    for (i=1; i<=n-1; i=i+1) {
        kMin = pq_getmin(&pq);
        for (j1=1;j1<=Sizes[kMin];j1=j1+1) {
            j = Links[kMin*rs+j1];
            wt = W[kMin*rs+j1];
            if (R[kMin]+wt < R[j]) {
                R[j] = R[kMin]+wt;
                P[j] = kMin;
                pq_lower(&pq, j);
            }
        }
    }

    res = R[i2];
    if (res == IntMax) {
        res = -1;
    }

    pq_destroy(&pq);
    free(R); free(P);
    return res;
}

void solve() {
    int n,rs;
    int k,i,j,nr,cost;
    int* W;
    int* Links;
    int* Sizes;
    char* id2name;
    char name1[20];
    char name2[20];
    scanf("%d", &n);
    rs = n+10;
    W = malloc((n+1)*rs*sizeof(int));
    Links = malloc((n+1)*rs*sizeof(int));
    Sizes = calloc((n+1),sizeof(int));
    id2name = malloc(20*(n+1));

    for (i = 1; i<=n; i=i+1) {
        scanf("%s", &id2name[20*i]);
        scanf("%d", &k);

        for (j = 1; j<=k; j=j+1) {
            scanf("%d%d", &nr, &cost);
            Sizes[i]++;
            Links[i*rs+Sizes[i]] = nr;
            W[i*rs+Sizes[i]] = cost;
        }
    }

    scanf("%d",&nr);
    for (i=1; i<=nr; i=i+1) {
        scanf("%s%s", name1, name2);
        int i1= find_index(id2name, n, name1);
        int i2= find_index(id2name, n, name2);
        // printf("search %d->%d: '%s'->'%s'\n", i1,i2, name1, name2);
        cost = find_mincost(W,Links,Sizes,n,rs,i1,i2);
        if (cost >= 0) {
            printf("%d\n", cost);
        }
    }

    free(W); free(Links); free(Sizes); free(id2name);
}

int main() {
    // pq_test();
    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }
    return 0;
}
  • created

    May '21
  • last reply

    May '21
  • 12

    replies

  • 571

    views

  • 2

    users

  • 4

    links

I don’t have any test cases, but if you want to generate some, I’ll run them through my code and compare your answers.

TSHPATH2
SHPATH2

Sorry, I can’t use this. My code uses a trie for the place names, so the names must only contain characters “a” to “z”.

I output -1 if there’s no path. I changed your code slightly so it prints out the result even when there’s no path. Our results start out identical, but then diverge a little.

(The lack of a blank line between data sets had me confused for a short while, but I don’t think that explains the difference.)

Good luck!

-1
-1
450816
-1
-1
-1
75935
-1
85998
101753
-1
135831
-1
-1
-1
236038
-1
-1
-1
-1
304005
-1
264249
289496
-1
200269
-1
-1
-1
77523
128272
-1
327699
-1
-1
569540
120788
-1
-1
-1
-1
-1
-1
355907
-1
-1
-1
344712
-1
-1
-1
-1
-1
-1
-1
-1
-1
64620
-1
-1
-1
-1
-1
-1
157463
-1
-1
-1
-1
-1
184878
-1
-1
-1
-1
193548
182206
-1
129018
-1
237847
-1
-1
-1
-1
-1
-1
-1
338186
45209
82736
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
750323
-1
-1
-1
-1
-1
-1
-1
247750
652806
-1
-1
-1
-1
-1
201767
-1
288761
-1
-1
-1
-1
-1
225695
-1
-1
240611
-1
-1
-1
-1
-1
620028
-1
-1
522752
-1
-1
-1
348250
452418
-1
302163
73307
280385
232556
263153
-1
196751
-1
-1
-1
-1
-1
204349
-1
-1
-1
304600
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
401673
-1
-1
-1
-1
-1
350229
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
673948
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
984749
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
404530
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
715888
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

Diverge? It sounds strange. I’ve got exactly the same output after commenting out line “if (cost >= 0)”

How strange. When I run your code on IDEONE, I get the below result. It differs from line 141 onwards

-1
-1
450816
-1
-1
-1
75935
-1
85998
101753
-1
135831
-1
-1
-1
236038
-1
-1
-1
-1
304005
-1
264249
289496
-1
200269
-1
-1
-1
77523
128272
-1
327699
-1
-1
569540
120788
-1
-1
-1
-1
-1
-1
355907
-1
-1
-1
344712
-1
-1
-1
-1
-1
-1
-1
-1
-1
64620
-1
-1
-1
-1
-1
-1
157463
-1
-1
-1
-1
-1
184878
-1
-1
-1
-1
193548
182206
-1
129018
-1
237847
-1
-1
-1
-1
-1
-1
-1
338186
45209
82736
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
750323
-1
-1
-1
-1
-1
-1
-1
247750
652806
-1
-1
-1
-1
-1
201767
-1
288761
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1

Probably a false alarm. I forgot that IDEONE truncates the input at 64k. I doubt any of your test cases would fit in that limit.

Sorry!

I’ve found an example for small N with the help of Floyd-Warshall. I’m searching for bug in my code now …

diff:

@@ -59,7 +59,7 @@
 53914
 63709
 42241
-100525
+91391
 59527
 0
 59607

test case:

1
20
b
12
2 87236
3 28409
5 165371
7 95610
8 49413
10 87134
11 77270
13 143516
15 109618
16 6322
19 101566
20 139878
c
11
1 87236
4 143523
6 55653
7 144979
11 131706
12 51798
13 63458
14 13578
16 72889
17 70899
19 199235
d
9
1 28409
4 139378
5 80
9 68500
14 131826
15 8906
16 26659
17 90886
19 175887
e
11
2 143523
3 139378
5 104852
6 55744
9 99114
10 33516
14 140920
16 35919
17 76038
18 87356
20 192898
f
11
1 165371
3 80
4 104852
6 128708
8 25440
10 197357
12 185930
14 118902
15 65094
16 170148
17 26291
g
9
2 55653
4 55744
5 128708
13 37030
14 181309
15 40315
16 8953
17 142998
19 74065
h
8
1 95610
2 144979
8 124918
10 14276
14 153344
18 109404
19 158377
20 57709
i
6
1 49413
5 25440
7 124918
10 185404
17 29537
18 108140
j
7
3 68500
4 99114
10 8833
13 10714
15 164772
19 83495
20 28865
ab
12
1 87134
4 33516
5 197357
7 14276
8 185404
9 8833
12 51804
14 44297
15 17105
17 196850
19 134663
20 123015
bb
7
1 77270
2 131706
12 184216
13 64898
14 112569
16 101451
20 152116
cb
10
2 51798
5 185930
10 51804
11 184216
13 116082
16 153428
17 34193
18 198474
19 144502
20 196460
db
11
1 143516
2 63458
6 37030
9 10714
11 64898
12 116082
14 154883
15 193346
16 40999
18 88587
19 22212
eb
12
2 13578
3 131826
4 140920
5 118902
6 181309
7 153344
10 44297
11 112569
13 154883
17 36286
18 192586
20 44388
fb
8
1 109618
3 8906
5 65094
6 40315
9 164772
10 17105
13 193346
18 49995
gb
12
1 6322
2 72889
3 26659
4 35919
5 170148
6 8953
11 101451
12 153428
13 40999
17 169358
18 48734
20 119634
hb
13
2 70899
3 90886
4 76038
5 26291
6 142998
8 29537
10 196850
12 34193
14 36286
16 169358
18 136270
19 27543
20 190406
ib
9
4 87356
7 109404
8 108140
12 198474
13 88587
14 192586
15 49995
16 48734
17 136270
jb
11
1 101566
2 199235
3 175887
6 74065
7 158377
9 83495
10 134663
12 144502
13 22212
17 27543
20 110932
ac
11
1 139878
4 192898
7 57709
9 28865
10 123015
11 152116
12 196460
14 44388
16 119634
17 190406
19 110932
400
b b
b c
b d
b e
b f
b g
b h
b i
b j
b ab
b bb
b cb
b db
b eb
b fb
b gb
b hb
b ib
b jb
b ac
c b
c c
c d
c e
c f
c g
c h
c i
c j
c ab
c bb
c cb
c db
c eb
c fb
c gb
c hb
c ib
c jb
c ac
d b
d c
d d
d e
d f
d g
d h
d i
d j
d ab
d bb
d cb
d db
d eb
d fb
d gb
d hb
d ib
d jb
d ac
e b
e c
e d
e e
e f
e g
e h
e i
e j
e ab
e bb
e cb
e db
e eb
e fb
e gb
e hb
e ib
e jb
e ac
f b
f c
f d
f e
f f
f g
f h
f i
f j
f ab
f bb
f cb
f db
f eb
f fb
f gb
f hb
f ib
f jb
f ac
g b
g c
g d
g e
g f
g g
g h
g i
g j
g ab
g bb
g cb
g db
g eb
g fb
g gb
g hb
g ib
g jb
g ac
h b
h c
h d
h e
h f
h g
h h
h i
h j
h ab
h bb
h cb
h db
h eb
h fb
h gb
h hb
h ib
h jb
h ac
i b
i c
i d
i e
i f
i g
i h
i i
i j
i ab
i bb
i cb
i db
i eb
i fb
i gb
i hb
i ib
i jb
i ac
j b
j c
j d
j e
j f
j g
j h
j i
j j
j ab
j bb
j cb
j db
j eb
j fb
j gb
j hb
j ib
j jb
j ac
ab b
ab c
ab d
ab e
ab f
ab g
ab h
ab i
ab j
ab ab
ab bb
ab cb
ab db
ab eb
ab fb
ab gb
ab hb
ab ib
ab jb
ab ac
bb b
bb c
bb d
bb e
bb f
bb g
bb h
bb i
bb j
bb ab
bb bb
bb cb
bb db
bb eb
bb fb
bb gb
bb hb
bb ib
bb jb
bb ac
cb b
cb c
cb d
cb e
cb f
cb g
cb h
cb i
cb j
cb ab
cb bb
cb cb
cb db
cb eb
cb fb
cb gb
cb hb
cb ib
cb jb
cb ac
db b
db c
db d
db e
db f
db g
db h
db i
db j
db ab
db bb
db cb
db db
db eb
db fb
db gb
db hb
db ib
db jb
db ac
eb b
eb c
eb d
eb e
eb f
eb g
eb h
eb i
eb j
eb ab
eb bb
eb cb
eb db
eb eb
eb fb
eb gb
eb hb
eb ib
eb jb
eb ac
fb b
fb c
fb d
fb e
fb f
fb g
fb h
fb i
fb j
fb ab
fb bb
fb cb
fb db
fb eb
fb fb
fb gb
fb hb
fb ib
fb jb
fb ac
gb b
gb c
gb d
gb e
gb f
gb g
gb h
gb i
gb j
gb ab
gb bb
gb cb
gb db
gb eb
gb fb
gb gb
gb hb
gb ib
gb jb
gb ac
hb b
hb c
hb d
hb e
hb f
hb g
hb h
hb i
hb j
hb ab
hb bb
hb cb
hb db
hb eb
hb fb
hb gb
hb hb
hb ib
hb jb
hb ac
ib b
ib c
ib d
ib e
ib f
ib g
ib h
ib i
ib j
ib ab
ib bb
ib cb
ib db
ib eb
ib fb
ib gb
ib hb
ib ib
ib jb
ib ac
jb b
jb c
jb d
jb e
jb f
jb g
jb h
jb i
jb j
jb ab
jb bb
jb cb
jb db
jb eb
jb fb
jb gb
jb hb
jb ib
jb jb
jb ac
ac b
ac c
ac d
ac e
ac f
ac g
ac h
ac i
ac j
ac ab
ac bb
ac cb
ac db
ac eb
ac fb
ac gb
ac hb
ac ib
ac jb
ac ac
1
20
b
9
3 166167
4 75754
5 130574
8 152346
10 54133
12 74554
13 43787
14 122153
18 113838
c
9
4 125556
5 182053
7 95853
9 45383
10 69413
11 122024
12 129999
14 147203
16 79971
d
11
1 166167
4 49884
5 114669
6 196084
8 140216
9 174414
13 175327
14 25519
16 13475
18 31789
19 59580
e
12
1 75754
2 125556
3 49884
6 87984
9 102968
10 173123
11 86341
13 15742
14 75663
16 101127
17 32402
20 29921
f
11
1 130574
2 182053
3 114669
7 97221
8 2484
10 59910
13 53582
14 2527
15 119351
18 32936
19 133928
g
11
3 196084
4 87984
7 100762
8 110468
9 103045
13 92537
14 95983
15 24413
18 9592
19 180064
20 102353
h
11
2 95853
5 97221
6 100762
9 109382
10 33713
11 92726
15 72092
16 150345
17 19718
18 55993
19 138683
i
9
1 152346
3 140216
5 2484
6 110468
14 92550
16 142960
17 134449
18 139314
19 21410
j
12
2 45383
3 174414
4 102968
6 103045
7 109382
10 43628
12 170766
13 184597
14 177475
15 51918
17 172275
20 43751
ab
10
1 54133
2 69413
4 173123
5 59910
7 33713
9 43628
11 30837
12 101215
13 139168
15 116069
bb
8
2 122024
4 86341
7 92726
10 30837
14 141238
15 2421
18 83638
20 117458
cb
10
1 74554
2 129999
9 170766
10 101215
13 113519
14 128665
15 128413
17 142013
19 6008
20 85108
db
12
1 43787
3 175327
4 15742
5 53582
6 92537
9 184597
10 139168
12 113519
16 57193
17 65936
18 10113
20 194178
eb
15
1 122153
2 147203
3 25519
4 75663
5 2527
6 95983
8 92550
9 177475
11 141238
12 128665
15 23773
16 2046
17 64209
18 112174
20 73286
fb
10
5 119351
6 24413
7 72092
9 51918
10 116069
11 2421
12 128413
14 23773
16 73489
18 66467
gb
9
2 79971
3 13475
4 101127
7 150345
8 142960
13 57193
14 2046
15 73489
20 174434
hb
7
4 32402
7 19718
8 134449
9 172275
12 142013
13 65936
14 64209
ib
12
1 113838
3 31789
5 32936
6 9592
7 55993
8 139314
11 83638
13 10113
14 112174
15 66467
19 169103
20 112215
jb
7
3 59580
5 133928
6 180064
7 138683
8 21410
12 6008
18 169103
ac
9
4 29921
6 102353
9 43751
11 117458
12 85108
13 194178
14 73286
16 174434
18 112215
400
b b
b c
b d
b e
b f
b g
b h
b i
b j
b ab
b bb
b cb
b db
b eb
b fb
b gb
b hb
b ib
b jb
b ac
c b
c c
c d
c e
c f
c g
c h
c i
c j
c ab
c bb
c cb
c db
c eb
c fb
c gb
c hb
c ib
c jb
c ac
d b
d c
d d
d e
d f
d g
d h
d i
d j
d ab
d bb
d cb
d db
d eb
d fb
d gb
d hb
d ib
d jb
d ac
e b
e c
e d
e e
e f
e g
e h
e i
e j
e ab
e bb
e cb
e db
e eb
e fb
e gb
e hb
e ib
e jb
e ac
f b
f c
f d
f e
f f
f g
f h
f i
f j
f ab
f bb
f cb
f db
f eb
f fb
f gb
f hb
f ib
f jb
f ac
g b
g c
g d
g e
g f
g g
g h
g i
g j
g ab
g bb
g cb
g db
g eb
g fb
g gb
g hb
g ib
g jb
g ac
h b
h c
h d
h e
h f
h g
h h
h i
h j
h ab
h bb
h cb
h db
h eb
h fb
h gb
h hb
h ib
h jb
h ac
i b
i c
i d
i e
i f
i g
i h
i i
i j
i ab
i bb
i cb
i db
i eb
i fb
i gb
i hb
i ib
i jb
i ac
j b
j c
j d
j e
j f
j g
j h
j i
j j
j ab
j bb
j cb
j db
j eb
j fb
j gb
j hb
j ib
j jb
j ac
ab b
ab c
ab d
ab e
ab f
ab g
ab h
ab i
ab j
ab ab
ab bb
ab cb
ab db
ab eb
ab fb
ab gb
ab hb
ab ib
ab jb
ab ac
bb b
bb c
bb d
bb e
bb f
bb g
bb h
bb i
bb j
bb ab
bb bb
bb cb
bb db
bb eb
bb fb
bb gb
bb hb
bb ib
bb jb
bb ac
cb b
cb c
cb d
cb e
cb f
cb g
cb h
cb i
cb j
cb ab
cb bb
cb cb
cb db
cb eb
cb fb
cb gb
cb hb
cb ib
cb jb
cb ac
db b
db c
db d
db e
db f
db g
db h
db i
db j
db ab
db bb
db cb
db db
db eb
db fb
db gb
db hb
db ib
db jb
db ac
eb b
eb c
eb d
eb e
eb f
eb g
eb h
eb i
eb j
eb ab
eb bb
eb cb
eb db
eb eb
eb fb
eb gb
eb hb
eb ib
eb jb
eb ac
fb b
fb c
fb d
fb e
fb f
fb g
fb h
fb i
fb j
fb ab
fb bb
fb cb
fb db
fb eb
fb fb
fb gb
fb hb
fb ib
fb jb
fb ac
gb b
gb c
gb d
gb e
gb f
gb g
gb h
gb i
gb j
gb ab
gb bb
gb cb
gb db
gb eb
gb fb
gb gb
gb hb
gb ib
gb jb
gb ac
hb b
hb c
hb d
hb e
hb f
hb g
hb h
hb i
hb j
hb ab
hb bb
hb cb
hb db
hb eb
hb fb
hb gb
hb hb
hb ib
hb jb
hb ac
ib b
ib c
ib d
ib e
ib f
ib g
ib h
ib i
ib j
ib ab
ib bb
ib cb
ib db
ib eb
ib fb
ib gb
ib hb
ib ib
ib jb
ib ac
jb b
jb c
jb d
jb e
jb f
jb g
jb h
jb i
jb j
jb ab
jb bb
jb cb
jb db
jb eb
jb fb
jb gb
jb hb
jb ib
jb jb
jb ac
ac b
ac c
ac d
ac e
ac f
ac g
ac h
ac i
ac j
ac ab
ac bb
ac cb
ac db
ac eb
ac fb
ac gb
ac hb
ac ib
ac jb
ac ac
1
20
b
11
2 54410
3 53905
4 132721
6 75150
7 28685
8 39131
9 89682
14 166020
15 91882
18 4528
20 151520
c
11
1 54410
3 120331
4 32257
9 76125
11 8720
14 150693
16 142853
17 147223
18 112416
19 138252
20 154
d
12
1 53905
2 120331
4 17880
5 124281
8 112010
9 155447
10 60934
13 113525
16 38090
18 116270
19 183539
20 66137
e
11
1 132721
2 32257
3 17880
5 11750
7 85015
8 177610
9 10983
10 177406
11 33821
13 14204
17 191662
f
13
3 124281
4 11750
6 166500
7 192862
8 25210
9 57266
10 167566
11 50039
12 40729
14 48960
15 154528
17 2278
20 11224
g
12
1 75150
5 166500
7 101992
8 67799
10 158946
11 77633
12 156508
15 127821
16 87935
17 116380
18 34289
20 100342
h
9
1 28685
4 85015
5 192862
6 101992
10 15582
15 106905
17 31606
18 2498
20 56042
i
11
1 39131
3 112010
4 177610
5 25210
6 67799
13 139883
14 102253
16 34458
18 35160
19 62739
20 68528
j
9
1 89682
2 76125
3 155447
4 10983
5 57266
12 32405
13 182146
16 155900
18 47991
ab
11
3 60934
4 177406
5 167566
6 158946
7 15582
11 120981
12 988
14 77234
16 78030
18 174289
20 66102
bb
9
2 8720
4 33821
5 50039
6 77633
10 120981
13 133864
15 123630
19 90057
20 131797
cb
9
5 40729
6 156508
9 32405
10 988
14 162137
15 70839
17 31946
18 142241
19 66297
db
9
3 113525
4 14204
8 139883
9 182146
11 133864
15 191888
16 139867
17 184045
19 23384
eb
10
1 166020
2 150693
5 48960
8 102253
10 77234
12 162137
15 172627
16 137107
18 147640
19 126657
fb
11
1 91882
5 154528
6 127821
7 106905
11 123630
12 70839
13 191888
14 172627
16 40833
18 144781
20 192907
gb
12
2 142853
3 38090
6 87935
8 34458
9 155900
10 78030
13 139867
14 137107
15 40833
17 187174
18 153199
19 70016
hb
10
2 147223
4 191662
5 2278
6 116380
7 31606
12 31946
13 184045
16 187174
19 172701
20 161632
ib
13
1 4528
2 112416
3 116270
6 34289
7 2498
8 35160
9 47991
10 174289
12 142241
14 147640
15 144781
16 153199
19 112659
jb
11
2 138252
3 183539
8 62739
11 90057
12 66297
13 23384
14 126657
16 70016
17 172701
18 112659
20 87836
ac
12
1 151520
2 154
3 66137
5 11224
6 100342
7 56042
8 68528
10 66102
11 131797
15 192907
17 161632
19 87836
400
b b
b c
b d
b e
b f
b g
b h
b i
b j
b ab
b bb
b cb
b db
b eb
b fb
b gb
b hb
b ib
b jb
b ac
c b
c c
c d
c e
c f
c g
c h
c i
c j
c ab
c bb
c cb
c db
c eb
c fb
c gb
c hb
c ib
c jb
c ac
d b
d c
d d
d e
d f
d g
d h
d i
d j
d ab
d bb
d cb
d db
d eb
d fb
d gb
d hb
d ib
d jb
d ac
e b
e c
e d
e e
e f
e g
e h
e i
e j
e ab
e bb
e cb
e db
e eb
e fb
e gb
e hb
e ib
e jb
e ac
f b
f c
f d
f e
f f
f g
f h
f i
f j
f ab
f bb
f cb
f db
f eb
f fb
f gb
f hb
f ib
f jb
f ac
g b
g c
g d
g e
g f
g g
g h
g i
g j
g ab
g bb
g cb
g db
g eb
g fb
g gb
g hb
g ib
g jb
g ac
h b
h c
h d
h e
h f
h g
h h
h i
h j
h ab
h bb
h cb
h db
h eb
h fb
h gb
h hb
h ib
h jb
h ac
i b
i c
i d
i e
i f
i g
i h
i i
i j
i ab
i bb
i cb
i db
i eb
i fb
i gb
i hb
i ib
i jb
i ac
j b
j c
j d
j e
j f
j g
j h
j i
j j
j ab
j bb
j cb
j db
j eb
j fb
j gb
j hb
j ib
j jb
j ac
ab b
ab c
ab d
ab e
ab f
ab g
ab h
ab i
ab j
ab ab
ab bb
ab cb
ab db
ab eb
ab fb
ab gb
ab hb
ab ib
ab jb
ab ac
bb b
bb c
bb d
bb e
bb f
bb g
bb h
bb i
bb j
bb ab
bb bb
bb cb
bb db
bb eb
bb fb
bb gb
bb hb
bb ib
bb jb
bb ac
cb b
cb c
cb d
cb e
cb f
cb g
cb h
cb i
cb j
cb ab
cb bb
cb cb
cb db
cb eb
cb fb
cb gb
cb hb
cb ib
cb jb
cb ac
db b
db c
db d
db e
db f
db g
db h
db i
db j
db ab
db bb
db cb
db db
db eb
db fb
db gb
db hb
db ib
db jb
db ac
eb b
eb c
eb d
eb e
eb f
eb g
eb h
eb i
eb j
eb ab
eb bb
eb cb
eb db
eb eb
eb fb
eb gb
eb hb
eb ib
eb jb
eb ac
fb b
fb c
fb d
fb e
fb f
fb g
fb h
fb i
fb j
fb ab
fb bb
fb cb
fb db
fb eb
fb fb
fb gb
fb hb
fb ib
fb jb
fb ac
gb b
gb c
gb d
gb e
gb f
gb g
gb h
gb i
gb j
gb ab
gb bb
gb cb
gb db
gb eb
gb fb
gb gb
gb hb
gb ib
gb jb
gb ac
hb b
hb c
hb d
hb e
hb f
hb g
hb h
hb i
hb j
hb ab
hb bb
hb cb
hb db
hb eb
hb fb
hb gb
hb hb
hb ib
hb jb
hb ac
ib b
ib c
ib d
ib e
ib f
ib g
ib h
ib i
ib j
ib ab
ib bb
ib cb
ib db
ib eb
ib fb
ib gb
ib hb
ib ib
ib jb
ib ac
jb b
jb c
jb d
jb e
jb f
jb g
jb h
jb i
jb j
jb ab
jb bb
jb cb
jb db
jb eb
jb fb
jb gb
jb hb
jb ib
jb jb
jb ac
ac b
ac c
ac d
ac e
ac f
ac g
ac h
ac i
ac j
ac ab
ac bb
ac cb
ac db
ac eb
ac fb
ac gb
ac hb
ac ib
ac jb
ac ac
1
20
b
9
3 126927
4 137335
6 146387
7 97746
8 91023
11 65526
16 133641
17 50704
18 78193
c
10
3 84097
5 56908
7 179119
11 183673
14 110880
15 82599
17 94394
18 98572
19 16374
20 182556
d
12
1 126927
2 84097
4 26191
5 146070
7 161749
8 36729
11 141009
12 93891
14 131
15 83644
16 191250
19 129844
e
12
1 137335
3 26191
5 21972
6 163202
7 189460
8 171451
9 65312
10 98415
13 88317
14 131714
16 13589
20 17338
f
12
2 56908
3 146070
4 21972
7 142920
8 1941
10 68750
11 34429
12 106252
13 195639
16 34982
18 26561
19 15491
g
9
1 146387
4 163202
7 70418
11 6523
12 59090
13 112035
16 35420
17 2663
18 11071
h
12
1 97746
2 179119
3 161749
4 189460
5 142920
6 70418
9 71845
14 11462
15 40964
16 130621
17 100071
18 5372
i
13
1 91023
3 36729
4 171451
5 1941
9 98044
10 27975
11 30389
13 52501
15 181357
16 168939
17 98565
18 34450
20 187499
j
8
4 65312
7 71845
8 98044
10 93928
12 31110
16 187428
19 146156
20 39069
ab
9
4 98415
5 68750
8 27975
9 93928
12 28336
16 114065
18 14067
19 127910
20 12655
bb
14
1 65526
2 183673
3 141009
5 34429
6 6523
8 30389
12 3137
13 178054
14 92413
15 27849
16 50291
17 173015
18 100251
20 158602
cb
14
3 93891
5 106252
6 59090
9 31110
10 28336
11 3137
13 62294
14 77722
15 129958
16 19942
17 78142
18 9604
19 175382
20 195885
db
11
4 88317
5 195639
6 112035
8 52501
11 178054
12 62294
15 1190
16 165162
17 54145
18 25531
19 170532
eb
7
2 110880
3 131
4 131714
7 11462
11 92413
12 77722
20 151653
fb
10
2 82599
3 83644
7 40964
8 181357
11 27849
12 129958
13 1190
17 185215
18 131226
20 149595
gb
15
1 133641
3 191250
4 13589
5 34982
6 35420
7 130621
8 168939
9 187428
10 114065
11 50291
12 19942
13 165162
17 113190
18 102316
20 152088
hb
10
1 50704
2 94394
6 2663
7 100071
8 98565
11 173015
12 78142
13 54145
15 185215
16 113190
ib
14
1 78193
2 98572
5 26561
6 11071
7 5372
8 34450
10 14067
11 100251
12 9604
13 25531
15 131226
16 102316
19 50123
20 12755
jb
9
2 16374
3 129844
5 15491
9 146156
10 127910
12 175382
13 170532
18 50123
20 159131
ac
12
2 182556
4 17338
8 187499
9 39069
10 12655
11 158602
12 195885
14 151653
15 149595
16 152088
18 12755
19 159131
400
b b
b c
b d
b e
b f
b g
b h
b i
b j
b ab
b bb
b cb
b db
b eb
b fb
b gb
b hb
b ib
b jb
b ac
c b
c c
c d
c e
c f
c g
c h
c i
c j
c ab
c bb
c cb
c db
c eb
c fb
c gb
c hb
c ib
c jb
c ac
d b
d c
d d
d e
d f
d g
d h
d i
d j
d ab
d bb
d cb
d db
d eb
d fb
d gb
d hb
d ib
d jb
d ac
e b
e c
e d
e e
e f
e g
e h
e i
e j
e ab
e bb
e cb
e db
e eb
e fb
e gb
e hb
e ib
e jb
e ac
f b
f c
f d
f e
f f
f g
f h
f i
f j
f ab
f bb
f cb
f db
f eb
f fb
f gb
f hb
f ib
f jb
f ac
g b
g c
g d
g e
g f
g g
g h
g i
g j
g ab
g bb
g cb
g db
g eb
g fb
g gb
g hb
g ib
g jb
g ac
h b
h c
h d
h e
h f
h g
h h
h i
h j
h ab
h bb
h cb
h db
h eb
h fb
h gb
h hb
h ib
h jb
h ac
i b
i c
i d
i e
i f
i g
i h
i i
i j
i ab
i bb
i cb
i db
i eb
i fb
i gb
i hb
i ib
i jb
i ac
j b
j c
j d
j e
j f
j g
j h
j i
j j
j ab
j bb
j cb
j db
j eb
j fb
j gb
j hb
j ib
j jb
j ac
ab b
ab c
ab d
ab e
ab f
ab g
ab h
ab i
ab j
ab ab
ab bb
ab cb
ab db
ab eb
ab fb
ab gb
ab hb
ab ib
ab jb
ab ac
bb b
bb c
bb d
bb e
bb f
bb g
bb h
bb i
bb j
bb ab
bb bb
bb cb
bb db
bb eb
bb fb
bb gb
bb hb
bb ib
bb jb
bb ac
cb b
cb c
cb d
cb e
cb f
cb g
cb h
cb i
cb j
cb ab
cb bb
cb cb
cb db
cb eb
cb fb
cb gb
cb hb
cb ib
cb jb
cb ac
db b
db c
db d
db e
db f
db g
db h
db i
db j
db ab
db bb
db cb
db db
db eb
db fb
db gb
db hb
db ib
db jb
db ac
eb b
eb c
eb d
eb e
eb f
eb g
eb h
eb i
eb j
eb ab
eb bb
eb cb
eb db
eb eb
eb fb
eb gb
eb hb
eb ib
eb jb
eb ac
fb b
fb c
fb d
fb e
fb f
fb g
fb h
fb i
fb j
fb ab
fb bb
fb cb
fb db
fb eb
fb fb
fb gb
fb hb
fb ib
fb jb
fb ac
gb b
gb c
gb d
gb e
gb f
gb g
gb h
gb i
gb j
gb ab
gb bb
gb cb
gb db
gb eb
gb fb
gb gb
gb hb
gb ib
gb jb
gb ac
hb b
hb c
hb d
hb e
hb f
hb g
hb h
hb i
hb j
hb ab
hb bb
hb cb
hb db
hb eb
hb fb
hb gb
hb hb
hb ib
hb jb
hb ac
ib b
ib c
ib d
ib e
ib f
ib g
ib h
ib i
ib j
ib ab
ib bb
ib cb
ib db
ib eb
ib fb
ib gb
ib hb
ib ib
ib jb
ib ac
jb b
jb c
jb d
jb e
jb f
jb g
jb h
jb i
jb j
jb ab
jb bb
jb cb
jb db
jb eb
jb fb
jb gb
jb hb
jb ib
jb jb
jb ac
ac b
ac c
ac d
ac e
ac f
ac g
ac h
ac i
ac j
ac ab
ac bb
ac cb
ac db
ac eb
ac fb
ac gb
ac hb
ac ib
ac jb
ac ac
1
20
b
9
6 157298
7 101820
9 164164
10 15306
11 144072
12 175383
14 122354
17 198161
20 123244
c
10
3 163990
4 168694
6 95310
7 50244
8 123152
11 12571
13 198634
14 55192
15 132770
19 73660
d
9
2 163990
5 33811
6 83392
7 133784
8 53332
11 24778
13 140636
14 199139
17 197007
e
12
2 168694
5 46515
6 177571
8 192124
9 75009
11 26168
12 145488
15 114150
16 181659
18 112958
19 9133
20 73984
f
8
3 33811
4 46515
7 36245
11 176983
16 143622
18 155122
19 80456
20 131491
g
10
1 157298
2 95310
3 83392
4 177571
8 196533
9 141432
11 113957
15 46157
17 114641
19 118767
h
9
1 101820
2 50244
3 133784
5 36245
9 146204
12 140132
13 65247
17 95845
18 167618
i
10
2 123152
3 53332
4 192124
6 196533
10 184284
11 22978
12 173751
13 160433
15 154609
19 151663
j
11
1 164164
4 75009
6 141432
7 146204
10 175325
13 175678
14 18749
15 175797
16 12081
17 8321
19 62496
ab
8
1 15306
8 184284
9 175325
13 124566
15 125957
16 179919
17 199308
20 113355
bb
10
1 144072
2 12571
3 24778
4 26168
5 176983
6 113957
8 22978
12 178257
15 66632
18 189611
cb
9
1 175383
4 145488
7 140132
8 173751
11 178257
13 24209
14 191483
15 166708
20 157633
db
9
2 198634
3 140636
7 65247
8 160433
9 175678
10 124566
12 24209
16 7036
17 25282
eb
6
1 122354
2 55192
3 199139
9 18749
12 191483
18 7546
fb
12
2 132770
4 114150
6 46157
8 154609
9 175797
10 125957
11 66632
12 166708
17 81528
18 49416
19 54491
20 42900
gb
6
4 181659
5 143622
9 12081
10 179919
13 7036
18 34058
hb
10
1 198161
3 197007
6 114641
7 95845
9 8321
10 199308
13 25282
15 81528
19 85245
20 124337
ib
8
4 112958
5 155122
7 167618
11 189611
14 7546
15 49416
16 34058
19 82016
jb
9
2 73660
4 9133
5 80456
6 118767
8 151663
9 62496
15 54491
17 85245
18 82016
ac
7
1 123244
4 73984
5 131491
10 113355
12 157633
15 42900
17 124337
400
b b
b c
b d
b e
b f
b g
b h
b i
b j
b ab
b bb
b cb
b db
b eb
b fb
b gb
b hb
b ib
b jb
b ac
c b
c c
c d
c e
c f
c g
c h
c i
c j
c ab
c bb
c cb
c db
c eb
c fb
c gb
c hb
c ib
c jb
c ac
d b
d c
d d
d e
d f
d g
d h
d i
d j
d ab
d bb
d cb
d db
d eb
d fb
d gb
d hb
d ib
d jb
d ac
e b
e c
e d
e e
e f
e g
e h
e i
e j
e ab
e bb
e cb
e db
e eb
e fb
e gb
e hb
e ib
e jb
e ac
f b
f c
f d
f e
f f
f g
f h
f i
f j
f ab
f bb
f cb
f db
f eb
f fb
f gb
f hb
f ib
f jb
f ac
g b
g c
g d
g e
g f
g g
g h
g i
g j
g ab
g bb
g cb
g db
g eb
g fb
g gb
g hb
g ib
g jb
g ac
h b
h c
h d
h e
h f
h g
h h
h i
h j
h ab
h bb
h cb
h db
h eb
h fb
h gb
h hb
h ib
h jb
h ac
i b
i c
i d
i e
i f
i g
i h
i i
i j
i ab
i bb
i cb
i db
i eb
i fb
i gb
i hb
i ib
i jb
i ac
j b
j c
j d
j e
j f
j g
j h
j i
j j
j ab
j bb
j cb
j db
j eb
j fb
j gb
j hb
j ib
j jb
j ac
ab b
ab c
ab d
ab e
ab f
ab g
ab h
ab i
ab j
ab ab
ab bb
ab cb
ab db
ab eb
ab fb
ab gb
ab hb
ab ib
ab jb
ab ac
bb b
bb c
bb d
bb e
bb f
bb g
bb h
bb i
bb j
bb ab
bb bb
bb cb
bb db
bb eb
bb fb
bb gb
bb hb
bb ib
bb jb
bb ac
cb b
cb c
cb d
cb e
cb f
cb g
cb h
cb i
cb j
cb ab
cb bb
cb cb
cb db
cb eb
cb fb
cb gb
cb hb
cb ib
cb jb
cb ac
db b
db c
db d
db e
db f
db g
db h
db i
db j
db ab
db bb
db cb
db db
db eb
db fb
db gb
db hb
db ib
db jb
db ac
eb b
eb c
eb d
eb e
eb f
eb g
eb h
eb i
eb j
eb ab
eb bb
eb cb
eb db
eb eb
eb fb
eb gb
eb hb
eb ib
eb jb
eb ac
fb b
fb c
fb d
fb e
fb f
fb g
fb h
fb i
fb j
fb ab
fb bb
fb cb
fb db
fb eb
fb fb
fb gb
fb hb
fb ib
fb jb
fb ac
gb b
gb c
gb d
gb e
gb f
gb g
gb h
gb i
gb j
gb ab
gb bb
gb cb
gb db
gb eb
gb fb
gb gb
gb hb
gb ib
gb jb
gb ac
hb b
hb c
hb d
hb e
hb f
hb g
hb h
hb i
hb j
hb ab
hb bb
hb cb
hb db
hb eb
hb fb
hb gb
hb hb
hb ib
hb jb
hb ac
ib b
ib c
ib d
ib e
ib f
ib g
ib h
ib i
ib j
ib ab
ib bb
ib cb
ib db
ib eb
ib fb
ib gb
ib hb
ib ib
ib jb
ib ac
jb b
jb c
jb d
jb e
jb f
jb g
jb h
jb i
jb j
jb ab
jb bb
jb cb
jb db
jb eb
jb fb
jb gb
jb hb
jb ib
jb jb
jb ac
ac b
ac c
ac d
ac e
ac f
ac g
ac h
ac i
ac j
ac ab
ac bb
ac cb
ac db
ac eb
ac fb
ac gb
ac hb
ac ib
ac jb
ac ac