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
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <algorithm>


#include "message.h"

using namespace std;

void recPut(int target, int x) {
	PutInt(target, x);
}

template<class T, class U>
void recPut(int target, const pair<T, U>& x) {
	recPut(target, x.first);
	recPut(target, x.second);
}

template<class T>
void recPut(int target, const vector<T>& V) {
	PutInt(target, V.size());
	for (auto& x:V) recPut(target, x);
}

void recGet(int target, int& x) {
	x=GetInt(target);
}

template<class T, class U>
void recGet(int target, pair<T, U>& x) {
	recGet(target, x.first);
	recGet(target, x.second);
}

template<class T>
void recGet(int target, vector<T>& V) {
	V.resize(GetInt(target));
	for (auto& x:V) recGet(target, x);
}



int main() {
	int nodeCnt=NumberOfNodes();
	int nodeId=MyNodeId();
	
	int N, M;
	bool r=false;
	scanf("%d%d", &N, &M);
	if (N>M) {
		r=true;
		swap(N, M);
	}
	
	char A[110000];
	char B[110000];
	pair <int, int> R[110000];
	
	if (!r) scanf("%s%s", A, B);
	else scanf("%s%s", B, A);
	
	int xStep=max(10, (N+nodeCnt-1)/nodeCnt);
	int yStep=max(10, M/800);
	int X=(N+xStep-1)/xStep;
	int Y=(M+yStep-1)/yStep;
	
	if (nodeId>=X) return 0;
	
	for (int i=0; i<=xStep; i++)
		R[i]=make_pair(i+nodeId*xStep,0);
	
	char *T=A+nodeId*xStep;
	pair<int, int> res;
	
	
	if (nodeId==X-1 && N%xStep!=0) xStep=N%xStep; // <- !!!
	
	for (int y=0, s=0; y<M; y++, s=(s+1)%yStep) {
		if (nodeId==0) res=make_pair(y+1,0);
		else {
			if (!s) Receive(nodeId-1);
			recGet(nodeId-1, res);
		}
		
		for (int x=0; x<xStep; x++) {
			pair<int, int> newRes=(R[x]);
			if (T[x]!=B[y]) {
				newRes.first++;
				if ((!r) && T[x]<B[y]) newRes.second++;
				if ((r) && T[x]>B[y]) newRes.second++;
			}
			newRes=min(newRes, make_pair(res.first+1, res.second));
			newRes=min(newRes, make_pair(R[x+1].first+1, R[x+1].second));
			
			R[x]=res;
			res=newRes;
		}
		R[xStep]=res;
		if (nodeId<X-1) {
			recPut(nodeId+1, res);
			if (s==yStep-1 || y==M-1) Send(nodeId+1);
		}
	}
	
	if (nodeId==X-1) {
//		printf("Node: %d %d %d\n", nodeId, xStep, yStep);
		printf("%d %d\n", res.first, res.second);
	}
	
	return 0;
}