UVa 11086 - Composite Prime

Accepted date: 2014-08-31
Ranking (as of 2014-08-31): 144 out of 569
Language: C++

/*
  UVa 11086 - Composite Prime

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

/*
4
3 4 6 8

3           3 is a prime number
4 = 2 * 2
6 = 2 * 3
8 = 2 * 4   4 is an element in M

5
12 13 21 22 23

12 = 3 * 4  4 is an element in M
13          13 is a prime number
21 = 3 * 7
22 = 3 * 11
23          23 is a prime number
*/

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

const int n_max = 1048576;
bool not_primes[n_max + 1]; // not_primes[i] is true if i is not a prime
bool not_composite_primes[n_max + 1];
  // composite_primes[i] is true if i is not a composite prime

void sieve_of_eratosthenes()
{
  not_primes[0] = not_primes[1] = true;
  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;
    }
}

void composite_primes()
{
  not_composite_primes[0] = not_composite_primes[1] =
    not_composite_primes[2] = not_composite_primes[3] = true;
  for (int i = 4; i <= n_max; i++)
    if (not_primes[i] && !not_composite_primes[i]) {
      for (int j = i * 2; j <= n_max; j += i)
        not_composite_primes[j] = true;
    }
}

int main()
{
  sieve_of_eratosthenes();
  composite_primes();
#ifdef DEBUG
  int nr_composite_primes = 0;
  for (int i = 4; i <= n_max; i++)
    if (not_primes[i] && !not_composite_primes[i])
      nr_composite_primes++;
  cout << nr_composite_primes << endl; // 219759
#endif
  int K;
  while (cin >> K) {
    int nr = 0;
    while (K--) {
      int n;
      cin >> n;
      if (not_primes[n] && !not_composite_primes[n])
        nr++;
    }
    cout << nr << endl;
  }
  return 0;
}

UVa 10520 - Determine it

Accepted date: 2014-08-29
Ranking (as of 2014-08-29): 178 out of 591
Language: C++

/*
  UVa 10520 - Determine it

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

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

const int n_max = 20;

long long a[n_max + 1][n_max + 1];

long long aij(int n, int i, int j)
{
  long long result = a[i][j];
  if (result != -1)
    return result;
  if (i < j) {
    for (int k = i; k < j; k++)
      result = max(result, aij(n, i, k) + aij(n, k + 1, j));
  }
  else {
    long long r0 = 0, r1 = 0;
    if (i < n)
      for (int k = i + 1; k <= n; k++) 
        r0 = max(r0, aij(n, k, 1) + aij(n, k, j));
    if (j > 0)
      for (int k = 1; k < j; k++)
        r1 = max(r1, aij(n, i, k) + aij(n, n, k));
    result = r0 + r1;
  }
  return a[i][j] = result;
}

int main()
{
  int n, an1;
  while (cin >> n >> an1) {
    memset(a, -1, sizeof(a));
    a[n][1] = an1;
    cout << aij(n, 1, n) << endl;
  }
  return 0;
}

UVa 941 - Permutations

Accepted date: 2014-08-26
Ranking (as of 2014-08-26): 119 out of 847
Language: C++

/*
  UVa 941 - Permutations

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

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

int main()
{
  const int nr_chars_max = 20;
  long long factorials[nr_chars_max];
    // factorials[i] is i!
  factorials[0] = factorials[1] = 1;
  for (int i = 2; i < nr_chars_max; i++)
    factorials[i] = factorials[i - 1] * i;

  int nr_samples;
  scanf("%d", &nr_samples);
  while (nr_samples--) {
    char S[nr_chars_max + 1];
    long long N;
    scanf("%s", S);
    scanf("%lld", &N);
    int length = strlen(S);
    sort(S, S + length);
    vector<char> s(S, S + length), t;
    for (int i = length - 1; i; i--) {
      int j = N / factorials[i];
      t.push_back(s[j]);
      s.erase(s.begin() + j);
      N %= factorials[i];
    }
    t.push_back(s[0]);
    t.push_back('\0');
    printf("%s\n", &t[0]);
  }
  return 0;
}

UVa 11857 - Driving Range

Accepted date: 2014-08-24
Ranking (as of 2014-08-24): 150 out of 596
Language: C++

/*
  UVa 11857 - Driving Range

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

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

const int n_max = 1000000, m_max = 1000000;
class union_find {
public:
  void init(int n);
  int find(int i) const;
  int do_union(int i, int j);
    // generate the union of the two sets to which i and j belong and 
    // return the representative of the result set
  int nr_sets() const {return s_;}

private:
  int n_; // number of elements
  int s_; // number of sets
  int representatives_[n_max]; // representatives[i] is the representative of 
    // a set to which i belongs
  int ranks_[n_max]; // ranks_[i] is the number of elements in the set 
    // to which i belongs
} vertices;

void union_find::init(int n)
{
  n_ = s_ = n;
  for (int i = 0; i < n_; i++) {
    representatives_[i] = i;
    ranks_[i] = 1;
  }
}

int union_find::find(int i) const
// return the representative of a set to which i belongs
{
  return (representatives_[i] == i) ? i : find(representatives_[i]);
}

int union_find::do_union(int i, int j)
// generate the union of the two sets to which i and j belong and 
// return the representative of the result set
{
  int ri = find(i), rj = find(j);
  if (ri == rj) // already in the same set
    return -1;
  s_--;
  if (ranks_[ri] >= ranks_[rj]) {
    ranks_[ri] += ranks_[rj];
    representatives_[rj] = ri;
    return ri;
  }
  else {
    ranks_[rj] += ranks_[ri];
    representatives_[ri] = rj;
    return rj;
  }
}

struct edge {
  int u_, v_, weight_;
  bool operator<(const edge& e) const {return weight_ < e.weight_;}
} edges[m_max];

int main()
{
  while (true) {
    int n, m;
    scanf("%d %d", &n, &m);
    if (!n && !m)
      break;
    for (int i = 0; i < m; i++)
      scanf("%d %d %d", &edges[i].u_, &edges[i].v_, &edges[i].weight_);
    // apply Kruskal's minimum spanning tree algorithm
    vertices.init(n);
    sort(edges, edges + m); // sort the edges in ascending order of their weights
    int max_cost = -1;
    for (int i = 0; i < m; i++)
      if (vertices.find(edges[i].u_) != vertices.find(edges[i].v_)) {
        vertices.do_union(edges[i].u_, edges[i].v_);
        if (vertices.nr_sets() == 1) {
          max_cost = edges[i].weight_;
          break;
        }
      }
    if (max_cost != -1)
      printf("%d\n", max_cost);
    else
      puts("IMPOSSIBLE");
  }
  return 0;
}

UVa 452 - Project Scheduling

Accepted date: 2014-08-22
Ranking (as of 2014-08-22): 224 out of 681
Language: C++

/*
  UVa 452 - Project Scheduling

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

#include <iostream>
#include <string>
#include <sstream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

const int nr_vertices = 26;
int nr_days[nr_vertices], nr_accumulated_days[nr_vertices],
  in_degrees[nr_vertices];
bool adjacency_matrix[nr_vertices][nr_vertices];

int main()
{
  string line;
  istringstream iss;
  getline(cin, line);
  iss.str(line);
  int nr_cases;
  iss >> nr_cases;
  iss.clear();
  getline(cin, line); // skip a blank line
  while (nr_cases--) {
    memset(adjacency_matrix, 0, sizeof(adjacency_matrix));
    memset(nr_days, 0, sizeof(nr_days));
    while (getline(cin, line) && !line.empty()) {
      iss.str(line);
      char c;
      int d;
      iss >> c >> d;
      int u = c - 'A';
      nr_days[u] = d;
      while (iss >> c)
        adjacency_matrix[c - 'A'][u] = true;
      iss.clear();
    }
    memset(in_degrees, 0, sizeof(in_degrees));
    for (int u = 0; u < nr_vertices; u++)
      for (int v = 0; v < nr_vertices; v++)
        if (adjacency_matrix[u][v])
          in_degrees[v]++;
    memset(nr_accumulated_days, 0, sizeof(nr_accumulated_days));
    queue<int> q;
    for (int u = 0; u < nr_vertices; u++)
      if (nr_days[u] && !in_degrees[u]) {
        nr_accumulated_days[u] = nr_days[u];
        q.push(u);
      }
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int v = 0; v < nr_vertices; v++)
        if (adjacency_matrix[u][v]) {
          nr_accumulated_days[v] = max(nr_accumulated_days[v],
            nr_accumulated_days[u] + nr_days[v]);
#ifdef DEBUG
          cout << static_cast<char>(v + 'A') << ": " <<
            nr_accumulated_days[v] << endl;
#endif
          if (!--in_degrees[v])
            q.push(v);
        }
    }
    int max_nr_accumulated_days = 0;
    for (int u = 0; u < nr_vertices; u++)
      max_nr_accumulated_days = max(max_nr_accumulated_days,
        nr_accumulated_days[u]);
    cout << max_nr_accumulated_days  << endl;
    if (nr_cases)
      cout << endl;
  }
  return 0;
}

UVa 10894 - Save Hridoy

Accepted date: 2014-08-12
Ranking (as of 2014-08-15): 12 out of 570
Language: C++

/*
  UVa 10894 - Save Hridoy

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

#include <cstdio>

const int hbanner_rows = 5, hbanner_columns = 61,
  vbanner_rows = 61, vbanner_columns = 5, N_max = 50;

char hbanner[hbanner_rows][hbanner_columns + 1] = {
  "*****..***..*...*.*****...*...*.*****.*****.***...*****.*...*",
  "*.....*...*.*...*.*.......*...*.*...*...*...*..*..*...*..*.*.",
  "*****.*****.*...*.***.....*****.*****...*...*...*.*...*...*..",
  "....*.*...*..*.*..*.......*...*.*.*.....*...*..*..*...*...*..",
  "*****.*...*...*...*****...*...*.*..**.*****.***...*****...*.."
};

char vbanner[vbanner_rows][vbanner_columns + 1] = {
  "*****",
  "*....",
  "*****",
  "....*",
  "*****",
  ".....",
  ".***.",
  "*...*",
  "*****",
  "*...*",
  "*...*",
  ".....",
  "*...*",
  "*...*",
  "*...*",
  ".*.*.",
  "..*..",
  ".....",
  "*****",
  "*....",
  "***..",
  "*....",
  "*****",
  ".....",
  ".....",
  ".....",
  "*...*",
  "*...*",
  "*****",
  "*...*",
  "*...*",
  ".....",
  "*****",
  "*...*",
  "*****",
  "*.*..",
  "*..**",
  ".....",
  "*****",
  "..*..",
  "..*..",
  "..*..",
  "*****",
  ".....",
  "***..",
  "*..*.",
  "*...*",
  "*..*.",
  "***..",
  ".....",
  "*****",
  "*...*",
  "*...*",
  "*...*",
  "*****",
  ".....",
  "*...*",
  ".*.*.",
  "..*..",
  "..*..",
  "..*.."
};

int main()
{
  char buff[hbanner_columns * N_max + 1];
  while (true) {
    int N;
    scanf("%d", &N);
    if (!N)
      break;
    if (N > 0) {
      for (int si = 0; si < hbanner_rows; si++) {
        int dj = 0;
        for (int sj = 0; sj < hbanner_columns; sj++)
          for (int n = 0; n < N; n++, dj++)
            buff[dj] = hbanner[si][sj];
        buff[dj] = '\0';
        for (int n = 0; n < N; n++)
          printf("%s\n", buff);
      }
    }
    else {
      int L = -N;
      for (int si = 0; si < vbanner_rows; si++) {
        int dj = 0;
        for (int sj = 0; sj < vbanner_columns; sj++)
          for (int n = 0; n < L; n++, dj++)
            buff[dj] = vbanner[si][sj];
        buff[dj] = '\0';
        for (int n = 0; n < L; n++)
          printf("%s\n", buff);
      }
    }
    printf("\n\n");
  }
  return 0;
}

UVa 538 - Balancing Bank Accounts

Accepted date: 2014-08-04
Ranking (as of 2014-08-04): 121 out of 656
Language: C++

/*
  UVa 538 - Balancing Bank Accounts

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

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

struct traveller {
  string name_;
  int account_;

  bool operator<(const traveller& t) const {return account_ < t.account_;}
};

int main()
{
  for (int cn = 1; ; cn++) {
    int n, t;
    cin >> n >> t;
    if (!n && !t)
      break;
    map<string, int> names;
    vector<traveller> travellers(n);
    for (int i = 0; i < n; i++) {
      string s;
      cin >> s;
      travellers[i].name_ = s; travellers[i].account_ = 0;
      names[s] = i;
    }
    while (t--) {
      string s, t;
      int a;
      cin >> s >> t >> a;
      travellers[names[s]].account_ -= a;
      travellers[names[t]].account_ += a;
    }
    sort(travellers.begin(), travellers.end());
    cout << "Case #" << cn << endl;
    for (int i = 0, j = n - 1; i < j && travellers[i].account_; ) {
      int d = travellers[i].account_ + travellers[j].account_;
      cout << travellers[j].name_ << ' ' <<
        travellers[i].name_ << ' ';
      if (d > 0) {
        cout << -travellers[i].account_ << endl;
        i++;
        travellers[j].account_ = d;
      }
      else if (d < 0) {
        cout << travellers[j].account_ << endl;
        travellers[i].account_ = d;
        j--;
      }
      else {
        cout << travellers[j].account_ << endl;
        i++; j--;
      }
    }
    cout << endl;
  }
  return 0;
}

UVa 10637 - Coprimes

Accepted date: 2014-08-04
Ranking (as of 2014-08-04): 384 out of 605
Language: C++

/*
  UVa 10637 - Coprimes

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

#include <cstdio>

const int S_max = 100;

bool coprimes[S_max + 1][S_max + 1];
  // coprimes[i][j] is true if i and j (i <= j) is co-prime

int gcd(int x, int y)
{
  if (x < y)
    return gcd(y, x);
  else
      return y == 0 ? x : gcd(y, x % y);
}

void partition(int S, int t, int ti, int numbers[])
{
  if (S) {
    for (int i = (!ti || numbers[ti - 1] == 1) ? 1 : numbers[ti - 1] + 1;
      i <= S; i++) {
      int j;
      for (j = 0; j < ti; j++)
        if (!coprimes[numbers[j]][i])
          break;
      if (j == ti) {
        numbers[ti] = i;
        partition(S - i, t, ti + 1, numbers);
      }
    }
  }
  else if (ti == t) {
    for (int i = 0; i < t; i++)
      printf("%d%c", numbers[i], ((i < t - 1) ? ' ' : '\n'));
  }
}

int main()
{
  for (int i = 1; i <= S_max; i++)
    coprimes[1][i] = true;
  for (int i = 2; i < S_max; i++)
    for (int j = i + 1; j <= S_max; j++)
      coprimes[i][j] = gcd(i, j) == 1;
  int N;
  scanf("%d", &N);
  for (int cn = 1; cn <= N; cn++) {
    int S, t;
    scanf("%d %d", &S, &t);
    printf("Case %d:\n", cn);
    int numbers[S_max];
    partition(S, t, 0, numbers);
  }
  return 0;
}

UVa 812 - Trade on Verweggistan

Accepted date: 2014-08-02
Ranking (as of 2014-08-02): 105 out of 629
Language: C++

/*
  UVa 812 - Trade on Verweggistan

  To build using Visucal Studio 2012:
    cl -EHsc UVa_812_Trade_on_Verweggistan.cpp
*/

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

const int w_max = 50, b_max = 20;
int boxes[w_max], max_profits[w_max];
int profits[w_max][b_max];
  // profits[i][j] is the accumulated profits up to j-th pile of i-th workyard
bool pruls[w_max + 1][w_max * b_max + 1];
  // pruls[][i] is true if i pruls have to be bought to get the max. profits

int main()
{
  const int price = 10;
  for (int wn = 1; ; wn++) {
    int w;
    scanf("%d", &w);
    if (!w)
      break;
    if (wn > 1)
      putchar('\n');
    int max_p = 0;
    for (int i = 0; i < w; i++) {
      scanf("%d", &boxes[i]);
      max_profits[i] = -1;
      for (int j = 0, k = 0; j < boxes[i]; j++) {
        int p;
        scanf("%d", &p);
        p = price - p;
        k += p;
        profits[i][j] = k;
        max_profits[i] = max(max_profits[i], k);
      }
#ifdef DEBUG
      printf("%d:", max_profits[i]);
      for (int j = 0; j < boxes[i]; j++)
        printf(" %d", profits[i][j]);
      putchar('\n');
#endif
      if (max_profits[i] >= 0)
        max_p += max_profits[i];
    }
    pruls[0][0] = true;
    int pi = 0, sb = 0;
    for (int i = 0; i < w; i++)
      if (max_profits[i] >= 0) {
        pi++;
        for (int k = 0; k <= sb + boxes[i]; k++)
          pruls[pi][k] = false;
        if (!max_profits[i])
          for (int k = 0; k <= sb; k++)
            if (pruls[pi - 1][k])
              pruls[pi][k] = true;
        for (int j = 0; j < boxes[i]; j++)
          if (profits[i][j] == max_profits[i])
            for (int k = 0; k <= sb; k++)
                if (pruls[pi - 1][k])
                  pruls[pi][k + j + 1] = true;
        sb += boxes[i];
#ifdef DEBUG
        for (int k = 0; k <= sb; k++)
          if (pruls[pi][k])
            printf("%d ", k);
        putchar('\n');
#endif
      }
    printf("Workyards %d\n", wn);
    printf("Maximum profit is %d.\n", max_p);
    printf("Number of pruls to buy:");
    for (int i = 0, j = 0; i <= sb && j < 10; i++)
      if (pruls[pi][i]) {
        printf(" %d", i);
        j++;
      }
    putchar('\n');
  }
  return 0;
}

UVa 10330 - Power Transmission

Accepted date: 2014-08-01
Ranking (as of 2014-08-02): 606 out of 1470
Language: C++

/*
  UVa 10330 - Power Transmission

  To build using Visucal Studio 2012:
    cl -EHsc UVa_10330_Power_Transmission.cpp
*/

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

struct edge {
  int v; // neighboring vertex
  int capacity; // capacity of edge
  int flow; // flow through edge
  int residual; // residual capacity of edge

  edge(int _v, int _capacity, int _residual)
    : v(_v), capacity(_capacity), flow(0), residual(_residual) {}
};

struct vertex_state {
  bool discovered;
  int parent;

  vertex_state() : discovered(false), parent(-1) {}
};

void bfs(const vector< vector<edge> >& graph,
  int start, vector<vertex_state>& states)
{
  queue<int> q;
  states[start].discovered = true;
  q.push(start);
  while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int i = 0; i < graph[u].size(); i++) {
      const edge& e = graph[u][i];
      if (e.residual > 0 && !states[e.v].discovered) {
        states[e.v].discovered = true;
        states[e.v].parent = u;
        q.push(e.v);
      }
    }
  }
}

edge& find_edge(vector< vector<edge> >& graph, int u, int v)
{
  int i;
  for (i = 0; i < graph[u].size(); i++)
    if (graph[u][i].v == v)
      break;
  return graph[u][i];
}

int path_volume(vector< vector<edge> >& graph,
  int start, int end, const vector<vertex_state>& states)
{
  if (states[end].parent == -1)
    return 0;
  edge& e = find_edge(graph, states[end].parent, end);
  if (start == states[end].parent)
    return e.residual;
  else
    return min(path_volume(graph, start, states[end].parent, states),
      e.residual);
}

void augment_path(vector< vector<edge> >& graph,
  int start, int end, const vector<vertex_state>& states, int volume)
{
  if (start == end)
    return;
  edge& e = find_edge(graph, states[end].parent, end);
  if (e.flow < e.capacity)
    e.flow += volume;
  if (e.residual)
    e.residual -= volume;
  edge& r= find_edge(graph, end, states[end].parent);
  if (r.flow)
    r.flow -= volume;
  if (r.residual < r.capacity)
    r.residual += volume;
  augment_path(graph, start, states[end].parent, states, volume);
}

void netflow(vector< vector<edge> >& graph, int source, int sink)
{
  while (true) {
    vector<vertex_state> states(graph.size());
    bfs(graph, source, states);
    int volume = path_volume(graph, source, sink, states);
      // calculate the volume of augmenting path
    if (volume > 0)
      augment_path(graph, source, sink, states, volume);
    else
      break;
  }
}

int total_flow(const vector< vector<edge> >& graph, int source)
{
  int flow = 0;
  const vector<edge>& edges = graph[source];
  for (int i = 0, e = edges.size(); i < e; i++)
    flow += edges[i].flow;
  return flow;
}

int main()
{
  int n;
  while (cin >> n) {
    int nr_vertices = 2 * n + 2;
    vector< vector<edge> > graph(nr_vertices);
    // indices are:
    // 0 - (2 * n - 1): regulator vertices, 2 * n: source vertex, 
    // 2 * n + 1: sink vertex
    // Note that each regulators are treated as a pair of vertices.
    int source = 2 * n, sink = 2 * n + 1;
    vector<int> rcs(n); // regulator capacities
    for (int i = 0; i < n; i++) {
      // append the edges between each pair of regulator vertices
      cin >> rcs[i];
      graph[2 * i].push_back(edge(2 * i + 1, rcs[i], rcs[i]));
      graph[2 * i + 1].push_back(edge(2 * i, rcs[i], 0));
    }
    int m;
    cin >> m;
    while (m--) { // append the edges between regulators
      int i, j, c;
      cin >> i >> j >> c;
      i--; j--;
      graph[2 * i + 1].push_back(edge(2 * j, c, c));
      graph[2 * j].push_back(edge(2 * i + 1, c , 0));
    }
    int b, d;
    cin >> b >> d;
    while (b--) { // append the edges from the source to regulators
      int i;
      cin >> i;
      i--;
      graph[source].push_back(edge(2 * i, rcs[i], rcs[i]));
      graph[2 * i].push_back(edge(source, rcs[i], 0));
    }
    while (d--) { // append the edges from regulators to the sink
      int i;
      cin >> i;
      i--;
      graph[2 * i + 1].push_back(edge(sink, rcs[i], rcs[i]));
      graph[sink].push_back(edge(2 * i + 1, rcs[i], 0));
    }
    netflow(graph, source, sink);
    cout << total_flow(graph, source) << endl;
  }
  return 0;
}