## 100 - Decl

# 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 }

## 250 - Stax

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

`) contains the value`

**i**`(and`

**maxXorin[j]**`, respectively) at least once. To make sure this always happens, we can try a greedy approach:`

**maxXoranna[i]**`, for each set of coordinates`

**stax[i][j] = min(maxXorin[j], maxXoranna[i])**`that need to contain a stack.`

**(i, j)**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

## 500 - kSpecialists

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.

## 1000 - Septica

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
s). 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):**7**- 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.