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
#include <algorithm> 
#include <cstdio> 
#include <utility> 
#include "message.h"

const int N = 100002;
const int MAX_MESSAGES = 1000;

char orig[N], dest[N];

int x1, x2;

std::pair<int, int> row[N][2], column[2][N];

inline std::pair<int, int> &dp(int x, int y){
	return (x < x1) ? column[0][y]:row[x][y & 1];
}


int main(){
	int nNodes = NumberOfNodes();
	int myNodeId = MyNodeId();
	
	int n, m;
	scanf("%d%d", &n, &m);
	scanf("%s", orig + 1);
	scanf("%s", dest + 1);
	
	const int nMessages = std::min(MAX_MESSAGES, m);
	x1 = 1 + (n * myNodeId) / nNodes; 
	x2 = 1 + (n * (myNodeId + 1)) / nNodes;
	
	column[0][0] = {x1 - 1, 0};
	
	
	if(myNodeId == 0) 
		for(int y = 0; y <= m; y++) 
			column[0][y] = {y, 0};
	
	for(int x = x1; x < x2; ++x)
		row[x][0] = {x, 0};
	
	for(int i = 0; i < nMessages; i++){
		
		int y1 = 1 + (m * i) / nMessages;
		int y2 = 1 + (m * (i + 1)) / nMessages;
		
		if(myNodeId){
			Receive(myNodeId - 1);
			for(int y = y1; y < y2; ++y){
				column[0][y].first = GetInt(myNodeId - 1);
				column[0][y].second = GetInt(myNodeId - 1);
			}
		}
		for(int y = y1; y < y2; ++y){
			for(int x = x1; x < x2; x++){
				dp(x, y) = dp(x - 1, y - 1);
				
				if(orig[x] != dest[y]){
					dp(x, y).first++;
					dp(x, y).second += (orig[x] < dest[y]); // nie na odwrót?
				
					dp(x - 1, y).first++;
					dp(x, y) = std::min(dp(x, y), dp(x - 1, y));
					dp(x - 1, y).first--;
				
					dp(x, y - 1).first++;
					dp(x, y) = std::min(dp(x, y), dp(x, y - 1));
					dp(x, y - 1).first--;
				}
			}
			column[1][y] = dp(x2 - 1, y);
		}
		if(myNodeId != nNodes - 1) {
			for(int y = y1; y < y2; ++y){
				PutInt(myNodeId + 1, column[1][y].first);
				PutInt(myNodeId + 1, column[1][y].second);
			}
			Send(myNodeId + 1);
		}
	}
	if(myNodeId == nNodes - 1)
		printf("%d %d\n", dp(n, m).first, dp(n, m).second);
	return 0;
}