2013年9月5日

UVa 338 - Long Multiplication

#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;

void rev(char * s) {
  char * head = s, * tail = s, c;
  while (*tail) {
    tail++;
  }
  tail--;
  while (head < tail) {
    c = *head;
    *head++ = *tail;
    *tail-- = c;
  }
}

string removeZero(string s) {
  while (s.length() > 1 && s[0] == '0') {
    s = s.substr(1);
  }
  return s;
}

string add(string s1, string s2) {
  int l1 = s1.length(), l2 = s2.length();
  char result[99];
  int d = 0, carry = 0;
  while (l1 || l2) {
    int digit = carry;
    if (l1) {
      digit += (s1[--l1] - '0');
    }
    if (l2) {
      digit += (s2[--l2] - '0');
    }
    result[d++] = digit % 10 + '0';
    carry = digit / 10;
  }
  if (carry) {
    result[d++] = carry + '0';
  }
  result[d++] = 0;
  rev(result);
  return removeZero(string(result));
}

string simpleMut(string s, char base) {
  int l = s.length();
  char result[99];
  int d = 0, carry = 0;
  while (l) {
    int digit = carry + (s[--l] - '0') * (base - '0');
    result[d++] = digit % 10 + '0';
    carry = digit / 10;
  }
  if (carry) {
    result[d++] = carry + '0';
  }
  result[d++] = 0;
  rev(result);
  return removeZero(string(result));
}

void solve(string s1, string s2) {
  s1 = removeZero(s1);
  s2 = removeZero(s2);
  int len = max(s1.length(), s2.length());
  string ans = "0";
  vector<string> process;
  for (int pos = s2.length() - 1; pos >= 0; pos--) {
    string result = simpleMut(s1, s2[pos]);
    process.PB(result);
    ans = add(ans, result + string(s2.length() - pos - 1, '0'));
  }
  len = max(len, (int)ans.length());
  printf("%*s\n", len, s1.c_str());
  printf("%*s\n", len, s2.c_str());
  printf("%*s\n", len, string(max(s1.length(), s2.length()), '-').c_str());
  int processNum = 0;
  for (int i = 0; i < process.size(); i++) {
    if (process[i] == "0" || (!processNum && i == process.size() - 1)) {
      continue;
    }
    printf("%*s\n", len - i, process[i].c_str());
    processNum++;
  }
  if (processNum > 1) {
    printf("%*s\n", len, string(len, '-').c_str());
  }
  if (processNum != 1) {
    printf("%*s\n", len, ans.c_str());
  }
}

int main() {
  char s[99];
  while (gets(s) && s[1]) {
    char s1[99], s2[99];
    sscanf(s, "%s%s", s1, s2);
    solve(s1, s2);
    puts("");
  }
  return 0;
}

UVa 271 - Simply Syntax

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;

int main() {
  char s[999];
  while (gets(s)) {
    stack<char> exp;
    bool ok = true;
    for (int i = strlen(s) - 1; ok && i >= 0; i--) {
      if (s[i] >= 'p' && s[i] <= 'z') {
        exp.push(s[i]);
      } else if (s[i] == 'N') {
        if (!exp.size()) {
          ok = false;
        }
      } else if (s[i] == 'C' || s[i] == 'D' || s[i] == 'E' || s[i] == 'I') {
        if (exp.size() >= 2) {
          exp.pop();
        } else {
          ok = false;
        }
      }
    }
    puts((exp.size() == 1 && ok) ? "YES" : "NO");
  }
  return 0;
}

2013年9月4日

UVa 10912 - Simple Minded Hashing

#include <cstdio>

int main() {
  int L, S, C = 1;
  int dp[27][352][27] = {};
  for (int t = 1; t <= 26; t++) {
    dp[1][t][t] = 1;
  }
  for (int l = 2; l <= 26; l++) {
    for (int s = 351; s; s--) {
      for (int pre = 0; pre < 26; pre++) {
        for (int tail = pre + 1; tail <= 26 && tail <= s; tail++) {
          dp[l][s][tail] += dp[l - 1][s - tail][pre];
        }
      }
    }
  }
  while (scanf("%d%d", &L, &S) && L) {
    int ans = 0;
    if (L <= 26 && S <= 351) {
      for (int t = 1; t <= 26; t++) {
        ans += dp[L][S][t];
      }
    }
    printf("Case %d: %d\n", C++, ans);
  }
  return 0;
}

UVa 11420 - Chest of Drawers

#include <cstdio>

int main() {
  long long dp[66][66][2] = {};
  dp[1][0][0] = dp[1][1][1] = 1;
  for (int i = 2; i < 66; i++) {
    for (int j = 0; j <= i; j++) {
      dp[i][j][0] = dp[i - 1][j][0];
      if (j) {
        dp[i][j][1] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1];
      }
      if (j != i) {
        dp[i][j][0] += dp[i - 1][j + 1][1];
      }
    }
  }
  int n, s;
  while (scanf("%d%d", &n, &s) && n > 0) {
    printf("%lld\n", dp[n][s][0] + dp[n][s][1]);
  }
  return 0;
}

UVa 196 - Spreadsheet

#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <sstream>
#include <string>
using namespace std;

int grid[1000][18279];
char formula[1000][18279][100];
bool done[1000][18279];

int solve(int r, int c) {
  if (done[r][c]) {
    return grid[r][c];
  }
  for (int i = 0; formula[r][c][i]; i++) {
    if (formula[r][c][i] == '+' || formula[r][c][i] == '=') {
      formula[r][c][i] = ' ';
    }
  }
  istringstream ss(formula[r][c]);
  string s;
  int sum = 0;
  while (ss >> s) {
    int r = 0, c = 0;
    for (int i = 0; s[i]; i++) {
      if (isdigit(s[i])) {
        r = r * 10 + (s[i] - '0');
      } else {
        c = c * 26 + (s[i] - 'A' + 1);
      }
    }
    sum += solve(r, c);
  }
  done[r][c] = true;
  return (grid[r][c] = sum);
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int R, C;
    scanf("%d%d", &C, &R);
    for (int r = 1; r <= R; r++) {
      for (int c = 1; c <= C; c++) {
        scanf("%s", formula[r][c]);
        done[r][c] = false;
        if (isdigit(formula[r][c][0])) {
          done[r][c] = true;
          grid[r][c] = atoi(formula[r][c]);
        }
      }
    }
    for (int r = 1; r <= R; r++) {
      for (int c = 1; c <= C; c++) {
        printf("%d%s", solve(r, c), c == C ? "\n" : " ");
      }
    }
  }
  return 0;
}

UVa 10898 - Combo Deal

#include <cstdio>
#include <queue>
#include <vector>
#define PB push_back
using namespace std;

struct Combo {
  Combo() {
    for (int i = 0; i < 6; i++) {
      num[i] = 0;
    }
  }
  int num[6], price;
};

int best[1000000];

int main() {
  int N;
  while (scanf("%d", &N) == 1) {
    vector<Combo> combos;
    for (int i = 0; i < N; i++) {
      Combo combo;
      scanf("%d", &combo.price);
      combo.num[i] = 1;
      combos.PB(combo);
    }
    int M;
    scanf("%d", &M);
    while (M--) {
      Combo combo;
      for (int i = 0; i < N; i++) {
        scanf("%d", &combo.num[i]);
      }
      scanf("%d", &combo.price);
      combos.PB(combo);
    }
    int last = 0;
    for (int i = 0; i < N; i++) {
      last = last * 10 + 9;
    }
    for (int i = 1; i <= last; i++) {
      best[i] = 2e9;
    }
    best[0] = 0;
    for (int price = 0; price <= last; price++) {
      if (best[price] == 2e9) {
        continue;
      }
      int num[6] = {};
      for (int temp = price, d = N - 1; temp; temp /= 10, d--) {
        num[d] = temp % 10;
      }
      for (int i = 0; i < combos.size(); i++) {
        int next[6] = {}, index = 0;
        bool push = true;
        for (int j = 0; j < N && push; j++) {
          next[j] = num[j] + combos[i].num[j];
          index = index * 10 + next[j];
          push = (next[j] <= 9);
        }
        if (!push) {
          continue;
        }
        best[index] = min(best[index], best[price] + combos[i].price);
      }
    }
    scanf("%d", &M);
    while (M--) {
      int index = 0;
      for (int i = 0; i < N; i++) {
        int num;
        scanf("%d", &num);
        index = index * 10 + num;
      }
      printf("%d\n", best[index]);
    }
  }
  return 0;
}

UVa 10911 - Forming Quiz Teams

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

inline double dis(int x1, int y1, int x2, int y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int main() {
  int bits[17] = {1};
  for (int b = 1; b < 17; b++) {
    bits[b] = bits[b - 1] << 1;
  }
  int N, C = 1;
  while (scanf("%d", &N) && N) {
    N <<= 1;
    int x[16], y[16];
    for (int i = 0; i < N; i++) {
      scanf("%*s%d%d", &x[i], &y[i]);
    }
    int last = bits[N];
    double dp[1 << 16];
    dp[0] = 0;
    for (int state = 1; state < last; state++) {
      bool found = false;
      for (int i = 0; bits[i] < state; i++) {
        for (int j = i + 1; bits[j] < state; j++) {
          if (state & bits[i] && state & bits[j]) {
            double sum = dp[state ^ bits[i] ^ bits[j]] + dis(x[i], y[i], x[j], y[j]);
            dp[state] = min(found ? dp[state] : 2e9, sum);
            found = true;
          }
        }
      }
    }
    printf("Case %d: %.2lf\n", C++, dp[last - 1]);
  }
  return 0;
}

2013年9月3日

UVa 10389 - Subway

#include <cstdio>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <map>
#define PB push_back
#define MP make_pair
using namespace std;

typedef pair<int, int> P;

struct State {
  State(P p, double need) : p(p), need(need) {}
  bool operator<(const State & other) const {
    return need > other.need;
  }
  P p;
  double need;
};

const double mpm[2] = {10000 / 60.0, 40000 / 60.0};

inline double dis(P & a, P & b) {
  int dx = a.first - b.first, dy = a.second - b.second;
  return sqrt(dx * dx + dy * dy);
}

int main() {
  char temp[9999];
  gets(temp);
  int T;
  sscanf(temp, "%d", &T);
  gets(temp);
  while (T--) {
    gets(temp);
    int sx, sy, ex, ey;
    sscanf(temp, "%d%d%d%d", &sx, &sy, &ex, &ey);
    P s = MP(sx, sy), e = MP(ex, ey);
    vector<P> walk;
    map<P, vector<P> > next;
    walk.PB(e);
    while (gets(temp) && *temp) {
      istringstream ss(temp);
      int x, y;
      vector<P> v;
      while (ss >> x >> y) {
        if (x < 0) {
          break;
        }
        v.PB(MP(x, y));
      }
      for (int i = 0; i < v.size(); i++) {
        walk.PB(v[i]);
        if (i) {
          next[v[i]].PB(v[i - 1]);
        }
        if (i < v.size() - 1) {
          next[v[i]].PB(v[i + 1]);
        }
      }
    }
    priority_queue<State> pq;
    map<P, double> best;
    best[s] = 0;
    pq.push(State(s, 0));
    while (!pq.empty()) {
      P now = pq.top().p;
      double need = pq.top().need;
      pq.pop();
      if (now == e) {
        printf("%.0lf\n", need);
        break;
      }
      for (int i = 0; i < walk.size(); i++) {
        P & j = walk[i];
        if (now != j) {
          double nextNeed = need + dis(now, j) / mpm[0];
          if (best.find(j) == best.end() || nextNeed < best[j]) {
            pq.push(State(j, nextNeed));
            best[j] = nextNeed;
          }
        }
      }
      for (int i = 0; i < next[now].size(); i++) {
        P & j = next[now][i];
        if (now != j) {
          double nextNeed = need + dis(now, j) / mpm[1];
          if (best.find(j) == best.end() || nextNeed < best[j]) {
            pq.push(State(j, nextNeed));
            best[j] = nextNeed;
          }
        }
      }
    }
    if (T) {
      puts("");
    }
  }
  return 0;
}

UVa 1112 - Mice and Maze

WA for 7 times just beacuse I always use T as variable of case number.
#include <cstdio>
#include <vector>
#include <queue>
#define PB push_back
using namespace std;

struct State {
  State(int now, int need) : now(now), need(need) {}
  bool operator<(const State & other) const {
    return need > other.need;
  }
  int now, need;
};

int main() {
  int Case;
  scanf("%d", &Case);
  while (Case--) {
    int N, E, T, M, need[101][101];
    vector<int> con[101];
    scanf("%d%d%d%d", &N, &E, &T, &M);
    while (M--) {
      int a, b, t;
      scanf("%d%d%d", &a, &b, &t);
      con[b].PB(a);
      need[b][a] = t;
    }
    int best[101];
    for (int i = 1; i <= N; i++) {
      best[i] = 1e8;
    }
    best[E] = 0;
    priority_queue<State> pq;
    pq.push(State(E, 0));
    while (!pq.empty()) {
      int now = pq.top().now, use = pq.top().need;
      pq.pop();
      if (use > T) {
        break;
      }
      for (int i = 0; i < con[now].size(); i++) {
        int j = con[now][i];
        if (use + need[now][j] < best[j]) {
          best[j] = use + need[now][j];
          pq.push(State(j, best[j]));
        }
      }
    }
    int ans = 0;
    for (int i = 1; i <= N; i++) {
      ans += (best[i] <= T);
    }
    printf("%d\n", ans);
    if (Case) {
      puts("");
    }
  }
  return 0;
}

UVa 10718 - Bit Mask

#include <cstdio>

int main() {
  long long N, L, U, bits[33] = {1};
  for (int b = 1; b < 33; b++) {
    bits[b] = bits[b - 1] << 1;
  }
  while (scanf("%lld%lld%lld", &N, &L, &U) == 3 ) {
    long long ans = 0;
    for (int b = 32; b >= 0; b--) {
      if (N & bits[b]) {
        if (ans + bits[b] <= L) {
          ans += bits[b];
        }
      } else if (ans + bits[b] <= U) {
        ans += bits[b];
      }
    }
    printf("%lld\n", ans);
  }
  return 0;
}

2013年9月2日

UVa 10926 - How Many Dependencies?

#include <cstdio>
#include <cstring>
#include <vector>
#define PB push_back
using namespace std;

int n;
vector<int> con[101];
bool vis[101];

void dfs(int i) {
  vis[i] = true;
  for (int j = 0; j < con[i].size(); j++) {
    if (!vis[con[i][j]]) {
      dfs(con[i][j]);
    }
  }
}

int main() {
  while (scanf("%d", &n) && n) {
    for (int i = 1; i <= n; i++) {
      con[i].clear();
      int num;
      scanf("%d", &num);
      while (num--) {
        int j;
        scanf("%d", &j);
        con[i].PB(j);
      }
    }
    int ans, maxDep = 0;
    for (int i = 1; i <= n; i++) {
      memset(vis, false, sizeof(vis));
      dfs(i);
      int dep = 0;
      for (int j = 1; j <= n; j++) {
        dep += vis[j];
      }
      if (dep > maxDep) {
        maxDep = dep;
        ans = i;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

UVa 501 - Black Box

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int M, N, num[30000];
    scanf("%d%d", &M, &N);
    for (int i = 0; i < M; i++) {
      scanf("%d", &num[i]);
    }
    vector<int> box;
    int done = 0, need = 0;
    while (N--) {
      int index;
      scanf("%d", &index);
      while (box.size() < index) {
        vector<int>::iterator it = lower_bound(box.begin(), box.end(), num[done]);
        box.insert(it, num[done++]);
      }
      printf("%d\n", box[need++]);
    }
    if (T) {
      puts("");
    }
  }
  return 0;
}

UVa 450 - Little Black Book

#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;

struct Data {
  Data (string title,
        string firstName,
        string lastName, 
        string address,
        string department,
        string homePhone,
        string workPhone,
        string campusBox)

    :   title(title),
        firstName(firstName),
        lastName(lastName),
        address(address),
        department(department),
        homePhone(homePhone),
        workPhone(workPhone),
        campusBox(campusBox) {}

  bool operator<(const Data & other) const {
    return lastName < other.lastName;
  }
  string title, firstName, lastName;
  string address, department, homePhone, workPhone, campusBox;
};

int main() {
  vector<Data> lists;
  char temp[9999];
  gets(temp);
  int N;
  sscanf(temp, "%d", &N);
  while (N--) {
    char department[99];
    gets(department);
    while (gets(temp) && temp[0]) {
      string s(temp);
      int comma[6];
      comma[0] = s.find(',');
      for (int i = 1; i < 6; i++) {
        comma[i] = s.find(',', comma[i - 1] + 1);
      }
      lists.PB(Data(s.substr(0, comma[0]),
                    s.substr(comma[0] + 1, comma[1] - comma[0] - 1),
                    s.substr(comma[1] + 1, comma[2] - comma[1] - 1),
                    s.substr(comma[2] + 1, comma[3] - comma[2] - 1),
                    department,
                    s.substr(comma[3] + 1, comma[4] - comma[3] - 1),
                    s.substr(comma[4] + 1, comma[5] - comma[4] - 1),
                    s.substr(comma[5] + 1)));
    }
  }
  sort(lists.begin(), lists.end());
  for (int i = 0; i < lists.size(); i++) {
    Data & data = lists[i];
    puts("----------------------------------------");
    printf("%s %s %s\n", data.title.c_str(), data.firstName.c_str(), data.lastName.c_str());
    puts(data.address.c_str());
    printf("Department: %s\n", data.department.c_str());
    printf("Home Phone: %s\n", data.homePhone.c_str());
    printf("Work Phone: %s\n", data.workPhone.c_str());
    printf("Campus Box: %s\n", data.campusBox.c_str());
  }
  return 0;
}

UVa 11310 - Delivery Debacle

#include <cstdio>

int main() {
  long long f[41] = {1, 1, 5};
  for (int i = 3; i <= 40; i++) {
    f[i] = f[i - 1] + 4 * f[i - 2] + 2 * f[i - 3];
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    int n;
    scanf("%d", &n);
    printf("%lld\n", f[n]);
  }
  return 0;
}

UVa 11492 - Babel

#include <cstdio>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#define PB push_back
using namespace std;

struct Node {
  Node(int index, int len, int head) : index(index), len(len), head(head) {}
  bool operator<(const Node & other) const {
    return (len > other.len);
  }
  int index, len, head;
};

const int SIZE = 4000;

int main() {
  int M;
  while (scanf("%d", &M) && M) {
    vector<int> con[SIZE], d[SIZE], letter[SIZE];
    char start[99], end[99];
    scanf("%s%s", start, end);
    map<string, int> indexOf;
    int N = 0;
    while (M--) {
      char s1[99], s2[99], word[99];
      scanf("%s%s%s", s1, s2, word);
      int a, b;
      if (indexOf.find(s1) != indexOf.end()) {
        a = indexOf[s1];
      } else {
        a = N;
        indexOf[s1] = N++;
      }
      if (indexOf.find(s2) != indexOf.end()) {
        b = indexOf[s2];
      } else {
        b = N;
        indexOf[s2] = N++;
      }
      con[a].PB(b);
      con[b].PB(a);
      int len = string(word).length();
      d[a].PB(len);
      d[b].PB(len);
      letter[a].PB(word[0] - 'a');
      letter[b].PB(word[0] - 'a');
    }
    if (string(start) == string(end)) {
      puts("0");
    } else if (indexOf.find(start) != indexOf.end() && indexOf.find(end) != indexOf.end()) {
      priority_queue<Node> pq;
      pq.push(Node(indexOf[start], 0, -1));
      int dis[SIZE][26];
      for (int i = 0; i < N; i++) {
        fill(dis[i], dis[i] + 26, 1e8);
      }
      while (!pq.empty()) {
        Node now = pq.top();
        pq.pop();
        int a = now.index;
        for (int i = 0; i < con[a].size(); i++) {
          int b = con[a][i];
          int head = letter[a][i];
          if (now.head != head && now.len + d[a][i] < dis[b][head]) {
            dis[b][head] = now.len + d[a][i];
            pq.push(Node(b, dis[b][head], head));
          }
        }
      }
      int ans = 1e8;
      for (int i = 0; i < 26; i++) {
        ans = min(ans, dis[indexOf[end]][i]);
      }
      if (ans >= 1e8) {
        puts("impossivel");
      } else {
        printf("%d\n", ans);
      }
    } else {
      puts("impossivel");
    }
  }
  return 0;
}

2013年9月1日

UVa 11389 - The Bus Driver Problem

#include <cstdio>
#include <vector>
#include <algorithm>
#define PB push_back
using namespace std;
 
int main() {
  int n, d, r;
  while (scanf("%d%d%d", &n, &d, &r) && n) {
    vector<int> len[2];
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < n; j++) {
        int l;
        scanf("%d", &l);
        len[i].PB(l);
      }
      sort(len[i].begin(), len[i].end());
    }
    int ans = 0;
    for (int i = 0; i < len[0].size(); i++) {
      int price = (len[0][i] + len[1][n - i - 1] - d) * r;
      ans += price < 0 ? 0 : price;
    }
    printf("%d\n", ans);
  }
  return 0;
}

UVa 11003 - Boxes

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int SIZE = 3000 + 1;
int num[1001][SIZE], load[1001][SIZE];

int main() {
  int N;
  while (scanf("%d", &N) && N) {
    memset(num, 0, sizeof(num));
    memset(load, 0, sizeof(load));
    load[0][0] = 2e9;
    int ans = 0, limit = 0;
    for (int i = 1; i <= N; i++) {
      for (int j = 0; j <= limit; j++) {
        num[i][j] = num[i - 1][j];
        load[i][j] = load[i - 1][j];
      }
      int w, l;
      scanf("%d%d", &w, &l);
      limit = max(limit, l);
      for (int j = 0; j <= limit; j++) {
        if (load[i - 1][j] >= w) {
          int newNum = num[i - 1][j] + 1, newLoad = min(load[i - 1][j] - w, l);
          if ((num[i][newLoad] < newNum) || ((num[i][newLoad] == newNum) && (load[i][newLoad] < newLoad))) {
            num[i][newLoad] = newNum;
            load[i][newLoad] = newLoad;
            ans = max(ans, newNum);
          }
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

UVa 1209 - Wordfish

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

int main() {
  char s[99];
  while (gets(s)) {
    int len = string(s).length();
    for (int i = 0; i < 10; i++) {
      prev_permutation(s, s + len);
    }
    int dis = 0;
    string ans;
    for (int i = 0; i < 21; i++) {
      int d = 2e9;
      for (int i = 1; s[i]; i++) {
        d = min(d, abs(s[i] - s[i - 1]));
      }
      if (d > dis) {
        dis = d;
        ans = s;
      }
      next_permutation(s, s + len);
    }
    printf("%s%d\n", ans.c_str(), dis);
  }
  return 0;
}

UVa 10616 - Divisible Group Sums

#include <cstdio>

int main() {
  int N, Q, S = 1;
  while (scanf("%d%d", &N, &Q) && N) {
    printf("SET %d:\n", S++);
    int num[200];
    for (int i = 0; i < N; i++) {
      scanf("%d", &num[i]);
    }
    int q = 1;
    while (Q--) {
      int D, M;
      scanf("%d%d", &D, &M);
      long long dp[11][20] = {1};
      for (int i = 0; i < N; i++) {
        for (int m = M; m; m--) {
          for (int r = 0; r < D; r++) {
            dp[m][r] += dp[m - 1][(r - num[i] % D + D) % D];
          }
        }
      }
      printf("QUERY %d: %lld\n", q++, dp[M][0]);
    }
  }
  return 0;
}