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;
}

UVa 471 - Magic Numbers

Accepted date: 2014-07-26
Ranking (as of 2014-07-26): 237 out of 1017
Language: C++

/*
  UVa 471 - Magic Numbers

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

#include <iostream>
using namespace std;
 
bool is_digits_repeated(long long n)
{
  unsigned int digits = 0; // i-th bit is '1' if digit of i (0 - 9) exists in n
  do {
    int d = 1 << static_cast<int>(n % 10);
    if (digits & d)
      return true;
    n /= 10;
    digits |= d;
  } while (n);
  return false;
}

int main()
{
  const long long s1_max = 9876543210LL;
  int t;
  cin >> t;
  while (t--) {
    long long N;
    cin >> N;
    for (long long s2 = 1, s2_max = s1_max / N; s2 <= s2_max; s2++)
      if (!is_digits_repeated(s2)) {
        long long s1 = s2 * N;
        if (!is_digits_repeated(s1))
          cout << s1 << " / " << s2 << " = " << N << endl;
      }
    if (t)
      cout << endl;
  }
  return 0;
}

UVa 703 - Triple Ties: The Organizer's Nightmare

Accepted date: 2014-07-24
Ranking (as of 2014-07-24): 260 out of 696
Language: C++

/*
  UVa 703 - Triple Ties: The Organizer's Nightmare

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

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

const int n_max = 100;
int tournaments[n_max + 1][n_max + 1];

struct triple_tie {
  int i_, j_, k_;

  triple_tie(int i, int j, int k) : i_(i), j_(j), k_(k) {}
  bool operator<(const triple_tie& tt) const {
    if (i_ != tt.i_)
      return i_ < tt.i_;
    else if (j_ != tt.j_)
      return j_ < tt.j_;
    else
      return k_ < tt.k_;
  }
};

int get_result(int i, int j)
{
  if (tournaments[i][j] /* > tournaments[j][i] */)
    return 1; // i beats j
  else if (/* tournaments[i][j] < */ tournaments[j][i])
    return -1; // j beats i
  else
    return 0; // draw

}

int main()
{
  int n;
  while (cin >> n) {
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        cin >> tournaments[i][j];

    vector<triple_tie> triple_ties;
    for (int i = 1; i <= n - 2; i++)
      for (int j = i + 1; j <= n - 1; j++)
        for (int k = j + 1; k <= n; k++) {
          int rij = get_result(i, j), rjk = get_result(j, k),
            rki = get_result(k, i);
          if (rij == 0 && rjk == 0 && rki == 0 || // draws
            rij == 1 && rjk == 1 && rki == 1)
            // i beats j, j beats k, k beats i
            triple_ties.push_back(triple_tie(i, j, k));
          else if (get_result(k, j) == 1 && get_result(j, i) == 1 &&
            get_result(i, k) == 1)
            // k beats j, j beats i, i beats k
            triple_ties.push_back(triple_tie(k, j, i));
        }
    sort(triple_ties.begin(), triple_ties.end());
    cout << triple_ties.size() << endl;
    for (vector<triple_tie>::const_iterator ti = triple_ties.begin(),
      te = triple_ties.end(); ti != te; ++ti)
      cout << ti->i_ << ' ' << ti->j_ << ' ' << ti->k_ << endl;
  }
  return 0;
}

UVa 11565 - Simple Equations

Accepted date: 2014-07-20
Ranking (as of 2014-07-20): 199 out of 757
Language: C++

/*
  UVa 11565 - Simple Equations

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

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

const int ABC_max = 10000;
int nr_factors, factors[ABC_max];

bool satisfy_equation(int A, int B, int C, int x, int y, int& z)
{
  int k = x * y;
  if (!(B % k)) {
    z = B / k;
    if (x != z && y != z && x + y + z == A && x * x + y * y + z * z == C)
      return true;
  }
  return false;
}

bool solve_equation(int A, int B, int C, int& x, int& y, int& z)
{
  int i, j;
  for (i = nr_factors - 1; i > 0; i--) {
    x = -factors[i];
    for (j = i - 1; j >= 0; j--) {
      y = -factors[j];
      if (satisfy_equation(A, B, C, x, y, z))
        return true;
    }
    for (j = 0; j < i; j++) {
      y = factors[j];
      if (satisfy_equation(A, B, C, x, y, z))
        return true;
    }
  }
  for (int i = 0; i < nr_factors - 1; i++) {
    x = factors[i];
    for (int j = nr_factors - 1; j > i; j--) {
      y = -factors[j];
      if (satisfy_equation(A, B, C, x, y, z))
        return true;
    }
    for (int j = i + 1; j < nr_factors; j++) {
      y = factors[j];
      if (satisfy_equation(A, B, C, x, y, z))
        return true;
    }
  }

  return false;
}

int main()
{
  int N;
  scanf("%d", &N);
  while (N--) {
    int A, B, C;
    scanf("%d %d %d", &A, &B, &C);
    nr_factors = 0;
    for (int i = 1, j = static_cast<int>(sqrt(static_cast<double>(B)));
      i <= j; i++)
      if (!(B % i)) {
        factors[nr_factors++] = i;
        if (i < B / i)
          factors[nr_factors++] = B / i;
      }
    sort(factors, factors + nr_factors);
    int x, y, z;
    if (solve_equation(A, B, C, x, y, z))
      printf("%d %d %d\n", x, y, z);
    else
      puts("No solution.");
  }
  return 0;
}