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
#include <cstdio>
#include <algorithm>
#include "message.h"
using namespace std;

const int MAX = 10005;

struct par
{
	int p;
	int s;
};

par mk(int p, int s)
{
	par x;
	x.p=p;
	x.s=s;
	return x;
}

par operator+(par a, par b)
{
	a.p+=b.p;
	a.s+=b.s;
	return a;
}

bool operator<(par a, par b)
{
	if (a.p==b.p) return a.s<b.s;
	return a.p<b.p;
}

char s1[MAX];
char s2[MAX];

par w[MAX][MAX];//[sufiks s1][sufiks s2](przyciski, szoki)

par chg(int i, int j)
{
	char a=s1[i];
	char b=s2[j];
	
	if (a>b) return mk(1, 0);
	if (a==b) return mk(0, 0);
	
	return mk(1, 1);
}

int main()
{
	if (MyNodeId()!=0) return 0;
	
	int n, m;
	
	scanf("%d%d%*c", &n, &m);
	
	for (int i=1; i<=n; i++) scanf("%c", &s1[i]);
	scanf("%*c");
	for (int i=1; i<=m; i++) scanf("%c", &s2[i]);
	
	for (int i=1; i<=n; i++) w[i][m+1]=mk(n-i+1, 0);
	
	for (int i=n; i>0; i--)
	{
		//rozważam literę s1[i], mam policzone wszystkie wartości dla i+1
		for (int j=m; j>0; j--)
		{
			//s1[i] ląduje na pozycji j
			//albo nie używam s1[i], albo używam tutaj, albo biorę wynik od następnika+1
			if (i!=n)
				w[i][j]=min(w[i+1][j]+mk(1, 0), min(chg(i, j)+w[i+1][j+1], w[i][j+1]+mk(1, 0)));
			else
				w[i][j]=min(mk(1+m-j+1, 0), min(chg(i, j)+mk(m-j, 0), w[i][j+1]+mk(1, 0)));
		}
	}
	
	printf("%d %d\n", w[1][1].p, w[1][1].s);
	
	//for (int i=0; i<=n+1; i++) {for (int j=0; j<=m+1; j++) printf("(%d %d) ", w[i][j].p, w[i][j].s); printf("\n");}
	
	return 0;
}