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
#include "message.h"
#include <cstdio>
#include <algorithm>
using namespace std;
char s1[100001],s2[100001];
int wyndol[100001][2];
pair<int, int> tab1[100001], tab2[100001];
int main(){
int n,m;
scanf("%d%d", &n, &m);
scanf("%s%s", s1,s2);
	int ile=NumberOfNodes();
	int x=MyNodeId();
	int p=m/ile;
	p*=x;
	p++;
	int k=m/ile;
	k*=(x+1);
	if(x==ile-1)
	k=m;
	int wyslij=n/900;
	if(wyslij==0)
	wyslij=1;
	for(int j=p-1; j<=k; j++)
		tab1[j]=make_pair(j,0);
	if(x!=0 && x!=ile-1){
	for(int i=1; i<=n; i++){
		if((i-1)%wyslij==0 || i==1)
		Receive(x-1);
		tab2[p-1]=make_pair(GetInt(x-1), GetInt(x-1));
		for(int j=p; j<=k; j++){
			if(s1[i-1]==s2[j-1]){
				tab2[j]=tab1[j-1];
				} else{
						if(tab1[j-1]<tab2[j-1] && tab1[j-1]<tab1[j]){
							tab2[j]=tab1[j-1];
							tab2[j].first++;
							if(s1[i-1]<s2[j-1])
							tab2[j].second++;
							} else{
								tab2[j]=min(tab1[j], tab2[j-1]);
								tab2[j].first++;
								}
						}	
			
			}
		//	if(x==1){
		//	printf("%d %d\n",tab2[k].first, tab2[k].second);
			//	}
			PutInt(x+1, tab2[k].second);
			PutInt(x+1, tab2[k].first);
			for(int j=p-1; j<=k; j++)
				tab1[j]=tab2[j];
		if(i%wyslij==0 || i==n)
		Send(x+1);
	}
		}
	if(x==0){
		//printf("%d %d %d", x, p, k);
		for(int i=1; i<=n; i++){
		tab2[p-1]=make_pair(i, 0);
		for(int j=p; j<=k; j++){
			if(s1[i-1]==s2[j-1]){
				tab2[j]=tab1[j-1];
				} else{
						if(tab1[j-1]<tab2[j-1] && tab1[j-1]<tab1[j]){
							tab2[j]=tab1[j-1];
							tab2[j].first++;
							if(s1[i-1]<s2[j-1])
							tab2[j].second++;
							} else{
								tab2[j]=min(tab1[j], tab2[j-1]);
								tab2[j].first++;
								}
						}	
			}
		PutInt(1, tab2[k].second);
		PutInt(1, tab2[k].first);
		//printf("%d %d\n", tab2[k].first, tab2[k].second);
			for(int j=p-1; j<=k; j++)
				tab1[j]=tab2[j];
		if(i%wyslij==0 || i==n)
		Send(1);
	}
}
	if(x==ile-1){
		for(int i=1; i<=n; i++){
		if((i-1)%wyslij==0)
		Receive(x-1);
		tab2[p-1]=make_pair(GetInt(x-1), GetInt(x-1));
		for(int j=p; j<=k; j++){
			if(s1[i-1]==s2[j-1]){
				tab2[j]=tab1[j-1];
				} else{
						if(tab1[j-1]<tab2[j-1] && tab1[j-1]<tab1[j]){
							tab2[j]=tab1[j-1];
							tab2[j].first++;
							if(s1[i-1]<s2[j-1])
							tab2[j].second++;
							} else{
								tab2[j]=min(tab1[j], tab2[j-1]);
								tab2[j].first++;
								}
						}	
			}
			for(int j=p-1; j<=k; j++)
				tab1[j]=tab2[j];
		}
		printf("%d %d", tab1[m].first, tab1[m].second);
		}
		
}