UVa 346 - Getting Chorded

Accepted date: 2014-12-27
Ranking (as of 2014-12-27): 33 out of 406
Language: C++

/*
  UVa 346 - Getting Chorded

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

#include <cstdio>
#include <cstring>
#include <cctype>

#ifdef ONLINE_JUDGE
#define _stricmp strcasecmp
#endif

const int nr_chars_max = 3, nr_notes = 3, index_max = 12;

struct note {
  char s_[nr_chars_max + 1];
  int ci_, i_;
};

const note chromatic_notes[] = {
  {"A", 0}, {"A#", 1}, {"Bb", 1}, {"B", 2}, {"Cb", 2}, {"B#", 3},
  {"C", 3},{"C#", 4}, {"Db", 4}, {"D", 5}, {"D#", 6},
  {"Eb", 6}, {"E", 7}, {"Fb", 7}, {"E#", 8}, {"F", 8}, {"F#", 9},
  {"Gb", 9}, {"G", 10}, {"G#", 11}, {"Ab", 11}
};

void get_index(note& n)
{
  int i;
  for (i = 0; i < sizeof(chromatic_notes) / sizeof(note); i++)
    if (!_stricmp(n.s_, chromatic_notes[i].s_))
      break;
  n.ci_ = chromatic_notes[i].ci_; n.i_ = i;
}

const char* get_key(const note& n)
{
  int i = n.i_;
  if (n.s_[1] == 'b')
    i--;
  else if (n.s_[1] == '#') {
    if (chromatic_notes[i].s_[0] == 'B' || chromatic_notes[i].s_[0] == 'E')
      i++;
  }
  return chromatic_notes[i].s_;
}

int main()
{
  const int perms[][nr_notes] = {
    {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}
  };

  note notes[nr_notes];
  while (scanf("%s %s %s", notes[0].s_, notes[1].s_, notes[2].s_) != EOF) {
    for (int i = 0; i < nr_notes; i++)
      get_index(notes[i]);
    bool recognized = false;
    for (size_t i = 0; i < sizeof(perms) / sizeof(perms[0]); i++) {
      int third = notes[perms[i][1]].ci_ - notes[perms[i][0]].ci_,
        fifth = notes[perms[i][2]].ci_ - notes[perms[i][0]].ci_;
      char key[nr_chars_max + 1];
      if (third < 0)
        third += index_max;
      if (fifth < 0)
        fifth += index_max;
      if (third == 4 && fifth == 7) {
        recognized = true;
        printf("%s %s %s is a %s Major chord.\n",
          notes[0].s_, notes[1].s_, notes[2].s_, get_key(notes[perms[i][0]]));
        break;
      }
      else if (third == 3 && fifth == 7) {
        recognized = true;
        printf("%s %s %s is a %s Minor chord.\n",
          notes[0].s_, notes[1].s_, notes[2].s_, get_key(notes[perms[i][0]]));
        break;
      }
    }
    if (!recognized)
      printf("%s %s %s is unrecognized.\n", notes[0].s_, notes[1].s_, notes[2].s_);
  }
  return 0;
}

UVa 1174 - IP-TV

Accepted date: 2014-12-22
Language: C++

/*
  UVa 1174 - IP-TV

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

#include <vector>
#include <map>
#include <queue>
#include <set>
#include <limits>
#include <cstdio>
#include <cstring>
using namespace std;

const int nr_chars_max = 15;

struct city {
  char s_[nr_chars_max + 1];

  city() {}
  city(const char* s) {strcpy(s_, s);}
  bool operator<(const city& c) const {return strcmp(s_, c.s_) < 0;}
};

int register_city(const char* s, map<city, int>& cities)
{
  pair<map<city, int>::iterator, bool> result =
    cities.insert(make_pair(city(s), static_cast<int>(cities.size())));
  return result.first->second;
}

struct edge {
  int v_;
  int w_;
  edge(int v, int w) : v_(v), w_(w) {}
};

struct distance_comparator {
  const vector<int>& distances_;

  distance_comparator(const vector<int>& distances) : distances_(distances) {}
  bool operator() (int i, int j) const
  {
    return (distances_[i] != distances_[j]) ? distances_[i] < distances_[j] : i < j;
  }
};

int mst_prim(int n, const vector< vector<edge> >& edges)
{
  vector<bool> visited(n, false);
  vector<int> distances(n, numeric_limits<int>::max());
  distances[0] = 0;
  int mst_distance = 0;
  set<int, distance_comparator> pq(distances); // priority queue
  pq.insert(0);
  while (!pq.empty()) {
    int u = *pq.begin();
    pq.erase(pq.begin());
    visited[u] = true;
    mst_distance += distances[u];
    const vector<edge>& es = edges[u];
    for (size_t i = 0, j = es.size(); i < j; i++) {
      int v = es[i].v_, w = es[i].w_;
      if (!visited[v] && w < distances[v]) {
        pq.erase(v); // remove v if it has already been in the queue
        distances[v] = w;
        pq.insert(v);
      }
    }
  }
  return mst_distance;
}

int main()
{
  int nr_cases;
  scanf("%d", &nr_cases);
  while (nr_cases--) {
    int M, N;
    scanf("%d %d", &M, &N);
    map<city, int> cities;
    vector< vector<edge> > edges(M);
    while (N--) {
      char B[nr_chars_max + 1], E[nr_chars_max + 1];
      int C;
      scanf("%s %s %d", B, E, &C);
      int u = register_city(B, cities), v = register_city(E, cities);
      edges[u].push_back(edge(v, C));
      edges[v].push_back(edge(u, C));
    }
    printf("%d\n", mst_prim(M, edges));
    if (nr_cases)
      putchar('\n');
  }
  return 0;
}

UVa 1235 - Anti Brute Force Lock

Accepted date: 2014-12-17
Ranking (as of 2014-12-17): 29 out of 408
Language: C++

/*
  UVa 1235 - Anti Brute Force Lock

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

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

const int nr_digits = 4, N_max = 500;
int keys[N_max + 1][nr_digits], edges[N_max + 1][N_max + 1];

int get_number_of_rolls(const int* ki, const int* kj)
{
  int d = 0;
  for (int k = 0; k < nr_digits; k++, ki++, kj++) {
    int i = *ki, j = *kj;
    if (i < j)
      swap(i, j);
    d += min(i - j, j + 10 - i);
  }
  return d;
}

struct distance_comparator {
  const vector<int>& distances_;

  distance_comparator(const vector<int>& distances) : distances_(distances) {}
  bool operator() (int i, int j) const
  {
    return (distances_[i] != distances_[j]) ? distances_[i] < distances_[j] : i < j;
  }
};

int mst_prim(int n, int s)
{
  vector<bool> visited(n, false);
  vector<int> distances(n, numeric_limits<int>::max());
  distances[s] = 0;
  int mst_distance = 0;
  set<int, distance_comparator> pq(distances); // priority queue
  if (!s) { // zero key (0000) is not in the unlock key list
    int u = 0, d = numeric_limits<int>::max();
    for (int v = 1; v < n; v++)
      if (edges[s][v] < d) {
        u = v; d = edges[s][v];
      }
    distances[u] = d;
    pq.insert(u);
  }
  else
    pq.insert(s);
  while (!pq.empty()) {
    int u = *pq.begin();
    pq.erase(pq.begin());
    visited[u] = true;
    mst_distance += distances[u];
    for (int v = 1; v < n; v++)
      if (!visited[v] && edges[u][v] < distances[v]) {
        pq.erase(v); // remove v if it has already been in the queue
        distances[v] = edges[u][v];
        pq.insert(v);
      }
  }
  return mst_distance;
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int N;
    scanf("%d", &N);
    int zero_key = 0;
    for (int i = 1; i <= N; i++) {
      char s[nr_digits + 1];
      scanf("%s", s);
      int k = 0;
      for (int j = 0; j < nr_digits; j++) {
        keys[i][j] = s[j] - '0';
        k += keys[i][j];
      }
      if (!k)
        zero_key = i;
    }
    for (int i = 0; i < N; i++)
      for (int j = i + 1; j <= N; j++)
        edges[i][j] = edges[j][i] = get_number_of_rolls(keys[i], keys[j]);
    // apply Prim's minimum spanning tree algorithm
    printf("%d\n", mst_prim(N + 1, zero_key));
  }
  return 0;
}

UVa 614 - Mapping the Route

Accepted date: 2014-12-16
Language: C++

/*
  UVa 614 - Mapping the Route

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

#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;

const int nr_rows_max = 12, nr_columns_max = 12;
int nr_rows, nr_columns;
int walls[nr_rows_max][nr_columns_max];
bool visited[nr_rows_max][nr_columns_max];
pair<int, int> paths[nr_rows_max][nr_columns_max];
int cells[nr_rows_max][nr_columns_max];

bool dfs(const pair<int, int>& u, const pair<int, int>& g)
{
  const int nr_dirs = 4;
  pair<int, int> dirs[nr_dirs] =
    {make_pair(0, -1), make_pair(-1, 0), make_pair(0, 1), make_pair(1, 0)};

#ifdef DEBUG
  printf("%d %d\n", u.first, u.second);
#endif
  visited[u.first][u.second] = true;
  if (u == g)
    return true;
  for (int i = 0; i < nr_dirs; i++) {
    int r = u.first + dirs[i].first, c = u.second + dirs[i].second;
    if (r < 0 || r >= nr_rows || c < 0 || c >= nr_columns)
      continue;
    if (i == 0 && walls[r][c] & 1 || i == 2 && walls[r][c - 1] & 1 || // eastern wall
      i == 1 && walls[r][c] & 2 || i == 3 && walls[r - 1][c] & 2) // southern wall
      continue;
    if (!visited[r][c]) {
      paths[r][c] = u;
      if (dfs(make_pair(r, c), g))
        return true;
    }
  }
  return false;
}

int follow_paths(const pair<int, int>& s, const pair<int, int>& u)
{
  if (u == s)
    return cells[u.first][u.second] = 1;
  else
    return cells[u.first][u.second] = follow_paths(s, paths[u.first][u.second]) + 1;
}

int main()
{
  for (int maze_nr = 1; ; maze_nr++) {
    pair<int, int> s, g;
    scanf("%d %d %d %d %d %d",
      &nr_rows, &nr_columns, &s.first, &s.second, &g.first, &g.second);
    s.first--; s.second--; g.first--; g.second--;
    if (!nr_rows)
      break;
    for (int r = 0; r < nr_rows; r++)
      for (int c = 0; c < nr_columns; c++)
        scanf("%d", &walls[r][c]);

    memset(visited, 0, sizeof(visited));
    memset(cells, 0, sizeof(cells));
    if (dfs(s, g))
      follow_paths(s, g);
    for (int r = 0; r < nr_rows; r++)
      for (int c = 0; c < nr_columns; c++)
        if (visited[r][c] && !cells[r][c])
          cells[r][c] = -1;
    printf("Maze %d\n\n", maze_nr);
    putchar('+');
    for (int c = 0; c < nr_columns; c++)
      printf("---+");
    putchar('\n');
    for (int r = 0; r < nr_rows; r++) {
      putchar('|');
      for (int c = 0; c < nr_columns; c++) {
        if (cells[r][c] > 0)
          printf("%3d", cells[r][c]);
        else if (cells[r][c] < 0)
          printf("???");
        else
          printf("   ");
        putchar((walls[r][c] & 1 || c == nr_columns - 1) ? '|' : ' ');
      }
      putchar('\n');
      if (r < nr_rows - 1) {
        putchar('+');
        for (int c = 0; c < nr_columns; c++)
          if (walls[r][c] & 2)
            printf("---+");
          else
            printf("   +");
        printf("\n");
      }
    }
    putchar('+');
    for (int c = 0; c < nr_columns; c++)
      printf("---+");
    printf("\n\n\n");
  }
  return 0;
}

UVa 928 - Eternal Truths

Accepted date: 2014-12-14
Ranking (as of 2014-12-14): 73 out of 444
Language: C++

/*
  UVa 928 - Eternal Truths

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

#include <queue>
#include <utility>
#include <cstdio>
using namespace std;

const int R_max = 300, C_max = 300, nr_steps = 3;
char maze[R_max][C_max + 1];
bool visited[R_max][C_max][nr_steps + 1];

int bfs(int R, int C, const pair<int, int>& s, const pair<int, int>& e)
{
  const int nr_dirs = 4;
  const pair<int, int> dirs[nr_dirs] =
    {make_pair(1, 0), make_pair(0, 1), make_pair(-1, 0), make_pair(0, -1)};
  for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++)
      for (int s = 1; s <= nr_steps; s++)
        visited[r][c][s] = false;
  queue< pair<pair<int, int>, int> > q;
  q.push(make_pair(s, 0));
  while (!q.empty()) {
    pair<pair<int, int>, int> p = q.front(); q.pop();
    if (p.first == e)
      return p.second;
    int s = (p.second + 1) % nr_steps;
    if (!s)
      s = nr_steps;
    for (int i = 0; i < nr_dirs; i++)
      for (int j = 1; j <= s; j++) {
        int r = p.first.first + j * dirs[i].first,
          c = p.first.second + j * dirs[i].second;
        if (r < 0 || r >= R || c < 0 || c >= C || maze[r][c] == '#')
          break;
        if (j == s && !visited[r][c][s]) {
#ifdef DEBUG
          printf("%d %d %d %d\n", r, c, s, p.second + 1);
#endif
          visited[r][c][s] = true;
          q.push(make_pair(make_pair(r, c), p.second + 1));
        }
      }
  }
  return -1;
}

int main()
{
  int nr_cases;
  scanf("%d", &nr_cases);
  while (nr_cases--) {
    int R, C;
    scanf("%d %d", &R, &C);
    getchar();
    pair<int, int> s, e;
    s.first = e.first = -1;
    for (int r = 0; r < R; r++) {
      gets(maze[r]);
      for (int c = 0; c < C; c++)
        if (s.first == -1 && maze[r][c] == 'S')
          s = make_pair(r, c);
        else if (e.first == -1 && maze[r][c] == 'E')
          e = make_pair(r, c);
    }
    int nr_moves = bfs(R, C, s, e);
    if (nr_moves != -1)
      printf("%d\n", nr_moves);
    else
      puts("NO");
  }
  return 0;
}

UVa 11945 - Financial Management

Accepted date: 2014-12-11
Language: JAVA

// UVa 11945 - Financial Management

import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    for (int n = 1; n <= N; n++) {
      double s = 0.0;
      for (int i = 0; i < 12; i++)
        s += sc.nextDouble();
      System.out.printf("%d $%,.2f\n", n, s / 12.0);
    }
  }
}

UVa 10917 - A Walk Through the Forest

Accepted date: 2014-12-07
Ranking (as of 2014-12-07): 254 out of 674
Language: C++

/*
  UVa 10917 - A Walk Through the Forest

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

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

struct edge {
  int v_;
  int w_;
  edge(int v, int w) : v_(v), w_(w) {}
};

struct distance_comparator {
  const vector<int>& distances_;

  distance_comparator(const vector<int>& distances) : distances_(distances) {}
  bool operator() (int i, int j) const
  {
    return (distances_[i] != distances_[j]) ? distances_[i] < distances_[j] : i < j;
  }
};

int dijkstra_shortest_path(int n, int start, int end,
  const vector< vector<edge> >& edges, vector<int>& distances)
{
  vector<bool> visited(n, false);
  set<int, distance_comparator> pq(distances); // priority queue
  distances[start] = 0;
  pq.insert(start);
  while(!pq.empty()) {
    int u = *pq.begin();
    pq.erase(pq.begin());
    visited[u] = true;
    if (u == end)
      break;
    int d = distances[u];
    const vector<edge>& es = edges[u];
    for (size_t i = 0, j = es.size(); i < j; i++) {
      int v = es[i].v_, w = es[i].w_;
      if (!visited[v] && distances[v] > d + w) {
        pq.erase(v); // remove v if it has already been in the queue
        distances[v] = d + w;
        pq.insert(v);
      }
    }
  }
  return distances[end];
}

void bfs(int n, int start, const vector< vector<edge> >& edges,
  const vector<int>& distances, vector<int>& routes)
{
  routes[start] = 1;
  vector<bool> visited(n, false);
  priority_queue<int, vector<int>, distance_comparator> pq(distances);
  visited[start] = true;
  pq.push(start);
  while (!pq.empty()) {
    int u = pq.top(); pq.pop();
    const vector<edge>& es = edges[u];
    for (size_t i = 0, j = es.size(); i < j; i++) {
      int v = es[i].v_;
      if (distances[u] > distances[v]) {
        if (visited[v])
          routes[v] += routes[u];
        else {
          visited[v] = true;
          routes[v] = routes[u];
          pq.push(v);
        }
      }
    }
  }
}

int main()
{
  while (true) {
    int n, m;
    cin >> n;
    if (!n)
      break;
    cin >> m;
    vector< vector<edge> > edges(n);
    while (m--) {
      int u, v, d;
      cin >> u >> v >> d;
      u--; v--;
      edges[u].push_back(edge(v, d));
      edges[v].push_back(edge(u, d));
    }
    vector<int> distances(n, numeric_limits<int>::max());
    dijkstra_shortest_path(n, 1, 0, edges, distances);
    vector<int> routes(n, 0);
    bfs(n, 0, edges, distances, routes);
    cout << routes[1] << endl;
  }
  return 0;
}

UVa 10307 - Killing Aliens in Borg Maze

Accepted date: 2014-12-03
Ranking (as of 2014-12-03): 138 out of 821
Language: C++

/*
  UVa 10307 - Killing Aliens in Borg Maze

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

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

const int x_max = 50, y_max = 50;
char maze[y_max][x_max + 1];

struct edge {
  int v_;
  int w_;
  edge(int v, int w) : v_(v), w_(w) {}
};

void bfs(int x, int y, int u, const pair<int, int>& p, vector<int>& sa_distances)
{
  const int nr_dirs = 4;
  const pair<int, int> dirs[nr_dirs] =
    {make_pair(1, 0), make_pair(0, 1), make_pair(-1, 0), make_pair(0, -1)};

  vector< vector<int> > distances(y, vector<int>(x, -1));
  queue< pair<int, int> > q;
  distances[p.first][p.second] = 0;
  sa_distances[u] = 0;
  q.push(p);
  while (!q.empty()) {
    pair<int, int> pu = q.front(); q.pop();
    for (int i = 0; i < nr_dirs; i++) {
      int j = pu.first + dirs[i].first, k = pu.second + dirs[i].second;
      if (maze[j][k] != '#' && distances[j][k] == -1) {
        distances[j][k] = distances[pu.first][pu.second] + 1;
        if (maze[j][k] != ' ')
          sa_distances[-maze[j][k]] = distances[j][k];
        q.push(make_pair(j, k));
      }
    }
  }
}

struct distance_comparator {
  const vector<int>& distances_;

  distance_comparator(const vector<int>& distances) : distances_(distances) {}
  bool operator() (int i, int j) const
  {
    return (distances_[i] != distances_[j]) ? distances_[i] < distances_[j] : i < j;
  }
};

int mst_prim(int n, const vector< vector<edge> >& edges)
{
  vector<bool> visited(n, false);
  vector<int> distances(n, numeric_limits<int>::max());
  distances[0] = 0;
  int mst_distance = 0;
  set<int, distance_comparator> pq(distances); // priority queue
  pq.insert(0);
  while (!pq.empty()) {
    int u = *pq.begin();
    pq.erase(pq.begin());
    visited[u] = true;
    mst_distance += distances[u];
    const vector<edge>& es = edges[u];
    for (size_t i = 0, j = es.size(); i < j; i++) {
      int v = es[i].v_, w = es[i].w_;
      if (!visited[v] && w < distances[v]) {
        pq.erase(v); // remove v if it has already been in the queue
        distances[v] = w;
        pq.insert(v);
      }
    }
  }
  return mst_distance;
}

int main()
{
  int N;
  scanf("%d", &N);
  while (N--) {
    int x, y;
    scanf("%d %d", &x, &y);
    getchar(); // skip '\n'
    int s = 0, n = 0; // total number of the start and the aliens
    vector< pair<int, int> > points; // positions of the start and the aliens
    for (int i = 0; i < y; i++) {
      gets(maze[i]);
      for (int j = 0; j < x; j++)
        if (maze[i][j] == 'S') {
          points.insert(points.begin(), make_pair(i, j));
          s++;
          maze[i][j] = 0;
        }
        else if (maze[i][j] == 'A') {
          points.push_back(make_pair(i, j));
          n++;
          maze[i][j] = -n;
        }
    }
    if (!s || !n) {
      puts("0"); continue;
    }
    n++; // n += s
    vector< vector<edge> > edges(n);
    // calculate the distances between the start and the aliens
    for (int i = 0; i < n; i++) {
      vector<int> distances(n, -1);
      bfs(x, y, i, points[i], distances);
      vector<edge>& es = edges[i];
      for (int j = 0; j < n; j++)
        if (i != j && distances[j] != -1)
          es.push_back(edge(j, distances[j]));
#ifdef DEBUG
      printf("%d: [%d %d] ", i, points[i].first, points[i].second);
      for (size_t j = 0; j < es.size(); j++)
        printf("%d: %d%c", es[j].v_, es[j].w_, ((j < es.size() - 1) ? ' ' : '\n'));
#endif
    }
    // apply Prim's minimum spanning tree algorithm
    printf("%d\n", mst_prim(n, edges));
  }
  return 0;
}

UVa 12247 - Jollo

Accepted date: 2014-12-02
Language: C++

/*
  UVa 12247 - Jollo

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

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

const int nr_cards = 52, nr_rounds = 3;

int main()
{
  while (true) {
    vector<int> princess(nr_rounds), prince(nr_rounds - 1);
    cin >> princess[0] >> princess[1] >> princess[2] >> prince[0] >> prince[1];
    if (!princess[0])
      break;
    sort(princess.begin(), princess.end()); // sort in ascending order
    if (prince[0] < prince[1])
      swap(prince[0], prince[1]); // sort in descending order
    vector<bool> discards(nr_cards + 1, false);

    // 1st round
    // Prince loses with the pair of cards that has the minimum positive difference.
    int min_diff = nr_cards, min_i, min_j;
    for (int i = 0; i < nr_rounds; i++)
      for (int j = 0; j < nr_rounds - 1; j++) {
        int diff = princess[i] - prince[j];
        if (diff > 0 && diff < min_diff) {
          min_diff = diff;
          min_i = i; min_j = j;
        }
      }
    if (min_diff == nr_cards) {
      // Prince will win two rounds with the current set of cards
      for (int i = 0; i < nr_rounds; i++)
        discards[princess[i]] = true;
      for (int i = 0; i < nr_rounds - 1; i++)
        discards[prince[i]] = true;
      for (int i = 1; i <= nr_cards; i++)
        if (!discards[i]) {
          cout << i << endl;
          break;
        }
      continue;
    }
#ifdef DEBUG
    cout << princess[min_i] << ' ' << prince[min_j] << endl;
#endif
    discards[princess[min_i]] = discards[prince[min_j]] = true;
    princess.erase(princess.begin() + min_i); prince.erase(prince.begin() + min_j);

    // 2nd round
    // Prince wins with the pair of remaining cards that has 
    // the maximum negative difference.
    min_diff = 0;
    for (int i = 0; i < nr_rounds - 1; i++) {
      int diff = princess[i] - prince[0];
      if (diff > 0) {
        min_diff = 0; break;
      }
      else if (diff < min_diff) {
        min_diff = diff;
        min_i = i;
      }
    }
    if (!min_diff) { // Prince will lose two rounds with the current set of cards
      cout << -1 << endl;
      continue;
    }

#ifdef DEBUG
    cout << princess[min_i] << ' ' << prince[0] << endl;
#endif
    discards[princess[min_i]] = discards[prince[0]] = true;
    princess.erase(princess.begin() + min_i);

    // 3rd round
    // Prince wins with a card that is greater than the Princess's remaining card, 
    // excluding the ones that have already been discarded.
    int p = princess[0] + 1;
    for ( ; p <= nr_cards; p++)
      if (!discards[p])
        break;
    cout << ((p <= nr_cards) ? p : -1) << endl;
  }
  return 0;
}