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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define VI vector<int>
#define PII pair<int,int>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define lint long long int
#define max_m 105
#define max_n 100005
#define DEBUG 0

using namespace std;

PII inc(PII a){
	return mp(a.st+1,a.nd);
}

int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	char s1[max_n],s2[max_n];
	scanf("%s",s1);
	scanf("%s",s2);
	int x = NumberOfNodes();
	int skok1 = (n+x)/x;
	int skok2 = (m+x)/x;
	int lb = 0, ub = 0;
	int mojafaza = 0;
	vector<PII> lewo,nowelewo;
	FOR(faza,0,2*x-1){
		PII dp[2][max_n];
		int lewopoz = 0;
		int akt = 0;
		if(MyNodeId()>=lb && MyNodeId()<=ub){
			if(DEBUG && MyNodeId()==1)  cout<<"FAZA "<<mojafaza<<" goscia "<<MyNodeId()<<" pracuja "<<lb<<" "<<ub<<endl;
			lewo = nowelewo; 
			nowelewo.clear();
			
			if(MyNodeId()==0){
				FOR(i,1,skok1+1) dp[1][i]  = mp(mojafaza*skok1+i,0);	
				nowelewo.pb(dp[1][skok1]);
			}
			else{
				Receive(MyNodeId()-1);
				FOR(i,0,skok1+1){
					dp[1][i].st = GetInt(MyNodeId()-1); 
					dp[1][i].nd = GetInt(MyNodeId()-1); 
					if(DEBUG) cout<<"OTRZYMALEM "<<dp[1][i].st<<" "<<endl;
				}
				nowelewo.pb(dp[1][skok1]);
			}
			if(lewo.size()==0){
				FOR(i,0,skok2+1) lewo.pb( mp(i+skok2*MyNodeId(),0));
			}
			if(DEBUG){
			if(MyNodeId()==1){
				cout<<"W FAZIE "<<mojafaza<<" lewo to "<<endl;
				FOR(i,0,lewo.size()) cout<<lewo[i].st<<" ";
				cout<<endl;
			}
			}
			dp[1][0] = lewo[lewopoz++];
			FOR(j,1,skok2+1){
				dp[akt][0] = lewo[lewopoz++];
				FOR(i,1,skok1+1){
					int poz1 = mojafaza*skok1+i;
					int poz2 = MyNodeId()*skok2+j;
				if(DEBUG)	if(MyNodeId()==1)
					cout<<"JESTEM "<<MyNodeId()<<" Pracuje nad "<<poz1<<" "<<poz2<<endl;
					if(poz1 > n || poz2 > m) continue;
					if(s1[poz1-1]==s2[poz2-1]) dp[akt][i] = dp[1-akt][i-1];
					else{
						dp[akt][i] = inc(min(dp[akt][i-1],dp[1-akt][i]));
						PII pos = mp(dp[1-akt][i-1].st+1,dp[1-akt][i-1].nd+(s1[poz1-1]<s2[poz2-1] ? 1 : 0));
						if(pos < dp[akt][i]) dp[akt][i] = pos; 
					}
					if(poz1==n && poz2==m) printf("%d %d\n",dp[akt][i].st,dp[akt][i].nd);
				if(DEBUG) if(MyNodeId()==1)	cout<<"dp["<<poz1<<","<<poz2<<"] = " <<dp[akt][i].st<<endl;
				}
				nowelewo.pb(dp[akt][skok1]);
				if(DEBUG) if(MyNodeId()==1) cout<<"NOWELEWO "<<dp[akt][skok1].st<<endl;
				akt = 1-akt;
			}	
			if(MyNodeId()!=(x-1)){
				FOR(i,0,skok1+1){
					PutInt(MyNodeId()+1,dp[1-akt][i].st);
					PutInt(MyNodeId()+1,dp[1-akt][i].nd);
				}
				Send(MyNodeId()+1);
			}
			mojafaza++;
		}

		if(faza<x-1) ub++;
		else lb++;
		
	}
}