UVa 11205 - The broken pedometer

Accepted date: 2015-12-26
Run Time: 0.013
Ranking (as of 2015-12-17): 126 out of 804
Language: C++

/*
  UVa 11205 - The broken pedometer

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

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

bool are_symbols_distinguishable(int mask, int mask_max, int nr_symbols,
  const vector<int>& symbols)
{
  vector<bool> masked_symbols(mask_max, false);
  for (int i = 0; i < nr_symbols; i++) {
    int j = symbols[i] & mask;
    if (masked_symbols[j])
      return false;
    masked_symbols[j] = true;
  }
  return true;
}

int count_leds(int i, int nr_leds)
{
  int count = 0;
  for (int j = 0; j < nr_leds; j++, i >>= 1)
    if (i & 1)
      count++;
  return count;
}

int main()
{
  int nr_problems;
  cin >> nr_problems;
  while (nr_problems--) {
    int nr_leds, nr_symbols;
    cin >> nr_leds >> nr_symbols;
    vector<int> symbols(nr_symbols);
    for (int i = 0; i < nr_symbols; i++) {
      int s = 0;
      for (int j = 0; j < nr_leds; j++) {
        char c;
        cin >> c;
        s <<= 1;
        if (c == '1')
          s |= 1;
      }
      symbols[i] = s;
    }
    int nr = nr_leds;
    if (!nr_symbols)
      nr = 0;
    else if (nr_symbols == 1)
      nr = 0;
    else {
      int min_nr_leds =
        static_cast<int>(ceil(log10(static_cast<double>(nr_symbols)) / log10(2.0)));
        // min. number of LEDs to distinguish the symbols
      for (int i = 1,
        i_max = static_cast<int>(pow(2.0, static_cast<double>(nr_leds)));
        i < i_max; i++)
        if (are_symbols_distinguishable(~i, i_max, nr_symbols, symbols)) {
          nr = min(nr, nr_leds - count_leds(i, nr_leds));
          if (nr == min_nr_leds)
            break;
        }
    }
    cout << nr << endl;
  }
  return 0;
}

UVa 11353 - A Different Kind of Sorting

Accepted date: 2015-12-17
Run Time: 0.259
Ranking (as of 2015-12-17): 38 out of 447
Language: C++

/*
  UVa 11353 - A Different Kind of Sorting

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11353_A_Different_Kind_of_Sorting.cpp

  See also 10856 - Recover Factorial.
*/

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

const int n_max = 2000000;

struct number {
  int n_;
  int nr_pfs_; // nmber of prime factors of n_

  bool operator<(const number& n) const {
    if (nr_pfs_ != n.nr_pfs_)
      return nr_pfs_ < n.nr_pfs_;
    else
      return n_ < n.n_;
  }
} numbers[n_max + 1];

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  for (int i = 1; i <= n_max; i++)
    numbers[i].n_ = i;
  numbers[1].nr_pfs_ = numbers[2].nr_pfs_ = 1;
  for (long long i = 2; i * 2 <= n_max; i++)
    numbers[i * 2].nr_pfs_ = numbers[i].nr_pfs_ + 1;
  for (long long i = 3; i <= n_max; i += 2) {
    if (!numbers[i].nr_pfs_)
      numbers[i].nr_pfs_ = 1;
    for (long long j = 2; i * j <= n_max; j++)
      numbers[i * j].nr_pfs_ = numbers[i].nr_pfs_ + numbers[j].nr_pfs_;
#ifdef DEBUG
    printf("%d: %d\n", i, numbers[i].nr_pfs_);
#endif
  }
  sort(numbers + 1, numbers + n_max + 1);
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  for (int cn = 1; ; cn++) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    printf("Case %d: %d\n", cn, numbers[n].n_);
  }
  return 0;
}

UVa 10541 - Stripe

Accepted date: 2015-12-14
Run Time: 0.122
Ranking (as of 2015-12-14): 420 out of 710
Language: JAVA

// UVa 10541 - Stripe

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

class Main {
  static final int nMax = 200, kMax = 100;
  static int nrs[] = new int[kMax + 1];
  static BigInteger nrRectangles[][] = new BigInteger[kMax + 1][nMax + 1];
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    while (T-- > 0) {
      int N = sc.nextInt(), K = sc.nextInt();
      for (int i = 1; i <= K; i++)
        nrs[i] = sc.nextInt();
      for (int n = 0; n <= N; n++)
        nrRectangles[0][n] = BigInteger.ONE;
      for (int k = 1; k <= K; k++)
        for (int n = 0; n <= N; n++)
          nrRectangles[k][n] = BigInteger.ZERO;
      for (int k = 1, s = 0; k <= K; k++) {
        for (int n = s + nrs[k]; n <= N; n++) {
          if (k > 1)
            nrRectangles[k][n] =
              nrRectangles[k][n - 1].add(nrRectangles[k - 1][n - nrs[k] - 1]);
          else
            nrRectangles[k][n] =
              nrRectangles[k][n - 1].add(nrRectangles[k - 1][n - nrs[k]]);
        }
        s += nrs[k] + 1;
      }
      System.out.println(nrRectangles[K][N]);
    }
  }
}

UVa 10655 - Contemplation! Algebra

Accepted date: 2015-12-11
Run Time: 0.000
Ranking (as of 2015-12-14): 130 out of 467
Language: C++

/*
  UVa 10655 - Contemplation! Algebra

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

#include <cstdio>

/*
  f(n) = a^n + b^n, then:
  f(0) = 1
  f(1) = a + b
  f(n) = (a + b) * f(n - 1) - a * b * f(n - 2) (n >= 2)
*/

long long power(long long b, int e)
{
  if (e == 0)
    return 1;
  long long p = power(b, e / 2);
  p *= p;
  if (e % 2)
    p *= b;
  return p;
}

int main()
{
  while (true) {
    int p, q, n;
    if (scanf("%d %d %d", &p, &q, &n) == 2)
      break;
    long long v0 = 2, v1 = p, v;
    if (n == 0)
      v = v0;
    else if (n == 1)
      v = v1;
    else {
      if (p == 0 && q == 0)
        v = 0;
      else if (p == 0) { // f(n) = - a * b * f(n - 2)
        if (n % 2)
          v = v1 * power(-q, n / 2);
        else
          v = v0 * power(-q, n / 2);
      }
      else if (q == 0) // f(n) = (a + b) * f(n - 1)
        v = v1 * power(p, n - 1);
      else if (p == 2 && q == 1) // f(n) = f(0)
        v = v0;
      else {
        for (int i = 2; i <= n; i++) {
          v = p * v1 - q * v0;
#ifdef DEBUG
          printf("%lld %lld %lld\n", v, v1, v0);
#endif
          v0 = v1, v1 = v;
        }
      }
    }
    printf("%lld\n", v);
  }
  return 0;
}

UVa 815 - Flooded!

Accepted date: 2015-12-07
Ranking (as of 2015-12-07): 34 out of 831
Language: C++

/*
  UVa 815 - Flooded!

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

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

int main()
{
  const int n_max = 30, m_max = 30, nr_elevations_max = n_max * m_max;
  const double epsilon = numeric_limits<double>::epsilon(),
    square_area = 10.0 * 10.0;
  for (int r = 1; ; r++) {
    int m, n;
    scanf("%d %d", &m, &n);
    if (!m)
      break;
    int i, nr_elevations = m * n, elevations[nr_elevations_max];
    double water;
    for (i = 0; i < nr_elevations; i++)
      scanf("%d", &elevations[i]);
    scanf("%lf", &water);
    printf("Region %d\n", r);
    sort(elevations, elevations + nr_elevations);
    double height = elevations[0];
    if (water) {
      double area = square_area;
      for (i = 0; i < nr_elevations - 1; i++, area += square_area) {
        double h = elevations[i + 1] - elevations[i], v = area * h;
        if (v - water >= epsilon) { // v >= water
          h = water / area;
          height += h;
          water = 0.0;
          break;
        }
        else {
          height = elevations[i + 1];
          water -= v;
        }
#ifdef DEBUG
        printf("%.2lf %.2lf\n", height, water);
#endif
      }
      if (water > epsilon)
        height += water / area;
    }
    else
      i = -1;
    printf("Water level is %.2lf meters.\n", height);
    printf("%.2lf percent of the region is under water.\n\n",
      static_cast<double>(i + 1) * 100.0 / nr_elevations);
  }
  return 0;
}

UVa 816 - Abbott's Revenge

Accepted date: 2015-12-05
Ranking (as of 2015-12-05): 39 out of 565
Language: C++

/*
  UVa 816 - Abbott's Revenge

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

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

enum {north, south, east, west};
enum {left, forward_, right};
const int nr_rows = 9, nr_columns = 9,
  nr_nsew = west - north + 1, nr_lfr = right - left + 1,
  nr_name_chars_max = 20, nr_chars_max = 8;

bool exits[nr_rows + 1][nr_columns + 1][nr_nsew][nr_lfr];
  // path[r][c][f][t] is true if the path to (r, c) from f to can be exited
bool visited[nr_rows + 1][nr_columns + 1][nr_nsew][nr_lfr];

int symbol_values[] = {
  0, 0, 0, 0, east, forward_, 0, 0, 0, 0, 0, left, 0, north, 
  0, 0, 0, right, south, 0, 0, 0, west, 0, 0, 0
};

struct path {
  int r_, c_;
  vector<int> froms_; // vector of north, south, east or west

  path() {}
  path(const path& p) : r_(p.r_), c_(p.c_), froms_(p.froms_) {}
  path(int r, int c, const vector<int>& froms, int f)
    : r_(r), c_(c), froms_(froms) {froms_.push_back(f);}
};

const int next_dirs[nr_nsew][nr_lfr] = {
  // dirs[f][t] is the next direction from f to t
  {west, north, east},
  {east, south, west},
  {north, east, south},
  {south, west, north}
};

void next_path(int from, int &r, int& c)
{
  switch (from) {
  case north:
    r--; break;
  case south:
    r++; break;
  case east:
    c++; break;
  case west:
    c--; break;
  }
}

void print_paths(int sr, int sc, const vector<int>& froms)
{
  int r = sr, c = sc;
  size_t i, j;
  for (i = 0, j = froms.size(); i < j; i++) {
    if (!(i % 10))
      printf("  ");
    printf("(%d,%d)%c", r, c, (((i % 10) == 9) ? '\n' : ' '));
    next_path(froms[i], r, c);
  }
  if (!(i % 10))
    printf("  ");
  printf("(%d,%d)\n", r, c);
}

int main()
{
  while (true) {
    char name[nr_name_chars_max + 1];
    scanf("%s", name);
    if (!strcmp(name, "END"))
      break;
    memset(exits, 0, sizeof(exits));
    memset(visited, 0, sizeof(visited));
    int sr, sc, gr, gc, sd;
    char s[nr_chars_max];
    scanf("%d %d %s %d %d", &sr, &sc, s, &gr, &gc);
    sd = symbol_values[s[0] - 'A'];
    while (true) {
      int r, c;
      scanf("%d", &r);
      if (!r)
        break;
      scanf("%d", &c);
      while (true) {
        scanf("%s", s);
        if (s[0] == '*')
          break;
        int f = symbol_values[s[0] - 'A'];
        for (int i = 1; s[i]; i++)
          exits[r][c][f][symbol_values[s[i] - 'A']] = true;
      }
    }
    printf("%s\n", name);
    bool solution = false;
    queue<path> q;
    visited[sr][sc][sd][forward_] = true;
    q.push(path(sr, sc, vector<int>(), sd));
    while (!q.empty()) {
      path u = q.front(); q.pop();
      int from = u.froms_.back(), r = u.r_, c = u.c_;
#ifdef DEBUG
      printf("%d %d %d %d\n", r, c, u.froms_.back(), u.forms_.size());
#endif
      next_path(from, r, c);
      if (r == gr && c == gc) {
        solution = true;
        print_paths(sr, sc, u.froms_);
        break;
      }
      if (r >= 1 && r <= nr_rows && c >= 1 && c <= nr_columns)
        for (int to = left; to <= right; to++)
          if (exits[r][c][from][to] && !visited[r][c][from][to]) {
            visited[r][c][from][to] = true;
            q.push(path(r, c, u.froms_, next_dirs[from][to]));
          }
    }
    if (!solution)
      puts("  No Solution Possible");
  }
  return 0;
}