C solution (Marius Gavrilescu)

    1 #include<stdio.h>
    2 #include<stdlib.h>
    3 #include<string.h>
    4 
    5 char decl[105], *var[105], delim[105] = "][\n";
    6 
    7 int main(void){
    8     for(char c = 'a' ; c <= 'z' ; c++) // Construct the delimiter containing
    9         delim[c - 'a' + 3] = c;        // all letters and ], [, newline
   10 
   11     while(!feof(stdin)){                            // While we aren't done
   12         fgets(decl, 105, stdin);                    // Read a declaration into decl
   13         scanf(" ");                                 // Trigger EOF if necessary
   14         char *last_space = strrchr(decl, ' ');      // Find the last space character
   15         *last_space = 0;                            // Split the string at this char
   16         char *type = decl, *vars = last_space + 1;  // into the type and a string of vars
   17 
   18         int varn = 0, sum = 0;
   19         var[0] = strtok(vars, ",");                 // Split the string of vars into an array
   20         while((var[++varn] = strtok(NULL, ",")));
   21 
   22         for(int i = 0 ; i < varn ; i++){            // For each variable
   23             int nr = 1;                             // nr is the dimension of the variable (number of elements)
   24             char *part = strtok(var[i], delim);     // Split it into parts using delim
   25             while(part) {                           // Each part is a dimension of the vector
   26                 nr *= atoi(part);                   // Multiply nr by the dimension
   27                 part = strtok(NULL, delim);
   28             }
   29             sum += nr * 4;                          // int is the default type and has 4 bytes
   30         }
   31 
   32         if(strstr(type, "short"))
   33             sum /= 2;
   34         if(strstr(type, "char"))
   35             sum /= 4;
   36         printf("%d\n", sum);
   37     }
   38 
   39     return 0;
   40 }

Perl solution (Marius Gavrilescu)

    1 #!/usr/bin/perl
    2 use v5.14;
    3 use warnings;
    4 
    5 use List::Util qw/reduce sum/;
    6 
    7 while (<>) {
    8     my ($type, $vars) = /(.*) ([^ ]+)$/; # Split the declaration into type and string of vars
    9     my @vars = split ',', $vars;         # Split the string of vars into an array
   10     y/0-9]//cd for @vars;                # Remove all characters from variables except for digits and ]
   11     my $result = sum map { reduce { $a * $b } 4, split ']' } @vars; # Split each var into dimensions, multiply the dimensions together and sum the results
   12     $result /= 2 if $type =~ /short/;
   13     $result /= 4 if $type =~ /char/;
   14     say $result;
   15 }

Let's take a look at Xorin's perspective from left to right, and, for each column, calculate maxXorin[j] = the height of the stack Xorin sees. It is clear that Xorin will only see the tallest stack out of all those which lie on the same column.

The same idea applies for maxXoranna[i].

When attempting to reconstruct a possible solution, for each stack (i, j), two conditions must hold:

• stax[i][j] ≤ maxXorin[j]
• stax[i][j] ≤ maxXoranna[i]

In other words, the height of any stack must not exceed the height that Xorin sees, and the height that Xoranna sees.

However, this piece of information is incomplete. We also need to make sure that each column j (and line i) contains the value maxXorin[j] (and maxXoranna[i], respectively) at least once. To make sure this always happens, we can try a greedy approach: stax[i][j] = min(maxXorin[j], maxXoranna[i]), for each set of coordinates (i, j) that need to contain a stack.

Time complexity: O(n*m + n*h * m*h) ≈ O(n*m)

C++ solution (Sergiu Puscas)

    1 #include <iostream>
    2 #include <cstring>
    3 #define nmax 1000
    4 #define hmax 10
    5 using namespace std;
    6 
    7 int n, m, h, a[nmax][nmax], maxXorin[nmax], maxXoranna[nmax];
    8 string topView[nmax], XorinView[nmax], XorannaView[nmax], sol[nmax];
    9 
   10 int main() {
   11     cin>>n>>m>>h;
   12     cin.get();
   13 
   14     for(int i=0; i<n; i++) getline(cin, topView[i]), sol[i].resize(m, '.');
   15     for(int i=0; i<h; i++) {
   16         getline(cin, XorinView[i]);
   17         for(int j=0; j<m; j++)
   18             if(XorinView[i][j] == '#' && maxXorin[j] == 0) maxXorin[j] = h-i;
   19     }
   20 
   21     for(int i=0; i<h; i++) {
   22         getline(cin, XorannaView[i]);
   23         for(int j=0; j<n; j++)
   24             if(XorannaView[i][j] == '#' && maxXoranna[n-j-1] == 0) maxXoranna[n-j-1] = h-i;
   25     }
   26 
   27     for(int i=0; i<n; i++)
   28         for(int j=0; j<m; j++)
   29             if(topView[i][j] == '#')
   30                 sol[i][j] = '0' + min(maxXorin[j], maxXoranna[i]);
   31 
   32     for(int i=0; i<n; i++) cout<<sol[i]<<"\n";
   33     return 0;
   34 }
   35 

It's easy to notice that we have a complete bipartite graph with K nodes. One set contains the nodes of the K specialists. The other contains the nodes of the K servers.

It is complete because we have a path between any pair of nodes.

Now, the answer for the problem is the minimum cost such that if we consider only the edges with cost less or equal to that cost, we have a perfect match. If we increase that cost, the match can only increase or stay the same.

Therefore, we can binary search for the answer.

The game of Septica can be broken down into two subproblems:

• finding a suitable strategy for the cases when you move first (this is also used by the computer);
• finding a suitable strategy for the cases when the opponent moves first.

There are 2 possible situations for starting a trick:

• Having at least 3 potential cuts in our set of cards (either valuable cards or 7s). In this situation, we start with a valuable card, because the chances of winning are high. Possible initial configurations (where X denotes any other card):
  
  • 10 10 10 10
  • 14 14 14 14
  • 10 10 10 X
  • 14 14 14 X
  • 10 10 7 X
  • 14 14 7 X
  • 10 7 7 X
  • 14 7 7 X
  • 7 7 7 X
  • 7 7 7 7
• Having less than 3 cuts in our set of cards. In this situation, we start with a random card, provided it is not valuable (choose anything but 7, 10, 14).

There are also 2 possible situations of responding to a trick started by the computer:

• The computer uses a valuable card (10 or 14) and we have at least 2 or 3 possible cuts in our hand. In this case, we can try to cut with a 7 or with the initial card used by the computer. If we don't have enough cuts, we use a random worthless card.
• The computer uses a worthless card. We try to cut with either a 7 or with the computer's initial card.

All the heuristics described above provide a good enough strategy for our problem. The success rate of this solution is greater than 70% on random matches.