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

#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#define MAXN 100007
#define MAX_NODE 107
#define MAX_MESS 1000
#define INF
#define PB push_back
#define MP make_pair
#define ST first
#define ND second

#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(a,b,c) for(int a=b;a<=(c);a++)
#define FORD(a,b,c) for (int a=b;a>=(c);a--)
#define VAR(v,n) __typeof(n) v=(n)
#define ALL(c) c.begin(),c.end()
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();i++)

using namespace std;

typedef long long LL; 
typedef pair<int,int> PII;

int ile_inst,OGR;
int mojeID,poprzednik,nastepnik;

int n,m,ktore_robie;
char s1[MAXN], s2[MAXN];
PII wyn[2][MAXN];
PII pop_dol, pop_lewo, akt_lewo, akt_wyn;

int main() {
	ile_inst = NumberOfNodes();
	mojeID = MyNodeId();
	poprzednik = mojeID-1;
	nastepnik = mojeID+1;
	
	scanf("%d%d",&n,&m);
	scanf(" %s %s",s1+1,s2+1);
	//printf("%s\n%s\n",s1+1,s2+1);
	int reszta = m%NumberOfNodes();
	int dlugosc = m/NumberOfNodes();
	int poczatek = MyNodeId()*dlugosc + min(MyNodeId(),reszta) + 1;
	int koniec = poczatek + dlugosc + (MyNodeId() < reszta ? 0 : -1);	
	OGR = (n+MAX_MESS-1)/MAX_MESS;
	//printf("%d %d\n",poczatek,koniec);
	
	if (poczatek <= koniec) {
		FOR(j,poczatek-1,koniec) wyn[0][j-poczatek+1] = MP(j,0);
		FOR(i,1,n) {
			int kt = i&1; 
			FOR(j,poczatek,koniec) {
				if (j == poczatek) {
					if (poczatek == 1)
						wyn[kt][0] = MP(i,0);
					else {
						if (i%OGR == 1 || OGR == 1) Receive(poprzednik);
						wyn[kt][0].ST = GetInt(poprzednik);
						wyn[kt][0].ND = GetInt(poprzednik);
					}	 
				}
			
				pop_lewo = wyn[1^kt][j-poczatek];
				pop_dol = wyn[1^kt][j-poczatek+1];
				akt_lewo = wyn[kt][j-poczatek];
				akt_wyn = MP(n+m,0);
			
				akt_wyn = min(akt_wyn,MP(pop_lewo.ST+1,pop_lewo.ND + (s1[i] < s2[j] ? 1 : 0)));
				akt_wyn = min(akt_wyn,MP(pop_dol.ST+1,pop_dol.ND));
				akt_wyn = min(akt_wyn,MP(akt_lewo.ST+1,akt_lewo.ND));
				if (s1[i] == s2[j])
					akt_wyn = min(akt_wyn,pop_lewo);
				
				if (j == koniec && koniec != m) {
					PutInt(nastepnik,akt_wyn.ST);
					PutInt(nastepnik,akt_wyn.ND);
					if (i%OGR == 0 || i == n) Send(nastepnik);
				}
				wyn[kt][j-poczatek+1] = akt_wyn; 
			}
			FOR(j,poczatek-1,koniec) wyn[kt^1][j-poczatek+1] = wyn[kt][j-poczatek+1];
		}	
		if (koniec == m) printf("%d %d\n",wyn[n&1][koniec-poczatek+1].ST,wyn[n&1][koniec-poczatek+1].ND);
	}
	return 0;
}