UVa 1590 - IP Networks

Accepted date: 2017-01-19
Run Time: 0.000
Ranking (as of 2017-01-19): 90 out of 362
Language: C++

Network_address = IP_address & Network_mask.
And for all IP addresses, Network address should be the same.

/*
  UVa 1590 - IP Networks

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

#include <cstdio>

const int m_max = 1000;
unsigned int ip_addresses[m_max];

void print_address(unsigned int address)
{
  printf("%u.%u.%u.%u\n", (address & 0xff000000) >> 24, (address & 0x00ff0000) >> 16,
    (address & 0x0000ff00) >> 8, address & 0x000000ff);
}

int main()
{
  const int nr_bits = 32;
  int m;
  while (scanf("%d", &m) != EOF) {
    for (int i = 0; i < m;i++) {
      int b0, b1, b2, b3;
      scanf("%d.%d.%d.%d", &b0, &b1, &b2, &b3);
      ip_addresses[i] = b0 << 24 | b1 << 16 | b2 << 8 | b3;
    }
    unsigned int mask = 0xffffffff, b = 1, address;
    for (int i = 0; i <= nr_bits; i++, mask &= ~b, b <<= 1) {
      address = ip_addresses[0] & mask;
      int j;
      for (j = 1; j < m; j++)
        if ((ip_addresses[j] & mask) != address)
          break;
      if (j == m)
        break;
    }
    print_address(address);
    print_address(mask);
  }
  return 0;
}

UVa 12321 - Gas Stations

Accepted date: 2017-01-17
Run Time: 0.030
Ranking (as of 2017-01-17): 79 out of 357
Language: C++

/*
  UVa 12321 - Gas Stations

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

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

const int G_max = 10000;

struct coverage {
  int l_, h_; // coverage is from l_ to h_

bool operator<(const coverage& c) const {return (l_ != c.l_) ? l_ < c.l_ : h_ < c.h_;}
} coverages[G_max];

int main()
{
  while (true) {
    int L, G;
    scanf("%d %d", &L, &G);
    if (!L)
      break;
    for (int i = 0; i < G; i++) {
      int xi, ri;
      scanf("%d %d", &xi, &ri);
      coverages[i].l_ = max(xi - ri, 0), coverages[i].h_ = min(xi + ri, L);
    }
    sort(coverages, coverages + G); // sort the stations by thier lower ends
#ifdef DEBUG
    for (int i = 0; i < G; i++)
      printf("[%d %d]%c", coverages[i].l_, coverages[i].h_, ((i < G - 1) ? ' ' : '\n'));
#endif
    int i = 0, h = 0, l = 0, nr = 0;
    for ( ; l < L && i < G; i++) {
      // discard the stations whose lower end is covered by other station
      const coverage& c = coverages[i];
      if (c.l_ > l) {
        if (c.l_ <= h) {
          l = h, h = 0, nr++;
          if (l == L)
            break;
        }
        else
          break;
      }
      h = max(h, c.h_);
    }
    if (h)
      l = h, nr++;
    printf("%d\n", (l == L) ? G - nr : -1);
  }
  return 0;
}

UVa 11926 - Multitasking

Accepted date: 2014-07-29
First verdict date: 2014-07-29
Last verdict date: 2016-12-20
Run Time: 0.000
Ranking (as of 2017-01-14): 239 out of 1233
Language: C++

/*
  UVa 11926 - Multitasking

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

#include <cstdio>
#include <cstring>

const int minutes_max = 1000000;

bool minutes[minutes_max + 1];

int main()
{
  while (true) {
    int n, m;
    scanf("%d %d", &n, &m);
    if (!n && !m)
      break;
    memset(minutes, 0, sizeof(minutes));
    bool conflict = false;
    while (n--) {
      int st, et;
      scanf("%d %d", &st, &et);
      if (conflict)
        continue;
      for (int i = st; i < et; i++) {
        if (minutes[i]) {
          conflict = true; break;
        }
        else
          minutes[i] = true;
      }
    }
    while (m--) {
      int st, et, ri;
      scanf("%d %d %d", &st, &et, &ri);
      if (conflict)
        continue;
      for (int i = 0; i <= minutes_max; i += ri) {
        for (int j = i + st; j <= minutes_max && j < i + et; j++) {
          if (minutes[j]) {
            conflict = true; break;
          }
          else
            minutes[j] = true;
        }
        if (conflict)
          break;
      }
    }
    puts(((conflict) ? "CONFLICT" : "NO CONFLICT"));
  }
  return 0;
}

UVa 465 - Overflow

Accepted date: 2011-07-23
First verdict date: 2011-07-23
Last verdict date: 2017-01-08
Run Time: 0.000
Ranking (as of 2017-01-14): 1144 out of 3584
Language: C++

/*
  UVa 465 - Overflow

  To build using Visucal Studio 2008:
    cl -EHsc -O2 overflow.cpp
*/

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

int main()
{
  string line;
  while (getline(cin, line)) {
    istringstream iss(line);
    double i, j;
    char op;
    iss >> i >> op >> j;
    double result = (op == '+') ?  i + j : i * j;
    cout << line << endl;
    if (i > numeric_limits<int>::max())
      cout << "first number too big\n";
    if (j > numeric_limits<int>::max())
      cout << "second number too big\n";
    if (result > numeric_limits<int>::max())
      cout << "result too big\n";
  }
  return 0;
}

UVa 12034 - Race

Accepted date: 2017-01-12
Run Time: 0.000
Ranking (as of 2016-01-12): 54 out of 401
Language: C++

An easy dynamic programming problem.

/*
  UVa 12034 - Race

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

#include <cstdio>

const int n_max = 1000, modulo = 10056;
int combinations[n_max + 1][n_max + 1];
int nr_ways[n_max + 1]; // nr_ways[i] is the number of way the race can finish with i horses

int main()
{
  // calculate the combinations
  for (int i = 0; i <= n_max; i++)
    combinations[i][0] = 1;
  for (int i = 0; i <= n_max; i++)
    combinations[i][i] = 1;
  for (int i = 1; i <= n_max; i++)
    for (int j = 1; j < i; j++)
      combinations[i][j] = (combinations[i - 1][j - 1] + combinations[i - 1][j]) % modulo;
  nr_ways[1] = 1;
  for (int i = 2; i <= n_max; i++) {
    int nr = 1;
    for (int j = 1; j < i; j++) {
      nr += combinations[i][j] * nr_ways[i - j] % modulo;
      nr %= modulo;
    }
    nr_ways[i] = nr;
  }
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int n;
    scanf("%d", &n);
    printf("Case %d: %d\n", t, nr_ways[n]);
  }
  return 0;
}

UVa 12238 - Ants Colony

Accepted date: 2017-01-11
Run Time: 0.330
Ranking (as of 2016-01-11): 31 out of 359
Language: C++

For explanation, see Range Minimum Query and Lowest Common Ancestor - topcoder.

/*
  UVa 12238 - Ants Colony

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

#include <algorithm>
#include <vector>
#include <cstdio>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

const int N_max = 100000;

struct edge {
  int v_;
  int weight_;
  edge(int v, int weight) : v_(v), weight_(weight) {}
};

vector<edge> edges[N_max];

const int level_max = 17; // ceil(log2(N_max))
int levels[N_max]; // level (depth) of node i in the tree
long long weights[N_max]; // weights[i] is the total length from the root to i-th node
int parents[N_max]; // parent node of i
int ancestors[N_max][level_max + 1];
  // ancestors[i][j] is the 2^j-th ancestor of node i

void dfs(int u, int parent, int level)
{
  levels[u] = level;
  const vector<edge>& mes = edges[u];
  for (size_t i = 0; i < mes.size(); i++) {
    int v = mes[i].v_, w = mes[i].weight_;
    if (v != parent) {
      parents[v] = u, weights[v] = w + weights[u];
      dfs(v, u, level + 1);
    }
  }
}

void process3(int n)
{
  for (int i = 0 ; i < n; i++) {
    // the first ancestor of every node i is parents[i]
    ancestors[i][0] = parents[i];
    for (int j = 1; 1 << j < n; j++)
      ancestors[i][j] = -1;
  }
  for (int j = 1; 1 << j < n; j++)
    for (int i = 0; i < n; i++)
      if (ancestors[i][j - 1] != -1)
        ancestors[i][j] = ancestors[ancestors[i][j - 1]][j - 1];
}

long long query(int p, int q)
{
  long long w = weights[p] + weights[q];
  //if p is situated on a higher level than q then we swap them
  if (levels[p] < levels[q])
    swap(p, q);
  // we compute the value of [log2(level[p)]
  int log;
  for (log = 1; 1 << log <= levels[p]; log++)
    ;
  log--;
  // we find the ancestor of node p situated on the same level
  // with q using the values in ancestors[][]
  for (int i = log; i >= 0; i--)
    if (levels[p] - (1 << i) >= levels[q])
      p = ancestors[p][i];
  if (p == q)
  return w - weights[p] * 2;
  // we compute LCA(p, q) using the values in ancestors[][]
  for (int i = log; i >= 0;i--)
    if (ancestors[p][i] != -1 && ancestors[p][i] != ancestors[q][i])
      p = ancestors[p][i], q = ancestors[q][i];
  return w - weights[parents[p]] * 2;
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  while (true) {
    int N;
    scanf("%d", &N);
    if (!N)
      break;
    for (int i = 0; i < N; i++)
      edges[i].clear();
    for (int v = 1; v < N; v++) {
      int u, w;
      scanf("%d %d", &u, &w);
      edges[u].push_back(edge(v, w)), edges[v].push_back(edge(u, w));
    }
    dfs(0, -1, 0);
    process3(N);
    int Q;
    scanf("%d", &Q);
    while (Q--) {
      int s, t;
      scanf("%d %d", &s, &t);
      printf("%lld%c", query(s, t), ((Q) ? ' ' : '\n'));
    }
  }
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0;
}

UVa 11732 - "strcmp()" Anyone?

Accepted date: 2017-01-09
Run Time: 0.110
Ranking (as of 2016-01-09): 2 out of 369
Language: C++

You can easily see that the below program works for some input cases of small N.

/*
  UVa 11732 - "strcmp()" Anyone?

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

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

const int N_max = 4000, nr_chars_max = 1000;

struct string {
  char s_[nr_chars_max + 1];

  bool operator<(const string& s) const {return strcmp(s_, s.s_) < 0;}
} strings[N_max];

int nr_comparisons[N_max];
  // nr_comparisons[i] is the number of comparisons between strings[i] and strings[i + 1]

int main()
{
  for (int c = 1; ; c++) {
    int N;
    scanf("%d", &N);
    if (!N)
      break;
    for (int i = 0; i < N; i++)
      scanf("%s", strings[i].s_);
    sort(strings, strings + N);
    for (int i = 0; i < N - 1; i++) {
      const char *cs = strings[i].s_, *ns = strings[i + 1].s_;
      int nr = 1;
      for ( ; *cs == *ns; nr++, cs++, ns++) {
        nr++;
        if (!*cs)
          break;
      }
      nr_comparisons[i] = nr;
    }
    long long T = 0;
    for (int i = 0; i < N - 1; i++) {
      int nr = nr_comparisons[i];
      T += nr;
      for (int j = i + 1; j < N - 1; j++) {
        if (nr_comparisons[j] < nr)
          nr = nr_comparisons[j];
        T += nr;
      }
    }
    printf("Case %d: %lld\n", c, T);
  }
  return 0;
}