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
#include<stdio.h>
#include "message.h"
#include<cstring>
#include<algorithm>
using namespace std;

int n,m;
char P[100010];
char R[100010];
int q, id;

long long int T[100010];
long long int TT[100010];

long long int Z[100010][2];

int main() {
    q = NumberOfNodes();
    id = MyNodeId();

    scanf("%d %d", &n, &m);
    scanf("%s", P);
    scanf("%s", R);

    for(int i=0;i<=n;i++)
        T[i] = i * 1000000;
    for(int i=0;i<=m;i++)
        TT[i] = i * 1000000;

    int y = m/q;

    if(y < 2) {
        q = 1;
        y = m;
        if(id > 0) return 0;
    }

    int x = n/500;

    if(x == 0) x = n/q;
    if(x == 0) x = n;

    int y2 = y;
    if(id == q-1)
        y2 += m%q;

    int c; 

    for(int i=0;i<=y2;i++) {
        Z[i][0] = TT[id*y + i];
    }

    for(int i=1;i<=n;i++) {
        if(id != 0) {
            if((i-1)%x == 0) {
                Receive(id - 1);
//                printf("RECEIVED\n");
            }
//            printf("READ\n");
            Z[0][1] = GetLL(id-1);
        }
        else {
            Z[0][1] = T[i];
        }


        for(int j=1; j<=y2; j++) {
            if(P[i - 1] == R[y*id + j - 1]) c = 0;
            else if(P[i - 1] <= R[y*id + j - 1]) c = 1000001;
            else c = 1000000;

            Z[j][1] = min(min(Z[j-1][1] + 1000000, Z[j][0] + 1000000), Z[j-1][0] + c);
        }

        if(id != q-1) {
//            printf("PUT\n");
            PutLL(id+1, Z[y2][1]);
            if((i > 1 && i%x==0) || i == n) {
//                printf("SEND\n");
                Send(id+1);
            }
        }
        for(int j=0;j<=y2;j++)
            Z[j][0] = Z[j][1];
    }

    if(id == q-1) {
        printf("%lld %lld\n", Z[y2][0]/1000000, Z[y2][0]%1000000);
    }

    return 0;
}