UVa 11975 - Tele-loto

Accepted date: 2015-05-15
Ranking (as of 2015-05-15): 27 out of 61
Language: C++

/*
  UVa 11975 - Tele-loto

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

#include <cstdio>

const int nr_balls_max = 75, nr_values = 4, nr_rows = 5, nr_columns = 5;
int balls[nr_balls_max], values[nr_values], ticket[nr_rows][nr_columns],
  findings[nr_rows][nr_columns];

bool corners(int n)
{
  return n >= 4 && findings[0][0] < 35 && findings[0][nr_columns - 1] < 35 &&
    findings[nr_rows - 1][0] < 35 && findings[nr_rows - 1][nr_columns - 1] < 35;
}

bool mid_line(int n)
{
  if (n < nr_columns)
    return false;
  for (int i = 0; i < nr_columns; i++)
    if (findings[2][i] >= 40)
      return false;
  return true;
}

bool diagonals(int n)
{
  return n >= 9 && findings[0][0] < 45 && findings[0][nr_columns - 1] < 45 &&
    findings[1][1] < 45 && findings[1][3] < 45 && findings[2][2] < 45 &&
    findings[3][1] < 45 && findings[3][3] < 45 &&
    findings[nr_rows - 1][0] < 45 && findings[nr_rows - 1][nr_columns - 1] < 45;
}

bool table(int n)
{
  if (n < nr_rows * nr_columns)
    return false;
  for (int i = 0; i < nr_rows; i++)
    for (int j = 0; j < nr_columns; j++)
      if (findings[i][j] == nr_balls_max)
        return false;
  return true;
}

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int N, L;
    scanf("%d %d", &N, &L);
    for (int i = 0; i < N; i++)
      scanf("%d", &balls[i]);
    for (int i = 0; i < nr_values; i++)
      scanf("%d", &values[i]);
    printf("Case %d:\n", t);
    while (L--) {
      for (int i = 0; i < nr_rows; i++)
        for (int j = 0; j < nr_columns; j++) {
          scanf("%d", &ticket[i][j]);
          findings[i][j] = nr_balls_max;
        }
      for (int i = 0; i < N; i++) {
        int c = (balls[i] - 1) / 15;
        for (int r = 0; r < nr_rows; r++)
          if (ticket[r][c] == balls[i]) {
            findings[r][c] = i; break;
          }
      }
      int value = 0;
      if (corners(N))
        value += values[0];
      if (mid_line(N))
        value += values[1];
      if (diagonals(N))
        value += values[2];
      if (table(N))
        value += values[3];
      printf("%d\n", value);
    }
    if (t < T)
      putchar('\n');
  }
  return 0;
}

UVa 334 - Identifying Concurrent Events

Accepted date: 2015-05-11
Ranking (as of 2015-05-11): 190 out of 386
Language: C++

/*
  UVa 334 - Identifying Concurrent Events

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

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
using namespace std;

int main()
{
  for (int case_nr = 1; ; case_nr++) {
    int n = 0, N, NC, NM;
    cin >> NC;
    if (!NC)
      break;
    vector<string> names;
    map<string, int> name_indices;
    set< pair<int, int> > edges;
    while (NC--) {
      cin >> N;
      for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        names.push_back(s);
        name_indices.insert(make_pair(s, n));
        if (i)
          edges.insert(make_pair(n - 1, n));
        n++;
      }
    }
    cin >> NM;
    while (NM--) {
      string s, r;
      cin >> s >> r;
      edges.insert(make_pair(name_indices[s], name_indices[r]));
    }
    vector< vector<bool> > matrix(n, vector<bool>(n, false));
    for (set< pair<int, int> >::const_iterator ei = edges.begin(), ee = edges.end();
      ei != ee; ++ei)
      matrix[ei->first][ei->second] = true;
#ifdef DEBUG
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        cout << matrix[i][j] << ((j < n - 1) ? ' ' : '\n');
#endif
    // apply Warshall's Transitive Closure algorithm
    for (int k = 0; k < n; k++)
      for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
          matrix[i][j] = matrix[i][j] || matrix[i][k] && matrix[k][j];
    int nr_events = n * (n - 1) / 2;
    for (int i = 0; i < n - 1; i++)
      for (int j = i + 1; j < n; j++)
        if (matrix[i][j] || matrix[j][i])
          nr_events--;

    cout << "Case " << case_nr << ", ";
    if (nr_events) {
      cout << nr_events << " concurrent events:\n";
      if (nr_events > 2)
        nr_events = 2;
      for (int i = 0; i < n - 1 && nr_events; i++)
        for (int j = i + 1; j < n && nr_events; j++)
          if (!matrix[i][j] && !matrix[j][i]) {
            nr_events--;
            cout << '(' << names[i] << ',' << names[j] << ") ";
          }
      cout << endl;
    }
    else
      cout << "no concurrent events.\n";

  }
  return 0;
}

UVa 11047 - The Scrooge Co Problem

Accepted date: 2015-05-09
Ranking (as of 2015-05-09): 56 out of 285
Language: C++

/*
  UVa 11047 - The Scrooge Co Problem

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

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

const int n_max = 99, nr_chars_max = 31;

char names[n_max][nr_chars_max + 1];
int dists[n_max][n_max], nexts[n_max][n_max];

int get_index(int n, const char* name)
{
  for (int i = 0; i < n; i++)
    if (!strcmp(name, names[i]))
      return i;
  return -1;
}

void floyd_warshall_with_path_reconstruction(int n)
{
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      if (dists[i][k] != numeric_limits<int>::max())
        for (int j = 0; j < n; j++)
          if (dists[k][j] != numeric_limits<int>::max() &&
            dists[i][k] + dists[k][j] < dists[i][j]) {
            dists[i][j] = dists[i][k] + dists[k][j];
            nexts[i][j] = nexts[i][k];
          }
}

void print_path(int u, int v)
{
  printf("Path:%s", names[u]);
  do {
    u = nexts[u][v];
    printf(" %s", names[u]);
  } while (u != v);
  putchar('\n');
}

int main()
{
  int C;
  scanf("%d", &C);
  while (C--) {
    int P;
    scanf("%d", &P);
    for (int i = 0; i < P; i++)
      scanf("%s", names[i]);
    for (int i = 0; i < P; i++)
      for (int j = 0; j < P; j++) {
        int C;
        scanf("%d", &C);
        dists[i][j] = (C >= 0) ? C : numeric_limits<int>::max();
        nexts[i][j] = j;
      }
    floyd_warshall_with_path_reconstruction(P);
    int R;
    scanf("%d", &R);
    while (R--) {
      char employee[nr_chars_max + 1], start[nr_chars_max + 1], end[nr_chars_max + 1];
      scanf("%s %s %s", employee, start, end);
      int s = get_index(P, start), e = get_index(P, end);
      if (dists[s][e] != numeric_limits<int>::max()) {
        printf("Mr %s to go from %s to %s, you will receive %d euros\n",
          employee, start, end, dists[s][e]);
        print_path(s, e);
      }
      else
        printf("Sorry Mr %s you can not go from %s to %s\n", employee, start, end);
    }
  }
  return 0;
}

UVa 12319 - Edgetown's Traffic Jams

Accepted date: 2015-05-08
Ranking (as of 2015-05-08): 23 out of 175
Language: C++

/*
  UVa 12319 - Edgetown's Traffic Jams

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

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <limits>
using namespace std;

void floyd_warshall(int n, vector< vector<int> >& matrix)
{
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++)
      if (matrix[i][k] != numeric_limits<int>::max())
        for (int j = 1; j <= n; j++)
          if (matrix[k][j] != numeric_limits<int>::max())
            matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
}

int main()
{
  while (true) {
    string s;
    getline(cin, s);
    istringstream iss(s);
    int n;
    iss >> n;
    iss.clear();
    if (!n)
      break;
    vector< vector<int> >
      matrix(n + 1, vector<int>(n + 1, numeric_limits<int>::max())),
      pmatrix(n + 1, vector<int>(n + 1, numeric_limits<int>::max()));
    for (int i = 0; i < n; i++) {
      getline(cin, s);
      iss.str(s);
      int j, k;
      iss >> j;
      while (iss >> k)
        matrix[j][k] = 1;
      iss.clear();
    }
    for (int i = 0; i < n; i++) {
      getline(cin, s);
      iss.str(s);
      int j, k;
      iss >> j;
      while (iss >> k)
        pmatrix[j][k] = 1;
      iss.clear();
    }
    int A, B;
    getline(cin, s);
    iss.str(s);
    iss >> A >> B;
    iss.clear();
    floyd_warshall(n, matrix);
    floyd_warshall(n, pmatrix);
    bool yes = true;
    for (int i = 1; i <= n && yes; i++)
      for (int j = 1; j <= n && yes; j++)
        if (i != j)
          if (matrix[i][j] < numeric_limits<int>::max()) {
            if (pmatrix[i][j] == numeric_limits<int>::max() ||
              pmatrix[i][j] > matrix[i][j] * A + B)
              yes = false;
          }
    cout << ((yes) ? "Yes\n" : "No\n");
  }
  return 0;
}

UVa 12498 - Ant's Shopping Mall

Accepted date: 2015-05-06
Ranking (as of 2015-05-06): 67 out of 175
Language: C++

/*
  UVa 12498 - Ant's Shopping Mall

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

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

const int R_max = 50, C_max = 50;

char mall[R_max][C_max + 1];

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int R, C;
    scanf("%d %d", &R, &C);
    for (int r = 0; r < R; r++)
      scanf("%s", mall[r]);
    int min_nr_moves = -1;
    for (int c = 0; c < C; c++) {
      int nr_moves = 0;
      for (int r = 0; r < R; r++) {
        int min_nr_column_moves = 0;
        if (mall[r][c] == '1') {
          min_nr_column_moves = C;
          for (int i = c - 1; i >= 0; i--)
            if (mall[r][i] == '0') {
              min_nr_column_moves = c - i;
              break;
            }
          for (int i = c + 1; i < C; i++)
            if (mall[r][i] == '0') {
              min_nr_column_moves = min(min_nr_column_moves, i - c);
              break;
            }
        }
        if (min_nr_column_moves == C) {
          nr_moves = -1;
          break;
        }
        else
          nr_moves += min_nr_column_moves;
      }
      if (nr_moves != -1) {
        if (min_nr_moves == -1)
          min_nr_moves = nr_moves;
        else
          min_nr_moves = min(min_nr_moves, nr_moves);
      }
    }
    printf("Case %d: %d\n", t, min_nr_moves);
  }
  return 0;
}

UVa 945 - Loading a Cargo Ship

Accepted date: 2015-05-04
Ranking (as of 2015-05-04): 3 out of 35
Language: C++

/*
  UVa 945 - Loading a Cargo Ship

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

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

const int c_max = 9, p_max = 999;

struct container {
  int weight_;
  int nr_packages_;
  int packages_[p_max];
} containers[c_max];

int main()
{
  bool printed = false;
  int c;
  while (scanf("%d", &c) != EOF) {
    if (printed)
      putchar('\n');
    else
      printed = true;
    for (int i = 0; i < c; i++) {
      scanf("%d", &containers[i].weight_);
      containers[i].nr_packages_ = 0;
    }
    int p;
    scanf("%d", &p);
    int min_nr_packages = 0, unloaded = 0;
    for (int i = 0; i < p; i++) {
      int weight;
      scanf("%d", &weight);
      if (unloaded) {
        unloaded += weight;
        continue;
      }
      int ci = -1;
      for (int j = 0; j < c; j++)
        if (containers[j].nr_packages_ == min_nr_packages) {
          if (ci == -1 || containers[j].weight_ > containers[ci].weight_)
            ci = j;
        }
      if (ci == -1 || containers[ci].weight_ < weight)
        unloaded += weight;
      else {
        containers[ci].weight_ -= weight;
        containers[ci].packages_[containers[ci].nr_packages_++] = weight;
        min_nr_packages = i + 1;
        for (int j = 0; j < c; j++)
          min_nr_packages = min(min_nr_packages, containers[j].nr_packages_);
      }
    }
    int cargo = 0, unused = 0, max_nr_packages = 0;
    for (int i = 0; i < c; i++) {
      max_nr_packages = max(max_nr_packages, containers[i].nr_packages_);
      unused += containers[i].weight_;
      for (int j = 0; j < containers[i].nr_packages_; j++)
        cargo += containers[i].packages_[j];
    }
    for (int i = max_nr_packages; i > 0; i--)
      for (int j = 0; j < c; j++) {
        if (containers[j].nr_packages_ >= i)
          printf("%d", containers[j].packages_[i - 1]);
        else
          putchar(':');
        printf("%c", (j < c - 1) ? ' ' : '\n');
      }
    for (int i = 0; i < c * 2 - 1; i++)
      putchar('=');
    putchar('\n');
    for (int i = 1; i <= c; i++)
      printf("%d%c", i, ((i < c) ? ' ' : '\n'));
    printf("\ncargo weight: %d\n", cargo);
    printf("unused weight: %d\n", unused);
    printf("unloaded weight: %d\n", unloaded);
  }
  return 0;
}

UVa 949 - Getaway

Accepted date: 2015-05-02
Ranking (as of 2015-05-02): 27 out of 73
Language: C++

/*
  UVa 949 - Getaway

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

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <utility>
#include <limits>
using namespace std;

int main()
{
  const int nr_dirs = 4;
  pair<int, int> dirs[nr_dirs] =
    {make_pair(1, 0), make_pair(-1, 0), make_pair(0, 1), make_pair(0, -1)};
  int nr, nc;
  while (cin >> nr >> nc) {
    int r;
    cin >> r;
    set< pair< pair<int, int>, pair<int, int> > > restrictions;
    while (r--) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      restrictions.insert(make_pair(make_pair(x1, y1), make_pair(x2, y2)));
    }
    int m;
    cin >> m;
    set< pair<pair<int, int>, int> > monitorizations;
    while (m--) {
      int t, x, y;
      cin >> t >> x >> y;
      monitorizations.insert(make_pair(make_pair(x, y), t));
    }
    queue< pair<pair<int, int>, int> > q;
    vector< vector<int> > arrived(nr, vector<int>(nc, numeric_limits<int>::max()));
    int t = 0;
    while (monitorizations.find(make_pair(make_pair(0, 0), t)) !=
      monitorizations.end())
      t++;
    arrived[0][0] = t;
    q.push(make_pair(make_pair(0, 0), t));
    while (!q.empty()) {
      pair<pair<int, int>, int> u = q.front(); q.pop();
      int ux = u.first.first, uy = u.first.second, ut = u.second;
      for (int i = 0; i < nr_dirs; i++) {
        int x = ux + dirs[i].first, y = uy + dirs[i].second;
        if (x >= 0 && x < nr && y >= 0 && y < nc &&
          restrictions.find(make_pair(make_pair(ux, uy), make_pair(x, y))) ==
            restrictions.end()) {
          int t = ut + 1;
          while (monitorizations.find(make_pair(make_pair(x, y), t)) !=
            monitorizations.end())
            t++;
          if (t < arrived[x][y]) {
            arrived[x][y] = t;
            q.push(make_pair(make_pair(x, y), t));
          }
        }
      }
    }
    cout << arrived[nr - 1][nc - 1] << endl;
  }
  return 0;
}