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 <algorithm>
#include <iostream>
#include <cassert>
#include <sstream>
using namespace std;
#define make(type, x) type x; cin>>x;
#define make2(type, x, y) type x, y; cin>>x>>y;
#define make3(type, x, y, z) type x, y, z; cin>>x>>y>>z;
#define MP make_pair
template<class C> void mini(C&a4, C b4){a4=min(a4, b4); }
template<class C> void maxi(C&a4, C b4){a4=max(a4, b4); }
template<class T1, class T2>
ostream& operator<< (ostream &out, pair<T1, T2> pair) { return out << "(" << pair.first << ", " << pair.second << ")";}
typedef pair<int, int> PII;
const int N = 1e5 + 5;
const int H = 1e4 + 5;
const int W = 1e2 + 5;
char a[N], b[N];

pair<int, int> dp[H][W];
int main() {
  make2(int, row, col);
  int inst_num = min(NumberOfNodes(), row);
  long long start_row = 1 + MyNodeId() * row / inst_num;
  long long end_row = ((MyNodeId() + 1) * row) / inst_num;
  if (MyNodeId() >= inst_num) {
    return 0;
  }
  for (int i = 1; i <= row; i++) {
    cin>>a[i];
  }
  for (int i = 1; i <= col; i++) {
    cin>>b[i];
  }
  
  int computed_cols = 0;
  int cols_in_package = 102;
  while (computed_cols < col) {
    int my_hei = end_row - start_row + 1;
    for (int i = 0; i <= my_hei; i++) {
      if (computed_cols == 0) {
        dp[i][0] = MP(i + start_row - 1, 0);
      } else {
        dp[i][0] = dp[i][cols_in_package];
      }
    }
    int inst = MyNodeId();
    int new_cols = min(cols_in_package, col - computed_cols);
    if (inst > 0) {
      Receive(inst - 1);
    }
    for (int c = 1; c <= new_cols; c++) {
      if (inst > 0) {
        int fir = GetInt(inst - 1);
        int sec = GetInt(inst - 1);
        dp[0][c] = MP(fir, sec);
      } else {
        dp[0][c] = MP(computed_cols + c, 0);
      }
      for (int r = 1; r <= my_hei; r++) {
        int i = r - 1 + start_row;
        int j = computed_cols + c;
        
        PII left = dp[r][c - 1];
        left.first++;
        PII right = dp[r - 1][c];
        right.first++;
        PII diag = dp[r - 1][c - 1];
        if (a[i] != b[j]) { 
          diag.first++;
        }
        if (a[i] < b[j]) {
          diag.second++;
        }
        dp[r][c] = min(min(left, right), diag);
        if (i == row && j == col) {
          cout<<dp[r][c].first<<" "<<dp[r][c].second<<endl;
        }
      }
      if (inst < inst_num - 1) {
        PutInt(inst + 1, dp[my_hei][c].first);
        PutInt(inst + 1, dp[my_hei][c].second);
      }
    }
    computed_cols += new_cols;
    if (inst < inst_num - 1) {
      Send(inst + 1);
    }
  }
      
      
  return 0;
}