UVa 1056 - Degrees of Separation

Accepted date: 2015-04-29
Ranking (as of 2015-04-29): 186 out of 422
Language: C++

/*
  UVa 1056 - Degrees of Separation

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

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

int main()
{
  for (int n = 1; ; n++) {
    int P, R;
    cin >> P >> R;
    if (!P)
      break;
    vector< vector<int> > matrix(P, vector<int>(P, P));
    map<string, size_t> names;
    while (R--) {
      string s, t;
      pair<map<string, size_t>::iterator, bool> result;
      cin >> s >> t;
      int i, j;
      result = names.insert(make_pair(s, names.size()));
      i = result.first->second;
      result = names.insert(make_pair(t, names.size()));
      j = result.first->second;
      matrix[i][j] = matrix[j][i] = 1;
    }
    for (int k = 0; k < P; k++)
      for (int i = 0; i < P; i++)
        for (int j = 0; j < P; j++)
          matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
    int min_degrees = 0;
    for (int i = 0; i < P - 1; i++)
      for (int j = i + 1; j < P; j++)
        min_degrees = max(min_degrees, matrix[i][j]);
    cout << "Network " << n << ": ";
    if (min_degrees < P)
      cout << min_degrees << endl << endl;
    else
      cout << "DISCONNECTED\n\n";
  }
  return 0;
}

UVa 12515 - Movie Police

Accepted date: 2015-04-23
Ranking (as of 2015-04-23): 11 out of 160
Language: C++

/*
  UVa 12515 - Movie Police

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

#include <cstdio>
#include <cstring>

const int M_max = 1000, l_max = 127;

struct signature {
  int l_;
  char s_[l_max + 1];
} signatures[M_max];

int main()
{
  int M, Q;
  scanf("%d %d", &M, &Q);
  for (int i = 0; i < M; i++) {
    scanf("%s", signatures[i].s_);
    signatures[i].l_ = strlen(signatures[i].s_);
  }
  while (Q--) {
    char clip[l_max + 1];
    scanf("%s", clip);
    int l = strlen(clip);
    int min_i = 0, min_hd = l + 1;
    for (int i = 0; i < M && min_hd; i++) {
      const signature& s = signatures[i];
      if (s.l_ >= l) {
        int hd = l + 1;
        for (int j = 0; j <= s.l_ - l; j++) {
          int d = 0;
          for (int k = 0; k < l && d < hd && d < min_hd; k++)
            if (s.s_[j + k] != clip[k])
              d++;
          if (d < hd)
            hd = d;
        }
        if (hd < min_hd) {
          min_i = i; min_hd = hd;
        }
      }
    }
    printf("%d\n", min_i + 1);
  }
  return 0;
}

UVa 10950 - Bad Code

Accepted date: 2015-04-21
Ranking (as of 2015-04-21): 33 out of 259
Language: C++

/*
  UVa 10950 - Bad Code

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

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

const int nr_letters = 26, nr_code_chars_max = 3, nr_encrypted_chars_max = 100;

struct code {
  char c_;
  int l_;
  char s_[nr_code_chars_max + 1];

  bool operator<(const code& c) const {return c_ < c.c_;}
} codes[nr_letters];

char encrypted[nr_encrypted_chars_max + 1], text[nr_encrypted_chars_max + 1];

bool plain_text(int n, int el, int ei, int ti, int& nr)
{
  if (ei == el) {
    text[ti] = '\0';
    puts(text);
    nr++;
    return nr == 100;
  }
  else {
    for (int ci = 0; ci < n; ci++) {
      const code& c = codes[ci];
      if (el - ei >= c.l_) {
        if (c.l_ == 1 && encrypted[ei] == c.s_[0]) {
          text[ti] = c.c_;
          if (plain_text(n, el, ei + 1, ti + 1, nr))
            return true;
        }
        else if (c.l_ == 2 &&
          encrypted[ei] == c.s_[0] && encrypted[ei + 1] ==  c.s_[1]) {
          text[ti] = c.c_;
          if (plain_text(n, el, ei + 2, ti + 1, nr))
            return true;
        }
      }
      if (encrypted[ei] == '0' && el - ei - 1 >= c.l_) {
        if (c.l_ == 1 && encrypted[ei + 1] == c.s_[0]) {
          text[ti] = c.c_;
          if (plain_text(n, el, ei + 2, ti + 1, nr))
            return true;
        }
        else if (c.l_ == 2 &&
          encrypted[ei + 1] == c.s_[0] && encrypted[ei + 2] ==  c.s_[1]) {
          text[ti] = c.c_;
          if (plain_text(n, el, ei + 3, ti + 1, nr))
            return true;
        }
      }
    }
    return false;
  }
}

int main()
{
  for (int case_nr = 1; ; case_nr++) {
    int N;
    scanf("%d", &N);
    if (!N)
      break;
    for (int i = 0; i < N; i++) {
      char letter[2];
      scanf("%s", letter);
      code& c = codes[i];
      c.c_ = letter[0];
      scanf("%s", c.s_);
      c.l_ = strlen(c.s_);
    }
    sort(codes, codes + N);
    scanf("%s", encrypted);
    printf("Case #%d\n", case_nr);
    int nr = 0;
    plain_text(N, strlen(encrypted), 0, 0, nr);
    putchar('\n');
  }
  return 0;
}

UVa 759 - The Return of the Roman Empire

Accepted date: 2015-04-15
Ranking (as of 2015-04-15): 157 out of 445
Language: C++

/*
  UVa 759 - The Return of the Roman Empire

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

#include <iostream>
#include <string>
using namespace std;

int roman_numeral(const char* s)
{
  int n = 0;
  while (*s) {
    const char* ns = s + 1;
    int d = 0;
    switch (*s) {
    case 'I':
      if (n % 10)
        return -1;
      if (*ns && (*ns == 'V' || *ns == 'X')) {
        d = (*ns == 'V') ? 4 : 9;
        ns++;
      }
      else {
        d++;
        while (*ns && *ns == 'I') {
          if (++ns - s > 3)
            return -1;
          d++;
        }
      }
      break;
    case 'V':
      if (n % 10)
        return -1;
      d = 5;
      while (*ns && *ns == 'I') {
        if (++ns - s > 4)
          return -1;
        d++;
      }
      break;
    case 'X':
      if ((n % 100) / 10 || n % 10)
        return -1;
      if (*ns && (*ns == 'L' || *ns == 'C')) {
        d = (*ns == 'L') ? 40 : 90;
        ns++;
      }
      else {
        d = 10;
        while (*ns && *ns == 'X') {
          if (++ns - s > 3)
            return -1;
          d += 10;
        }
      }
      break;
    case 'L':
      if ((n % 100) / 10 || n % 10)
        return -1;
      d = 50;
      while (*ns && *ns == 'X') {
        if (++ns - s > 4)
          return -1;
        d += 10;
      }
      break;
    case 'C':
      if ((n % 1000) / 100 || n % 100)
        return -1;
      if (*ns && (*ns == 'D' || *ns == 'M')) {
        d = (*ns == 'D') ? 400 : 900;
        ns++;
      }
      else {
        d = 100;
        while (*ns && *ns == 'C') {
          if (++ns - s > 3)
            return -1;
          d += 100;
        }
      }
      break;
    case 'D':
      if ((n % 1000) / 100 || n % 100)
        return -1;
      d = 500;
      while (*ns && *ns == 'C') {
        if (++ns - s > 4)
          return -1;
        d += 100;
      }
      break;
    case 'M':
      if (n / 1000 || n % 1000)
        return -1;
      d = 1000;
      while (*ns && *ns == 'M') {
        if (++ns - s > 3)
          return -1;
        d += 1000;
      }
      break;
    default:
      return -1;
    }
    n += d;
    s = ns;
  }
  return n;
}

int main()
{
  string s;
  while (getline(cin, s)) {
    int n = roman_numeral(s.c_str());
    if (n >= 0)
      cout << n << endl;
    else
      cout << "This is not a valid number\n";
  }
  return 0;
}

UVa 10961 - Chasing After Don Giovanni

Accepted date: 2015-04-13
Ranking (as of 2015-04-13): 74 out of 83
Language: C++

/*
  UVa 10961 - Chasing After Don Giovanni

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

#include <cstdio>

const int ns_max = 100;

struct stop {
  int s_, a_;

  stop() {}
  stop(int s, int a) : s_(s), a_(a) {}
  stop(const stop& s) : s_(s.s_), a_(s.a_) {}
  bool operator==(const stop& s) const {return s_ == s.s_ && a_ == s.a_;}
  bool operator!=(const stop& s) const {return s_ != s.s_ || a_ != s.a_;}

} gs[ns_max + 1], ls[ns_max + 1];

bool move(stop& current, const stop& next)
{
  if (current != next) {
    if (current.s_ != next.s_) {
      if (current.s_ < next.s_)
        current.s_++;
      else
        current.s_--;
    }
    else {
      if (current.a_ < next.a_)
        current.a_++;
      else
        current.a_--;
    }
  }
  return current == next;
}

int main()
{
  int nc;
  scanf("%d", &nc);
  while (nc--) {
    scanf("%d %d", &gs[0].s_, &gs[0].a_);
    scanf("%d %d", &ls[0].s_, &ls[0].a_);
    int gn, ln;
    scanf("%d", &ln);
    ln++;
    for (int i = 1; i < ln; i++)
      scanf("%d %d", &ls[i].s_, &ls[i].a_);
    scanf("%d", &gn);
    gn++;
    for (int i = 1; i < gn; i++)
      scanf("%d %d", &gs[i].s_, &gs[i].a_);
    int li = 0, gi = 0;
    stop l(ls[0]), g(gs[0]);
    while (li < ln - 1 && gi < gn - 1) {
      if (l == g)
        break;
      if (move(l, ls[li + 1]))
        li++;
      if (move(g, gs[gi + 1]))
        gi++;
#ifdef DEBUG
      printf("l: [%d, %d], g: [%d, %d]\n", l.s_, l.a_, g.s_, g.a_);
#endif
    }
    puts((l == g && li != ln - 1) ? "No" : "Yes");
    if (nc)
      putchar('\n');
  }
  return 0;
}

UVa 939 - Genes

Accepted date: 2015-04-11
Ranking (as of 2015-04-11): 54 out of 134
Language: C++

/*
  UVa 939 - Genes

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

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

const int N_max = 3100;

map<string, int> names;

enum {non_existent, recessive, dominant};

const int nr_status = dominant - non_existent + 1;

const string status_strings[nr_status] = {
  "non-existent", "recessive", "dominant"
};

const int hypothesis[nr_status][nr_status] = {
  {non_existent, non_existent, recessive},
  {non_existent, recessive, dominant},
  {recessive, dominant, dominant}
};

struct person {
  int parent_, other_parent_;
  int status_;
} persons[N_max];

int get_status(int pi)
{
  if (persons[pi].status_ != -1)
    return persons[pi].status_;
  int parent_status = get_status(persons[pi].parent_),
    other_parent_status = get_status(persons[pi].other_parent_);
  return persons[pi].status_ = hypothesis[parent_status][other_parent_status];
}

int main()
{
  int N;
  cin >> N;
  for (int i = 0; i < N; i++)
    persons[i].parent_ = persons[i].other_parent_ = persons[i].status_ = -1;
  int nr_persons = 0;
  while (N--) {
    string s, t;
    cin >> s >> t;
    pair<map<string, int>::iterator, bool> result =
      names.insert(make_pair(s, nr_persons));
    int pi = result.first->second;
    if (result.second)
      nr_persons++;
    int i;
    for (i = 0; i < nr_status; i++)
      if (t == status_strings[i]) {
        persons[pi].status_ = i;
        break;
      }
    if (i == nr_status) {
      result = names.insert(make_pair(t, nr_persons));
      person& c = persons[result.first->second];
      if (c.parent_ == -1)
        c.parent_ = pi;
      else
        c.other_parent_ = pi;
      if (result.second)
        nr_persons++;
    }
  }
  for (map<string, int>::const_iterator ni = names.begin(), ne = names.end();
    ni != ne; ++ni)
    cout << ni->first << ' ' << status_strings[get_status(ni->second)] << endl;
  return 0;
}

UVa 447 - Population Explosion

Accepted date: 2015-04-10
Ranking (as of 2015-04-10): 91 out of 454
Language: C++

/*
  UVa 447 - Population Explosion

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

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

const int nr_quarters = 20;

char quarters[2][nr_quarters][nr_quarters + 1];

void init_quarters(char q[nr_quarters][nr_quarters + 1])
{
  for (int i = 0; i < nr_quarters; i++)
    for (int j = 0; j < nr_quarters; j++)
      q[i][j] = ' ';
}

void print_quarters(char q[nr_quarters][nr_quarters + 1])
{
  puts("********************");
  for (int i = 0; i < nr_quarters; i++)
    puts(q[i]);
}

int main()
{
  const int nr_dirs = 8;
  int dirs[nr_dirs][2] =
    {{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}};

  int nr_cases;
  scanf("%d", &nr_cases);
  while (nr_cases--) {
    int nr_years;
    scanf("%d", &nr_years);
    while (getchar() != '\n')
      ;
    char (*pq)[nr_quarters][nr_quarters + 1] = &quarters[0],
      (*cq)[nr_quarters][nr_quarters + 1] = &quarters[1];
    init_quarters(*pq);
    int c;
    while ((c = getchar()) != '\n' && c != EOF) {
      ungetc(c, stdin);
      int i, j;
      scanf("%d %d", &i, &j);
      (*pq)[i - 1][j - 1] = 'O';
      while (getchar() != '\n')
        ;
    }
    if (nr_years--)
      print_quarters(*pq);
    while (nr_years-- > 0) {
      init_quarters(*cq);
      for (int i = 0; i < nr_quarters; i++)
        for (int j = 0; j < nr_quarters; j++) {
          int n = 0;
          for (int k = 0; k < nr_dirs; k++) {
            int ci = i + dirs[k][0], cj = j + dirs[k][1];
            if (ci >= 0 && ci < nr_quarters && cj >= 0 && cj < nr_quarters &&
              (*pq)[ci][cj] == 'O')
              n++;
          }
          if ((*pq)[i][j] == 'O') {
            if (n == 2 || n == 3)
              (*cq)[i][j] = 'O';
          }
          else {
            if (n == 3)
              (*cq)[i][j] = 'O';
          }
        }
      print_quarters(*cq);
      swap(pq, cq);
    }
    puts("********************");
    if (nr_cases)
      putchar('\n');
  }
  return 0;
}

UVa 857 - Quantiser

Accepted date: 2015-04-08
Ranking (as of 2015-04-08): 43 out of 153
Language: C++

/*
  UVa 857 - Quantiser

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

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

const int n_max = 2000;

struct timestamp {
  int i_, note_, m_, b_, t_;

  timestamp() {}
  timestamp(int i, int note, int m, int b, int t)
    : i_(i), note_(note), m_(m), b_(b), t_(t) {}

  bool operator<(const timestamp& t) const {
    if (m_ != t.m_)
      return m_ < t.m_;
    else if (b_ != t.b_)
      return b_ < t.b_;
    else if (t_ != t.t_)
      return t_ < t.t_;
    else
      return note_ < t.note_;
  }
};

struct message {
  int code_, note_, m_, b_, t_;
  bool filtered_;

  bool operator<(const message& m) const {
    if (m_ != m.m_)
      return m_ < m.m_;
    else if (b_ != m.b_)
      return b_ < m.b_;
    else
      return t_ < m.t_;
  }
} messages[n_max];

int main()
{
  while (true) {
    int n;
    scanf("%d", &n);
    if (n == -1) {
      printf("%d\n", n);
      break;
    }
    int nr_messages = 0;
    multiset<timestamp> timestamps;
    for (int i = 0; i < n; i++) {
      message& m = messages[nr_messages];
      m.filtered_ = false;
      scanf("%d %d %d %d %d", &m.code_, &m.note_, &m.m_, &m.b_, &m.t_);
      int j = m.t_ / 60, k = m.t_ % 60;
      if (k >= 30)
        j++;
      if ((m.t_ = 60 * j) == 480) {
        m.t_ = 0;
        if ((m.b_ += 1) == 5) {
          m.b_ = 1;
          m.m_++;
        }
      }
#ifdef DEBUG
      printf("    %d %d %d %d %d\n", m.code_, m.note_, m.m_, m.b_, m.t_);
#endif
      timestamp ts(nr_messages, m.note_, m.m_, m.b_, m.t_);
      if (m.code_) {
        timestamps.insert(ts);
        nr_messages++;
      }
      else {
        pair<multiset<timestamp>::iterator, multiset<timestamp>::iterator>
          result = timestamps.equal_range(ts);
        if (result.first == result.second)
          nr_messages++;
        else {
          for (multiset<timestamp>::iterator ti = result.first;
            ti != result.second; ++ti)
            messages[ti->i_].filtered_ = true;
        }
      }
    }
    stable_sort(messages, messages + nr_messages);
    int nr_filtered = 0;
    for (int i = 0; i < nr_messages; i++)
      if (messages[i].filtered_)
        nr_filtered++;
    printf("%d\n", nr_messages - nr_filtered);
    for (int i = 0; i < nr_messages; i++) {
      const message& m = messages[i];
      if (!m.filtered_)
        printf("%d %d %d %d %d\n", m.code_, m.note_, m.m_, m.b_, m.t_);
    }
  }
  return 0;
}

UVa 906 - Rational Neighbor

Accepted date: 2015-04-07
Ranking (as of 2015-04-07): 33 out of 153
Language: C++

/*
  UVa 906 - Rational Neighbor

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

#include <cstdio>
#include <cmath>

int main()
{
  long long a, b;
  while (scanf("%lld %lld", &a, &b) != EOF) {
    double n;
    scanf("%lf", &n);
    long long m = static_cast<long long>(ceil(1.0 / (n * b)));
    long long c, d;
    bool done = false;
    for (d = m; ; d++) {
      for (c = static_cast<long long>(static_cast<double>(a) * d / b); ; c++) {
        long long e = b * c - a * d;
        if (e <= 0)
          continue;
        if (e <= n * b * d) {
          done = true;
          break;
        }
        else
          break;
      }
      if (done)
        break;
    }
    printf("%lld %lld\n", c, d);
  }
  return 0;
}

UVa 12542 - Prime Substring

Accepted date: 2015-04-04
Ranking (as of 2015-04-04): 124 out of 427
Language: C++

/*
  UVa 12542 - Prime Substring

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

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

const int n_max = 100000;
bool not_primes[n_max + 1]; // not_primes[i] is true if i is not a prime

void sieve_of_eratosthenes()
{
  for (int i = 2, e = static_cast<int>(sqrt(static_cast<double>(n_max))); i <= e; i++)
    if (!not_primes[i]) {
      for (int j = i * i; j <= n_max; j += i)
        not_primes[j] = true;
    }
}

const int nr_digits_max = 255, nr_prime_digits_max = 6;

int number(const char* s, int i, int j)
{
  int n = 0;
  for ( ; i < j; i++) {
    n *= 10;
    n += s[i] - '0';
  }
  return n;
}

int main()
{
  sieve_of_eratosthenes();
  while (true) {
    char s[nr_digits_max + 1];
    scanf("%s", s);
    int length = strlen(s);
    if (length == 1 && s[0] == '0')
      break;
    int max_prime = 0;
    for (int i = 0; i < length; i++)
      for (int j = i + 1; j <= i + nr_prime_digits_max && j <= length; j++) {
        int n = number(s, i, j);
        if (n <= n_max && !not_primes[n] && n > max_prime)
          max_prime = n;
      }
    printf("%d\n", max_prime);
  }
  return 0;
}

UVa 10430 - Dear GOD

Accepted date: 2015-04-01
Ranking (as of 2015-04-01): 156 out of 183
Language: JAVA

//  UVa 10430 - Dear GOD

import java.util.Scanner;
import java.math.BigInteger;

class Main {
  public static void main(String[] args) {
    System.out.println("Dear GOD, Pardon Me");
      Scanner sc = new Scanner(System.in);
    boolean printed = false;
    while (sc.hasNextInt()) {
      if (printed)
        System.out.println();
      else
        printed = true;
      int t = sc.nextInt();
      if (t == 1) {
        int n = sc.nextInt();
        System.out.println("X = " + n);
        System.out.println("K = " + 1);
      }
      else {
        BigInteger T = BigInteger.valueOf(t);
        int n = sc.nextInt();
        // X * T^n = K * (T^n - 1) / (T - 1)
        BigInteger Tp = T.pow(n); // T^n
        BigInteger Ts =
          Tp.subtract(BigInteger.ONE).divide(T.subtract(BigInteger.ONE));
          // (T^n - 1) / (T - 1)
        BigInteger gcd = Tp.gcd(Ts);
        System.out.println("X = " + Ts.divide(gcd));
        System.out.println("K = " + Tp.divide(gcd));
      }
    }
  }
}