UVa 10902 - Pick-up Sticks

Accepted date: 2016-05-31
Run Time: 0.080
Ranking (as of 2016-05-31): 21 out of 681
Language: C++

/*
  UVa 10902 - Pick-up Sticks

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10902_Pick-up_Sticks.cpp
*/

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

const double epsilon = numeric_limits<double>::epsilon();

struct point{
  double x_, y_;
};

struct segment{
  int n_;
  point s_, e_;
};

inline bool in_range(double l, double u, double d)
{
  return d >= l && d <= u;
}

double direction(const point& p1, const point& p2, const point& p3)
{
  return (p1.x_ - p2.x_) * (p2.y_ - p3.y_) - (p2.x_ - p3.x_) * (p1.y_ - p2.y_);
}

bool on_segment(const point& p1, const point& p2, const point& p3)
{
  return in_range(min(p1.x_, p2.x_), max(p1.x_, p2.x_), p3.x_) &&
    in_range(min(p1.y_, p2.y_), max(p1.y_, p2.y_), p3.y_);
}

bool segment_intersect(const point& p1, const point& p2, const point& p3, const point& p4)
{
  double d1 = direction(p3, p4, p1), d2 = direction(p3, p4, p2),
    d3 = direction(p1, p2, p3), d4 = direction(p1, p2, p4);
  if((d1 > epsilon && d2 < -epsilon || d1 < -epsilon && d2 > epsilon) &&
    (d3 > epsilon && d4 < -epsilon || d3 < -epsilon && d4 > epsilon))
    return true;
  if (fabs(d1) < epsilon && on_segment(p3, p4, p1))
    return true;
  if (fabs(d2) < epsilon && on_segment(p3, p4, p2))
    return true;
  if (fabs(d3) < epsilon && on_segment(p1, p2, p3))
    return true;
  if (fabs(d4) < epsilon && on_segment(p1, p2, p4))
    return true;
  return false;
}

int main()
{
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    segment s;
    vector<segment> segments;
    s.n_ = 1;
    scanf("%lf %lf %lf %lf", &s.s_.x_, &s.s_.y_, &s.e_.x_, &s.e_.y_);
    segments.push_back(s);
    for (int i = 2; i <= n; i++) {
      s.n_ = i;
      scanf("%lf %lf %lf %lf", &s.s_.x_, &s.s_.y_, &s.e_.x_, &s.e_.y_);
      for (vector<segment>::iterator si = segments.begin(); si != segments.end(); ) {
        if (segment_intersect(si->s_, si->e_, s.s_, s.e_))
          segments.erase(si);
        else
          ++si;
      }
      segments.push_back(s);
    }
    printf("Top sticks:");
    for (vector<segment>::const_iterator si = segments.begin(), se = segments.end();
      si != se; ) {
      printf(" %d", si->n_);
      printf("%c", (++si != se) ? ',' : '.');
    }
    putchar('\n');
  }
  return 0;
}

UVa 10927 - Bright Lights

Accepted date: 2016-05-29
Run Time: 0.060
Ranking (as of 2016-05-29): 4 out of 508
Language: C++

/*
  

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10927_Bright_Lights.cpp
*/

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

const int N_max = 100000;

struct pole {
  int X_, Y_, Z_, x_, y_, gcd_;

  bool operator<(const pole& p) const {
    if (x_ != p.x_)
      return x_ < p.x_;
    if (y_ != p.y_)
      return y_ < p.y_;
    if (gcd_ != p.gcd_)
      return gcd_ < p.gcd_;
    return Z_ < p.Z_;
  }
} poles[N_max];

int invisibles[N_max];

bool compare_invisible(int i, int j)
{
  return (poles[i].X_ != poles[j].X_) ?
    poles[i].X_ < poles[j].X_ : poles[i].Y_ < poles[j].Y_;
}

int gcd(int x, int y)
{
  if (x < y)
    return gcd(y, x);
  else
      return y == 0 ? x : gcd(y, x % y);
}

int main()
{
  for (int ds = 1; ; ds++) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    for (int i = 0; i < n; i++) {
      pole& p = poles[i];
      scanf("%d %d %d", &p.X_, &p.Y_, &p.Z_);
      p.gcd_ = gcd(abs(p.X_), abs(p.Y_));
      p.x_ = p.X_ / p.gcd_, p.y_ = p.Y_ / p.gcd_;
    }
    printf("Data set %d:\n", ds);
    sort(poles, poles + n);
#ifdef DEBUG
    for (int i = 0; i < n; i++)
      printf("%d %d %d %d\n", poles[i].x_, poles[i].y_, poles[i].gcd_, poles[i].Z_);
#endif
    int nr_invisibles = 0, x = poles[0].x_, y = poles[0].y_, Z = poles[0].Z_;
    for (int i = 1; i < n; i++) {
      if (poles[i].x_ != x || poles[i].y_ != y) {
        x = poles[i].x_, y = poles[i].y_, Z = poles[i].Z_;
      }
      else {
        if (poles[i].Z_ <= Z)
          invisibles[nr_invisibles++] = i;
        else
          Z = poles[i].Z_;
      }
    }
    if (nr_invisibles) {
      sort(invisibles, invisibles + nr_invisibles, compare_invisible);
      puts("Some lights are not visible:");
      for (int i = 0; i < nr_invisibles; i++)
        printf("x = %d, y = %d%c\n", poles[invisibles[i]].X_, poles[invisibles[i]].Y_,
          ((i < nr_invisibles - 1) ? ';' : '.'));
    }
    else
      puts("All the lights are visible.");
  }
  return 0;
}

UVa 11345 - Rectangles

Accepted date: 2016-05-28
Run Time: 0.000
Ranking (as of 2016-05-28): 6 out of 528
Language: C++

/*
  UVa 11345 - Rectangles

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11345_Rectangles.cpp
*/

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

int main()
{
  int N;
  scanf("%d", &N);
  for (int n = 1; n <= N; n++) {
    int M, max_X1, max_Y1, min_X2, min_Y2;
    scanf("%d", &M);
    scanf("%d %d %d %d", &max_X1, &max_Y1, &min_X2, &min_Y2);
    while (--M) {
      int X1, Y1, X2, Y2;
      scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2);
      max_X1 = max(max_X1, X1), max_Y1 = max(max_Y1, Y1),
        min_X2 = min(min_X2, X2), min_Y2 = min(min_Y2, Y2);
#ifdef DEBUG
      printf("%d %d %d %d\n", max_X1, max_Y1, min_X2, min_Y2);
#endif
    }
    int area = 0;
    if (max_X1 < min_X2 && max_Y1 < min_Y2)
      area = (min_X2 - max_X1) * (min_Y2 - max_Y1);
    printf("Case %d: %d\n", n, area);
  }
  return 0;
}

UVa 12482 - Short Story Competition

Accepted date: 2016-05-27
Run Time: 0.000
Ranking (as of 2016-05-27): 18 out of 426
Language: C++

/*
  UVa 12482 - Short Story Competition

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_12482_Short_Story_Competition.cpp
*/

#include <cstdio>

const int N_max = 1000, C_max = 70;
char s[N_max * (C_max + 1)];

int main()
{
  int N, L, C;
  while (scanf("%d %d %d", &N, &L, &C) != EOF) {
    while (getchar() != '\n')
      ;
    gets(s);
    if (!s[0]) {
      puts("0");
      continue;
    }
    int l = 1, c = 0, d;
    char *p = s, *q = p;
    while (true) {
      while (*p && *p != ' ')
        p++;
      d = p - q;
      if (!*p)
        break;
      if (c + d == C) {
        l++, c = 0;
#ifdef DEBUG
        *p = '\n';
#endif
        p++;
      }
      else {
        p++, d++;
        if (c + d > C) {
          l++, c = p - q;
#ifdef DEBUG
          *(q - 1) = '\n';
#endif
        }
        else if (c + d == C) {
          l++, c = 0;
#ifdef DEBUG
          *(p - 1) = '\n';
#endif
        }
        else
          c += d;
      }
      q = p;
    }
    if (c + d > C)
      l++;
#ifdef DEBUG
    puts(s);
#endif
    printf("%d\n", (l + L - 1) / L);
  }
  return 0;
}

UVa 393 - The Doors

Accepted date: 2016-05-25
Run Time: 0.000
Ranking (as of 2016-05-25): 59 out of 521
Language: C++

/*
  UVa 393 - The Doors

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_393_The_Doors.cpp

  ACM Mid-Central Regionals 1996, Problem #2
    (http://www.ntnu.edu.tw/acm/ProblemSetArchive/B_US_MidCen/1996/index.html)
*/

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

const double infinite = numeric_limits<double>::max(),
  epsilon = numeric_limits<double>::epsilon();
const int nr_walls_max = 18, nr_ys = 4;

struct wall {
  double x_;
  double ys_[nr_ys];
} walls[nr_walls_max + 2] = {
  // walls[0] is the chamber's left wall and 
  // walls[nr_walls_max + 1] is the chamber's right wall
  {0.0, {5.0, 5.0, 5.0, 5.0}}
};

int nr_walls;
double distances[nr_walls_max + 2][nr_ys][nr_walls_max + 2][nr_ys];
  // distances[si][sj][ei][ej] is the distance between walls[si].ys_[sj] 
  // and walls[ei].ys_[ej]

double get_distance(int si, int sj, int ei, int ej)
{
  double dx = walls[ei].x_ - walls[si].x_, dy = walls[ei].ys_[ej] - walls[si].ys_[sj],
    dm  = dy / dx;
  for (int i = si + 1; i < ei; i++) {
    double y = walls[si].ys_[sj] + dm * (walls[i].x_ - walls[si].x_);
    if (y >= walls[i].ys_[0] - epsilon && y <= walls[i].ys_[1] + epsilon ||
      y >= walls[i].ys_[2] - epsilon && y <= walls[i].ys_[3] + epsilon)
      ;
    else
      return infinite;
  }
  return sqrt(dx * dx + dy * dy);
}

int main()
{
  while (true) {
    scanf("%d", &nr_walls);
    if (nr_walls == -1)
      break;
    for (int i = 1; i <= nr_walls; i++) {
      wall& w = walls[i];
      scanf("%lf %lf %lf %lf %lf", &w.x_, &w.ys_[0], &w.ys_[1], &w.ys_[2], &w.ys_[3]);
    }
    nr_walls++;
    walls[nr_walls].x_ = 10.0;
    walls[nr_walls].ys_[0] = walls[nr_walls].ys_[1] =
      walls[nr_walls].ys_[2] = walls[nr_walls].ys_[3] = 5.0;
    for (int si = 0; si <= nr_walls; si++)
      for (int sj = 0; sj < nr_ys; sj++)
        for (int ei = 0; ei <= nr_walls; ei++)
          for (int ej = 0; ej < nr_ys; ej++)
            distances[si][sj][ei][ej] = (ei > si) ? get_distance(si, sj, ei, ej) : infinite;
    for (int mi = 1; mi <= nr_walls; mi++)
      for (int mj = 0; mj < nr_ys; mj++)
        for (int ei = 1; ei <= nr_walls; ei++)
          for (int ej = 0; ej < nr_ys; ej++)
            if (distances[0][0][mi][mj] < infinite &&
              distances[mi][mj][ei][ej] < infinite)
              distances[0][0][ei][ej] = min(distances[0][0][ei][ej],
                distances[0][0][mi][mj] + distances[mi][mj][ei][ej]);
    printf("%.2lf\n", distances[0][0][nr_walls][0]);
  }
  return 0;
}

UVa 10400 - Game Show Math

Accepted date: 2016-05-18
Run Time: 0.020
Ranking (as of 2016-05-18): 5 out of 1718
Language: C++

/*
  UVa 10400 - Game Show Math

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10400_Game_Show_Math.cpp
*/

#include <cstdio>
#include <cstdlib>
#include <cstring>

const int p_max = 100, result_min = -32000, result_max = 32000;
char operators[p_max][result_max - result_min + 1];
int p, numbers[p_max], target;

bool game(int pi, int result)
{
  if (pi < p) {
    int r;
    if ((r = result + numbers[pi]) <= result_max && !operators[pi][r]) {
      operators[pi][r] = '+';
#ifdef DEBUG
      printf("[%d][%d]: %c\n", pi, r, operators[pi][r]);
#endif
      if (game(pi + 1, r))
        return true;
    }
    if ((r = result - numbers[pi]) >= result_min && !operators[pi][r]) {
      operators[pi][r] = '-';
#ifdef DEBUG
      printf("[%d][%d]: %c\n", pi, r, operators[pi][r]);
#endif
      if (game(pi + 1, result - numbers[pi]))
        return true;
    }
    if (abs(r = result * numbers[pi]) <= result_max && !operators[pi][r]) {
      operators[pi][r] = '*';
#ifdef DEBUG
      printf("[%d][%d]: %c\n", pi, r, operators[pi][r]);
#endif
      if (game(pi + 1, r))
        return true;
    }
    if (numbers[pi] && !(result % numbers[pi]) && !operators[pi][r = result / numbers[pi]]) {
      operators[pi][r] = '/';
#ifdef DEBUG
      printf("[%d][%d]: %c\n", pi, r, operators[pi][r]);
#endif
      if (game(pi + 1, r))
        return true;
    }
    return false;
  }
  else
    return result == target;
}

void print_expression(int pi, int result)
{
  if (!pi)
    printf("%d", numbers[pi]);
  else {
    int r = result;
    switch (operators[pi][r]) {
    case '+':
      r -= numbers[pi]; break;
    case '-':
      r += numbers[pi]; break;
    case '*':
      r /= numbers[pi]; break;
    case '/':
      r *= numbers[pi]; break;
    }
    print_expression(pi - 1, r);
    printf("%c%d", operators[pi][result], numbers[pi]);
  }
}

int main()
{
  int n;
  scanf("%d", &n);
  while (n--) {
    scanf("%d", &p);
    for (int i = 0; i < p; i++)
      scanf("%d", &numbers[i]);
    scanf("%d", &target);
    if (p > 1) {
      memset(operators, 0, sizeof(operators));
      game(1, numbers[0]);
      if (operators[p - 1][target]) {
        print_expression(p - 1, target);
        printf("=%d\n", target);
      }
      else
        puts("NO EXPRESSION");
    }
    else {
      if (numbers[0] == target)
        printf("%d=%d\n", numbers[0], target);
      else
        puts("NO EXPRESSION");
    }
  }
  return 0;
}

UVa 10086 - Test the Rods

Accepted date: 2016-05-17
Run Time: 0.010
Ranking (as of 2016-05-17): 2 out of 453
Language: C++

/*
  UVa 10086 - Test the Rods

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10086_Test_the_Rods.cpp
*/

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

const int infinite = numeric_limits<int>::max();
const int T_max = 300, n_max = 30, m_max = 20;

struct site {
  int m_;
  int c1_[m_max + 1], c2_[m_max + 1];
} sites[n_max + 1];

int ssites[n_max + 1];

int T1, T2, n, costs[n_max + 1][T_max + 1];
  // costs[i][j] is the minimum cost for testing j samples at NCPC up to i-th site
int prevs[n_max + 1][T_max + 1]; // costs[i - 1][prevs[i][j]] contributes to costs[i][j]

void print_samples(int i, int t, int pt)
{
  if (i == 1)
    printf("%d", t);
  else {
    print_samples(i - 1, pt, prevs[i - 1][pt]);
    printf(" %d", t - pt);
  }
}

int main()
{
  while (true) {
    scanf("%d %d", &T1, &T2);
    if (!T1 && !T2)
      break;
    scanf("%d", &n);
    for (int i = 1, ss = 0; i <= n; i++) {
      site& s = sites[i];
      scanf("%d", &s.m_);
      for (int j = 1; j <= s.m_; j++)
        scanf("%d", &s.c1_[j]);
      for (int j = 1; j <= s.m_; j++)
        scanf("%d", &s.c2_[j]);
      ss += s.m_;
      ssites[i] = ss;
    }
    for (int i = 0; i <= n; i++)
      for (int j = 0; j <= T1; j++)
        costs[i][j] = infinite;
    costs[0][0] = 0;
    for (int i = 1; i <= n; i++) {
      const site& s = sites[i];
      for (int j = max(0, ssites[i] - T2); j <= min(T1, ssites[i]); j++)
        for (int k = max(0, j - s.m_); k <= j; k++)
          if (costs[i - 1][k] < infinite) {
            int c = costs[i - 1][k] + s.c1_[j - k] + s.c2_[s.m_ - (j - k)];
/*
#ifdef DEBUG
            printf("costs[%d][%d]: costs[%d][%d]:%d + s.c1_[%d]:%d + s.c2_[%d]:%d)\n",
              i, j, i - 1, k, costs[i - 1][k],
              j - k, s.c1_[j - k], s.m_ - (j - k), s.c2_[s.m_ - (j - k)]);
#endif
*/
            if (c < costs[i][j]) {
              costs[i][j] = c;
              prevs[i][j] = k;
            }
          }
#ifdef DEBUG
      for (int j = 0; j <= min(T1, ssites[i]); j++)
        if (costs[i][j] < infinite)
          printf("costs[%d][%d]:%d prevs[%d][%d]:%d\n",
            i, j, costs[i][j], i, j, prevs[i][j]);
#endif
    }
    printf("%d\n", costs[n][T1]);
    print_samples(n, T1, prevs[n][T1]);
    printf("\n\n");
  }
  return 0;
}

UVa 10118 - Free Candies

Accepted date: 2016-05-13
Run Time: 0.030
Ranking (as of 2016-05-13): 8 out of 631
Language: C++

/*
  UVa 10118 - Free Candies

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10118_Free_Candies.cpp
*/

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

const int nr_piles = 4, n_max = 40, color_max = 20, backet_max = 5;

int candies[nr_piles][n_max];
int n, piles[nr_piles], nr_colors;
bool colors[color_max + 1];
int results[n_max + 1][n_max + 1][n_max + 1][n_max + 1];
bool visited[n_max + 1][n_max + 1][n_max + 1][n_max + 1];

#ifdef DEBUG
int game(int indent)
#else
int game()
#endif
{
#ifdef DEBUG
  for (int i = 0; i < indent; i++)
    putchar(' ');
  printf("[%d][%d][%d][%d] %d\n",
    piles[0], piles[1], piles[2], piles[3], nr_colors);
#endif
  if (visited[piles[0]][piles[1]][piles[2]][piles[3]])
    return results[piles[0]][piles[1]][piles[2]][piles[3]];
  int result = 0;
  for (int i = 0; i < nr_piles; i++)
    if (piles[i] < n) {
      int c = candies[i][piles[i]];
      if (colors[c]) {
        piles[i]++, nr_colors--, colors[c] = false;
#ifdef DEBUG
        result = max(result, 1 + game(indent + 1));
#else
        result = max(result, 1 + game());
#endif
        piles[i]--, nr_colors++, colors[c] = true;
      }
      else if (nr_colors < backet_max - 1) {
        piles[i]++, nr_colors++, colors[c] = true;
#ifdef DEBUG
        result = max(result, game(indent + 1));
#else
        result = max(result, game());
#endif
        piles[i]--, nr_colors--, colors[c] = false;
      }
    }
#ifdef DEBUG
  for (int i = 0; i < indent; i++)
    putchar(' ');
  printf("[%d][%d][%d][%d] %d: %d\n",
    piles[0], piles[1], piles[2], piles[3], nr_colors, result);
#endif
  visited[piles[0]][piles[1]][piles[2]][piles[3]] = true;
  return results[piles[0]][piles[1]][piles[2]][piles[3]] = result;
}

int main()
{
  while (true) {
    scanf("%d", &n);
    if (!n)
      break;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < nr_piles; j++)
          scanf("%d", &candies[j][i]);
    memset(piles, 0, sizeof(piles));
    nr_colors = 0;
    memset(colors, 0, sizeof(colors));
    memset(visited, 0, sizeof(visited));
    visited[n][n][n][n] = true, results[n][n][n][n] = 0;
#ifdef DEBUG
    printf("%d\n", game(0));
#else
    printf("%d\n", game());
#endif
  }
  return 0;
}

UVa 11178 - Morley's Theorem

Accepted date: 2016-05-03
Run Time: 0.020
Ranking (as of 2016-05-03): 43 out of 433
Language: C++

/*
  UVa 11178 - Morley's Theorem

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11178_Morleys_Theorem.cpp
*/

#include <cstdio>
#include <cmath>

struct point {
  double x_, y_;

  point() {}
  point(double x, double y) : x_(x), y_(y) {}
};

double square_distance(const point& p, const point& q)
{
  double dx = p.x_ - q.x_, dy = p.y_ - q.y_;
  return dx * dx + dy * dy;
}

point pA, pB, pC, pD, pE, pF;
double as, bs, cs, a, b, c, A, B, C;

point trilinear_to_cartesian(double x, double y, double z)
{
  double d = a * x + b * y + c * z;
  return point(a * x / d * pA.x_ + b * y / d * pB.x_ + c * z / d * pC.x_,
    a * x / d * pA.y_ + b * y / d * pB.y_ + c * z / d * pC.y_);
}
 
int main()
{
  int N;
  scanf("%d", &N);
  while (N--) {
    scanf("%lf %lf %lf %lf %lf %lf", &pA.x_, &pA.y_, &pB.x_, &pB.y_, &pC.x_, &pC.y_);
    as = square_distance(pB, pC), bs = square_distance(pC, pA), cs = square_distance(pA, pB);
    a = sqrt(as), b = sqrt(bs), c = sqrt(cs);
    A = acos((bs + cs - as) / (2.0 * b * c)), B = acos((cs + as - bs) / (2.0 * c * a)),
      C = acos((as + bs - cs) / (2.0 * a * b));
    pD = trilinear_to_cartesian(1.0, 2.0 * cos(C / 3.0), 2.0 * cos(B / 3.0)),
      pE = trilinear_to_cartesian(2.0 * cos(C / 3.0), 1.0, 2.0 * cos(A / 3.0)),
      pF = trilinear_to_cartesian(2.0 * cos(B / 3.0), 2.0 * cos(A / 3.0), 1.0);
    printf("%.6lf %.6lf %.6lf %.6lf %.6lf %.6lf\n", pD.x_, pD.y_, pE.x_, pE.y_, pF.x_, pF.y_);
  }
  return 0;
}

UVa 11341 - Term Strategy

Accepted date: 2016-05-02
Run Time: 0.000
Ranking (as of 2016-05-02): 87 out of 436
Language: C++

/*
  UVa 11341 - Term Strategy

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11341_Term_Strategy.cpp
*/

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

const int N_max = 10, M_max = 100, min_grade = 5;
int table[N_max + 1][M_max + 1];
int grades[N_max + 1][M_max + 1];
  // grades[i][j] is max. of the total grade up to i-th courses 
  // with j hours spent for preparation

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int N, M, m = 0;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N; i++)
      for (int j = 1, k = 1; j <= M; j++) {
        scanf("%d", &table[i][k]);
        if (table[i][k] >= min_grade)
          k++;
        else
          m++;
      }
    M -= m;
    if (M < N) {
      puts("Peter, you shouldn't have played billiard that much.");
      continue;
    }
    for (int j = 1; j <= M; j++)
      grades[1][j] = table[1][j];
    for (int i = 2; i <= N; i++)
      for (int j = i; j <= M; j++) {
        int g = 0;
        for (int k = 1; k < j; k++)
          g = max(g, grades[i - 1][k] + table[i][j - k]);
        grades[i][j] = g;
      }
    printf("Maximal possible average mark - %.2lf.\n",
      static_cast<double>(grades[N][M]) / N + 1.0e-9);
      // Without 1.0e-9, you will receive the verdict Wrong Answer.
  }
  return 0;
}