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

UVa 12791 - Lap

Accepted date: 2015-11-24
Ranking (as of 2015-11-24): 56 out of 454
Language: C++

/*
  UVa 12791 - Lap

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

#include <cstdio>

int main()
{
  int X, Y;
  while (scanf("%d %d", &X, &Y) != EOF) {
    int d = Y - X;
    int lap = Y / d;
    if (Y % d)
      lap++;
    printf("%d\n", lap);
  }
  return 0;
}

UVa 181 - Hearts

Accepted date: 2015-11-21
Ranking (as of 2015-11-21): 142 out of 449
Language: C++

/*
  UVa 181 - Hearts

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

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

enum {s_Clubs, s_Diamonds, s_Hearts, s_Spades};
enum {d_2 = 2, d_3, d_4, d_5, d_6, d_7, d_8, d_9, d_10,
  d_Jack, d_Queen, d_King, d_Ace};

const int nr_suits = s_Spades - s_Clubs + 1, nr_denominations = d_Ace - d_2 + 1,
  nr_cards = nr_suits * nr_denominations;
const int nr_players = 5, nr_tricks = 10;
struct card {
  int suit_, denomination_;
} cards[nr_cards], player_cards[nr_players];

const int symbols[] = {
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, d_2, d_3, d_4, d_5, d_6, d_7, d_8, d_9, 0, 0, 0, 0, 0, 0,
  0, d_Ace, 0, s_Clubs, s_Diamonds, 0, 0, 0, s_Hearts, 0, d_Jack, d_King, 0, 0, 0, 0,
  0, d_Queen, 0, s_Spades, d_10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

struct game_suit {
  int nr_denominations_;
  int denominations_[nr_denominations];
} game[nr_players][nr_suits];

int hearts[nr_players];

int get_trump()
{
  card& ci = cards[nr_players * nr_tricks];
  card& cj = cards[nr_players * nr_tricks + 1];
  if (ci.denomination_ < cj.denomination_)
    return cj.suit_;
  else if (ci.denomination_ > cj.denomination_)
    return ci.suit_;
  else
    return max(ci.suit_, cj.suit_);
}

void get_leader_card(int pi, int trump)
{
  int i = -1;
  for (int j = 0; j < nr_suits; j++) {
    game_suit& gsj = game[pi][j];
    if (!gsj.nr_denominations_)
      continue;
    if (i == -1)
      i = j;
    else {
      game_suit& gsi = game[pi][i];
      int di = gsi.denominations_[gsi.nr_denominations_ - 1],
        dj = gsj.denominations_[gsj.nr_denominations_ - 1];
      if (di < dj)
        i = j;
      else if (di == dj && i != trump)
        i = j;
    }
  }
  game_suit& gs = game[pi][i];
  player_cards[pi].suit_ = i,
    player_cards[pi].denomination_ = gs.denominations_[--gs.nr_denominations_];
}

void get_follower_card(int pi, int suit, int trump)
{
  int i = -1;
  if (game[pi][suit].nr_denominations_)
    i = suit;
  else if (game[pi][trump].nr_denominations_)
    i = trump;
  else {
    for (int j = 0; j < nr_suits; j++)
      if (j != suit && j != trump && game[pi][j].nr_denominations_) {
        if (i == -1)
          i = j;
        else if (game[pi][i].denominations_[game[pi][i].nr_denominations_ - 1] <=
          game[pi][j].denominations_[game[pi][j].nr_denominations_ - 1])
          i = j;
      }
  }
  game_suit& gs = game[pi][i];
  player_cards[pi].suit_ = i,
    player_cards[pi].denomination_ = gs.denominations_[--gs.nr_denominations_];
}

int get_winner(int suit, int trump)
{
  int i = -1, ti = -1;
  for (int j = 0; j < nr_players; j++) {
    if (player_cards[j].suit_ == trump) {
      if (ti == -1)
        ti = j;
      else if (player_cards[ti].denomination_ < player_cards[j].denomination_)
        ti = j;
    }
    else if (player_cards[j].suit_ == suit) {
      if (i == -1)
        i = j;
      else if (player_cards[i].denomination_ < player_cards[j].denomination_)
        i = j;
    }
  }
  return (ti != -1) ? ti : i;
}

void print_hearts()
{
  printf("%3d", hearts[nr_players - 1]);
  for (int i = 0; i < nr_players - 1; i++)
    printf("%3d", hearts[i]);
  putchar('\n');
}

int main()
{
  while (true) {
    char s[3];
    scanf("%s", s);
    if (s[0] == '#')
      break;
    cards[0].suit_ = symbols[s[1]], cards[0].denomination_ = symbols[s[0]];
    for (int i = 1; i < nr_cards; i++) {
      scanf("%s", s);
      cards[i].suit_ = symbols[s[1]], cards[i].denomination_ = symbols[s[0]];
    }
    int trump = get_trump();
#ifdef DEBUG
    printf("trump: %d\n", trump);
#endif
    for (int i = 0; i < nr_players; i++) {
      hearts[i] = 0;
      for (int j = 0; j < nr_suits; j++)
        game[i][j].nr_denominations_ = 0;
    }
    for (int i = 0; i < nr_tricks; i++) // deliver the cards to the players
      for (int j = 0; j < nr_players; j++) {
        const card& c = cards[i * nr_players + j];
        game_suit& gs = game[j][c.suit_];
        gs.denominations_[gs.nr_denominations_++] = c.denomination_;
      }
    for (int i = 0; i < nr_players; i++)
      for (int j = 0; j < nr_suits; j++) {
#ifdef DEBUG
        printf("player: %d suit: %d demoninations: ", i, j);
#endif
        game_suit& gs = game[i][j];
        sort(gs.denominations_, gs.denominations_ + gs.nr_denominations_);
#ifdef DEBUG
        if (gs.nr_denominations_)
          for (int k = 0; k < gs.nr_denominations_; k++)
            printf("%d%c", gs.denominations_[k],
              ((k < gs.nr_denominations_ - 1) ? ' ' : '\n'));
        else
          putchar('\n');
#endif
      }
    int leader = 0;
    for (int i = 0; i < nr_tricks; i++) {
      get_leader_card(leader, trump);
#ifdef DEBUG
      printf("trick %d\n  player: %d suit: %d demonination: %d\n", i + 1,
        leader, player_cards[leader].suit_, player_cards[leader].denomination_);
#endif
      int suit = player_cards[leader].suit_;
      for (int j = 0; j < nr_players; j++)
        if (j != leader) {
          get_follower_card(j, suit, trump);
#ifdef DEBUG
          printf("  player: %d suit: %d demonination: %d\n",
            j, player_cards[j].suit_, player_cards[j].denomination_);
#endif
        }
      int winner = get_winner(suit, trump);
      for (int j = 0; j < nr_players; j++)
        if (player_cards[j].suit_ == s_Hearts)
          hearts[winner] += player_cards[j].denomination_;
      leader = winner;
#ifdef DEBUG
    print_hearts();
#endif
    }
    print_hearts();
  }
  return 0;
}

UVa 10586 - Polynomial Remains

Accepted date: 2015-11-19
Ranking (as of 2015-11-19): 8 out of 553
Language: C++

/*
  UVa 10586 - Polynomial Remains

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

#include <cstdio>

const int n_max = 10000;
int coefficients[n_max + 1];

int main()
{
  while (true) {
    int n, k;
    scanf("%d %d", &n, &k);
    if (n == -1)
      break;
    for (int i = 0; i <= n; i++)
      scanf("%d", &coefficients[i]);
    for (int i = n - k, j = n; i >= 0; i--, j--)
      if (coefficients[j]) {
        coefficients[i] -= coefficients[j];
        coefficients[j] = 0;
      }
    int i;
    for (i = k - 1; i >= 0; i--)
      if (coefficients[i])
        break;
    if (i >= 0) {
      for (int j = 0; j <= i; j++) {
        printf("%d%c", coefficients[j], ((j < i) ? ' ' : '\n'));
        coefficients[j] = 0;
      }
    }
    else
      puts("0");
  }
  return 0;
}

UVa 418 - Molecules

Accepted date: 2015-11-17
Ranking (as of 2015-11-17): 2 out of 493
Language: C++

/*
  UVa 418 - Molecules

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

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

const int nr_permutations = 24, nr_chains = 4, nr_elements = 12;

char molecules[nr_chains][nr_elements + 1];

const int orders[nr_permutations][nr_chains] = {
  {0, 1, 2, 3}, {0, 1, 3, 2}, {0, 2, 1, 3}, {0, 2, 3, 1},
  {0, 3, 1, 2}, {0, 3, 2, 1}, {1, 0, 2, 3}, {1, 0, 3, 2},
  {1, 2, 0, 3}, {1, 2, 3, 0}, {1, 3, 0, 2}, {1, 3, 2, 0},
  {2, 0, 1, 3}, {2, 0, 3, 1}, {2, 1, 0, 3}, {2, 1, 3, 0},
  {2, 3, 0, 1}, {2, 3, 1, 0}, {3, 0, 1, 2}, {3, 0, 2, 1},
  {3, 1, 0, 2}, {3, 1, 2, 0}, {3, 2, 0, 1}, {3, 2, 1, 0}
};

int main()
{
  while (true) {
    scanf("%s", molecules[0]);
    if (molecules[0][0] == 'Q')
      break;
    for (int i = 1; i < nr_chains; i++)
      scanf("%s", molecules[i]);
    int area = 0;
    for (int p = 0; p < nr_permutations; p++) {
      const char *vertical_left = molecules[orders[p][0]],
        *horizontal_up = molecules[orders[p][1]],
        *vertical_right = molecules[orders[p][2]],
        *horizontal_down = molecules[orders[p][3]];
      for (int i = 1; i < nr_elements - 1; i++)
        for (int j = 1; j < nr_elements - 1; j++) {
          if (vertical_left[i] != horizontal_up[j])
            continue;
          for (int jj = j + 2; jj < nr_elements - 1; jj++)
            for (int k = 1; k < nr_elements - 1; k++) {
              if (horizontal_up[jj] != vertical_right[k])
                continue;
              for (int ii = i + 2; ii < nr_elements - 1; ii++)
                for (int l = 1; l < nr_elements - 1; l++) {
                  if (vertical_left[ii] != horizontal_down[l])
                    continue;
                  int kk = k + ii - i, ll = l + jj - j;
                  if (kk > 0 && kk < nr_elements - 1 &&
                    ll > 0 && ll < nr_elements - 1 &&
                    vertical_right[kk] == horizontal_down[ll]) {
                    area = max(area, (ii - i - 1) * (jj - j - 1));
                  }
                }
            }
        }
    }
    printf("%d\n", area);
  }
  return 0;
}

UVa 150 - Double Time

Accepted date: 2015-11-11
Ranking (as of 2015-11-11): 2 out of 452
Language: C++

/*
  UVa 150 - Double Time

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

#include <cstdio>
#include <cstring>

const int nr_chars_max = 15, nr_days_of_week = 7, nr_months = 12;

const char* day_names[nr_days_of_week] = {
  "Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"
};

const char* month_names[nr_months] = {
  "January", "February", "March", "April", "May", "June",
  "July", "August", "September", "October", "November", "December"
};

int nr_days[2][nr_months] = {
  {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
  {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} // leap year
};

int nr_days_of_year[2][nr_months] = {
  {31, 59, 90,120,151,181,212,243,273,304,334,365},
  {31, 60, 91,121,152,182,213,244,274,305,335,366} // leap year
};

const int start_year = 1582, start_day_of_week = 5 /* Friday */,
  julian_calendar_start_days = 273 + 5 /* 5 October */,
  gregorian_calendar_start_days = 273 + 15 /* 15 October */;

int get_day_of_week(const char* day)
{
  for (int i = 0; i < nr_days_of_week; i++)
    if (!strcmp(day, day_names[i]))
      return i;
  return -1;
}

int get_month(const char* month)
{
  for (int i = 0; i < nr_months; i++)
    if (!strcmp(month, month_names[i]))
      return i;
  return -1;
}

bool julian_calendar_leap_year(int year)
{
  return !(year % 4);
}

int julian_calendar_number_of_leap_years(int syear, int eyear)
{
  // number of leap years between [syear, eyear)
  syear--; eyear--;
  return eyear / 4 - syear / 4;
}

int julian_calendar_number_of_days(int year, int month, int day)
{
  int nr_days = (year - start_year) * 365 +
    julian_calendar_number_of_leap_years(start_year, year) -
    julian_calendar_start_days;
  int leap_year = julian_calendar_leap_year(year) ? 1 : 0;
  if (month)
    nr_days += nr_days_of_year[leap_year][month - 1];
  nr_days += day;
  return nr_days;
}

bool gregorian_calendar_leap_year(int year)
{
  if (!(year % 400))
    return true;
  else if (!(year % 100))
    return false;
  else if (!(year % 4))
    return true;
  else
    return false;
}

int gregorian_calendar_number_of_leap_years(int syear, int eyear)
{
  // return the number of leap years between [syear, eyear)
  syear--; eyear--;
  return (eyear / 4 - eyear / 100 + eyear / 400) -
    (syear / 4 - syear / 100 + syear / 400);
}

int gregorian_calendar_number_of_days(int year, int month, int day)
{
  int nr_days = (year - start_year) * 365 +
    gregorian_calendar_number_of_leap_years(start_year, year) -
    gregorian_calendar_start_days;
  int leap_year = gregorian_calendar_leap_year(year) ? 1 : 0;
  if (month)
    nr_days += nr_days_of_year[leap_year][month - 1];
  nr_days += day;
  return nr_days;
}

int main()
{
  while (true) {
    int day_of_week, day, month, year, leap_year, j_days, g_days;
    char day_name[nr_chars_max + 1], month_name[nr_chars_max + 1];
    scanf("%s", day_name);
    if (day_name[0] == '#')
      break;
    scanf("%d %s %d", &day, month_name, &year);
    day_of_week = get_day_of_week(day_name), month = get_month(month_name);
    j_days = julian_calendar_number_of_days(year, month, day);
    if ((start_day_of_week + j_days) % nr_days_of_week == day_of_week) {
      // julian calendar
      g_days = j_days + gregorian_calendar_start_days;
      for (year = start_year; ; year++) {
        leap_year = gregorian_calendar_leap_year(year) ? 1 : 0;
        if (g_days <= nr_days_of_year[leap_year][nr_months - 1])
          break;
        g_days -= nr_days_of_year[leap_year][nr_months - 1];
      }
      for (month = 0; ; month++) {
        if (g_days <= nr_days[leap_year][month])
          break;
        g_days -= nr_days[leap_year][month];
      }
      printf("%s %d %s %d\n", day_name, g_days, month_names[month], year);
    }
    else { // gregorian calendar
      g_days = gregorian_calendar_number_of_days(year, month, day);
      j_days = g_days + julian_calendar_start_days;
      for (year = start_year; ; year++) {
        leap_year = julian_calendar_leap_year(year) ? 1 : 0;
        if (j_days <= nr_days_of_year[leap_year][nr_months - 1])
          break;
        j_days -= nr_days_of_year[leap_year][nr_months - 1];
      }
      for (month = 0; ; month++) {
        if (j_days <= nr_days[leap_year][month])
          break;
        j_days -= nr_days[leap_year][month];
      }
      printf("%s %d* %s %d\n", day_name, j_days, month_names[month], year);
    }
  }
  return 0;
}

UVa 11986 - Save from Radiation

Accepted date: 2015-11-05
Ranking (as of 2015-11-06): 14 out of 388
Language: C++

/*
  UVa 11986 - Save from Radiation

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

#include <cstdio>

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    long long N;
    scanf("%lld", &N);
    int nr = 0;
    for ( ; N; N >>= 1)
      nr++;
    printf("Case %d: %d\n", t, nr);
  }
  return 0;
}

UVa 11714 - Blind Sorting

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

/*
  UVa 11714 - Blind Sorting

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

#include <cstdio>
#include <cmath>

int main()
{
  long long n;
  while (scanf("%lld", &n) != EOF)
    printf("%lld\n",
      n + static_cast<long long>(ceil(log2(static_cast<double>(n)))) - 2);
  return 0;
}

UVa 782 - Contour Painting

Accepted date: 2015-11-02
Ranking (as of 2015-11-02): 11 out of 552
Language: C++

/*
  UVa 782 - Contour Painting

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

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

const int nr_rows_max = 100, nr_columns_max = 100;
char grid[nr_rows_max + 1][nr_columns_max + 1];
bool visited[nr_rows_max][nr_columns_max];

int main()
{
  const int nr_dirs = 4;
  const pair<int, int> dirs[nr_dirs] = {
    make_pair(1, 0), make_pair(0, 1), make_pair(-1, 0), make_pair(0, -1)
  };
  int n;
  scanf("%d", &n);
  while (getchar() != '\n')
    ;
  while (n--) {
    int nr_rows = 0, sr = -1, sc;
    memset(grid, 0, sizeof(grid));
    while (true) {
      gets(grid[nr_rows]);
      if (grid[nr_rows][0] == '_')
        break;
      for (char* p = grid[nr_rows]; *p; p++)
        if (*p == '*') {
          sr = nr_rows, sc = p - grid[nr_rows];
          *p = '\0';
        }
      nr_rows++;
    }
    memset(visited, 0, sizeof(visited));
    queue< pair<int, int> > q;
    if (sr != -1) {
      visited[sr][sc] = true;
      q.push(make_pair(sr, sc));
    }
    while (!q.empty()) {
      pair<int, int> u = q.front();
      q.pop();
      for (int i = 0; i < nr_dirs; i++) {
        int r = u.first + dirs[i].first, c = u.second + dirs[i].second;
        if (r >= 0 && r < nr_rows && c >= 0 && c < nr_columns_max) {
          if (grid[r][c] != '\0' && grid[r][c] != ' ' && grid[r][c] != '#')
            grid[u.first][u.second] = '#';
          else if (!visited[r][c]) {
            visited[r][c] = true;
            q.push(make_pair(r, c));
          }
        }
      }
    }
    for (int r = 0; r <= nr_rows; r++) {
      for (int c = nr_columns_max - 1, lc = -1; c >= 0; c--) {
        if (grid[r][c] != '\0' && grid[r][c] != ' ') {
          if (lc == -1)
            lc = c; // last column
        }
        else {
          if (lc != -1)
            grid[r][c] = ' ';
          else
            grid[r][c] = '\0';
        }
      }
      puts(grid[r]);
    }
  }
  return 0;
}

UVa 11464 - Even Parity

Accepted date: 2015-10-20
Ranking (as of 2015-10-20): 18 out of 815
Language: C++

/*
  UVa 11464 - Even Parity

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

#include <cstdio>

const int N_max = 15;
int N, min_count, cells[N_max][N_max], transformations[N_max][N_max];

void transformation(int c, int count)
{
  if (c == N) {
    for (int i = 0; i < N - 1; i++)
      for (int j = 0; j < N; j++) {
        int p = 0;
        if (i)
          p += transformations[i - 1][j];
        if (j)
          p += transformations[i][j - 1];
        if (j < N - 1)
          p += transformations[i][j + 1];
        transformations[i + 1][j] = (p & 1) ? 1 : 0;
        if (!transformations[i + 1][j] && cells[i + 1][j]) // transformation of 1 to 0
          return;
        else if (transformations[i + 1][j] != cells[i + 1][j]) {
          if (++count >= min_count)
            return;
        }
      }
    min_count = count;
#ifdef DEBUG
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        printf("%d%c", transformations[i][j], ((j < N - 1) ? ' ' : '\n'));
    printf("%d %d\n", count, min_count);
#endif
  }
  else {
    int cc = cells[0][c];
    transformations[0][c] = cc;
    transformation(c + 1, count);
    if (!min_count)
      return;
    if (!cc && count + 1 < min_count) {
      transformations[0][c] = 1;
      transformation(c + 1, count + 1);
    }
  }
}

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        scanf("%d", &cells[i][j]);
    min_count = N * N + 1;
    transformation(0, 0);
    printf("Case %d: %d\n", t, ((min_count > N * N) ? -1 : min_count));
  }
  return 0;
}

UVa 11157 - Dynamic Frog

Accepted date: 2015-10-19
Ranking (as of 2015-10-19): 35 out of 945
Language: C++

/*
  UVa 11157 - Dynamic Frog

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

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

const int N_max = 100;

struct stone {
  char type_;
  int m_;
} stones[N_max + 2] = {{'B', 0}};

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int N, D;
    scanf("%d %d", &N, &D);
    stones[N + 1].type_ = 'B';
    stones[N + 1].m_ = D;
    for (int n = 1; n <= N; n++) {
      char s[16];
      scanf("%s", s);
      stones[n].type_ = s[0], stones[n].m_ = atoi(s + 2);
    }
#ifdef DEBUG
    for (int n = 0; n <= N + 1; n++)
      printf("%c-%d%c", stones[n].type_, stones[n].m_, ((n <= N) ? ' ' : '\n'));
#endif
    int max_d = 0;
    if (N) {
#ifdef DEBUG
      puts("left to right");
#endif
      for (int i = 0; i <= N; ) {
        if (stones[i + 1].type_ == 'B') {
          max_d = max(max_d, stones[i + 1].m_ - stones[i].m_);
#ifdef DEBUG
          printf("%d - %d: %d %d\n",
            i, i + 1, stones[i + 1].m_ - stones[i].m_, max_d);
#endif
          i++;
        }
        else {
          max_d = max(max_d, stones[i + 2].m_ - stones[i].m_);
#ifdef DEBUG
          printf("%d - %d: %d %d\n",
            i, i + 2, stones[i + 2].m_ - stones[i].m_, max_d);
#endif
          i += 2;
          if (stones[i].type_ == 'S')
            stones[i].type_ = 0; // will not exist on the way back to the left bank
        }
      }
#ifdef DEBUG
      puts("right to left");
#endif
      for (int i = N + 1; i > 0; ) {
        int j = i - 1;
        for ( ; j > 0 && !stones[j].type_; j--)
          ;
        max_d = max(max_d, stones[i].m_ - stones[j].m_);
#ifdef DEBUG
        printf("%d - %d: %d %d\n", i, j, stones[i].m_ - stones[j].m_, max_d);
#endif
        i = j;
      }
    }
    else
      max_d = D;
    printf("Case %d: %d\n", t, max_d);
  }
  return 0;
}

UVa 10980 - Lowest Price in Town

Accepted date: 2015-10-15
Ranking (as of 2015-10-15): 211 out of 559
Language: C++

/*
  UVa 10980 - Lowest Price in Town

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

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstdio>
using namespace std;

const int M_max = 20, K_max = 100;

struct item_price {
  int N_;
  double P_;
} item_prices[M_max];

double lowest_prices[K_max + 1];

int main()
{
  for (int case_nr = 1; ; case_nr++) {
    string s;
    istringstream iss;
    if (!getline(cin, s))
      break;
    iss.str(s);
    double price;
    int M;
    iss >> price >> M;
    iss.clear();
    for (int i = 0; i < M; i++) {
      getline(cin, s);
      iss.str(s);
      iss >> item_prices[i].N_ >> item_prices[i].P_;
      iss.clear();
    }
    for (int k = 1; k <= K_max; k++) {
      double p = price * k;
      for (int i = 0; i < M; i++) {
        const item_price& ip = item_prices[i];
        p = min(p, ip.P_ * (k + ip.N_ - 1) / ip.N_);
        for (int j = 1; j <= ip.N_; j++)
          if (k - j >= 0)
            p = min(p, lowest_prices[k - j] + ip.P_);
          else
            break;
      }
      lowest_prices[k] = p;
#ifdef DEBUG
      printf("%d: %lf\n", k, p);
#endif
    }
    cout << "Case " << case_nr << ":\n";
    getline(cin, s);
    iss.str(s);
    int K;
    while (iss >> K)
      cout << "Buy " << K << " for $" << fixed << setprecision(2) <<
        lowest_prices[K] << endl;
    iss.clear();
  }
  return 0;
}

UVa 1213 - Sum of Different Primes

Accepted date: 2015-10-14
Ranking (as of 2015-10-14): 460 out of 821
Language: C++

/*
  UVa 1213 - Sum of Different Primes

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

#include <cstdio>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif

const int n_max = 1120, k_max = 14, nr_primes_max = 187;
const int primes[nr_primes_max] = {
     2,    3,    5,    7,   11,   13,   17,   19,   23,   29,
    31,   37,   41,   43,   47,   53,   59,   61,   67,   71,
    73,   79,   83,   89,   97,  101,  103,  107,  109,  113,
   127,  131,  137,  139,  149,  151,  157,  163,  167,  173,
   179,  181,  191,  193,  197,  199,  211,  223,  227,  229,
   233,  239,  241,  251,  257,  263,  269,  271,  277,  281,
   283,  293,  307,  311,  313,  317,  331,  337,  347,  349,
   353,  359,  367,  373,  379,  383,  389,  397,  401,  409,
   419,  421,  431,  433,  439,  443,  449,  457,  461,  463,
   467,  479,  487,  491,  499,  503,  509,  521,  523,  541,
   547,  557,  563,  569,  571,  577,  587,  593,  599,  601,
   607,  613,  617,  619,  631,  641,  643,  647,  653,  659,
   661,  673,  677,  683,  691,  701,  709,  719,  727,  733,
   739,  743,  751,  757,  761,  769,  773,  787,  797,  809,
   811,  821,  823,  827,  829,  839,  853,  857,  859,  863,
   877,  881,  883,  887,  907,  911,  919,  929,  937,  941,
   947,  953,  967,  971,  977,  983,  991,  997, 1009, 1013,
  1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
  1087, 1091, 1093, 1097, 1103, 1109, 1117
};

int nr_ways[n_max + 1][k_max + 1][nr_primes_max];

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  for (int i = 0; i < nr_primes_max; i++)
    nr_ways[primes[i]][1][i] = 1;
  for (int k = 2; k <= k_max; k++) {
    for (int n = 1; n <= n_max; n++)
      for (int i = 0; i < nr_primes_max; i++) {
        int nr = nr_ways[n][k - 1][i];
        if (nr)
          for (int j = i + 1; j < nr_primes_max; j++)
            if (n + primes[j] <= n_max)
              nr_ways[n + primes[j]][k][j] += nr;
      }
#ifdef DEBUG
    for (int n = 1; n <= n_max; n++) {
      bool printed = false;
      for (int i = 0; i < nr_primes_max; i++)
        if (nr_ways[n][k][i]) {
          printed = true;
          printf("[%d][%d][%d]:%d ", n, k, primes[i], nr_ways[n][k][i]);
        }
      if (printed)
        putchar('\n');
    }
#endif
  }
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  while (true) {
    int n, k;
    scanf("%d %d", &n, &k);
    if (!n && !k)
      break;
    int nr = 0;
    for (int i = 0; i < nr_primes_max; i++)
      nr += nr_ways[n][k][i];
    printf("%d\n", nr);
  }
  return 0;
}

UVa 10453 - Make Palindrome

Accepted date: 2015-10-13
Ranking (as of 2015-10-13): 14 out of 1216
Language: C++

/*
  UVa 10453 - Make Palindrome

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

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

const int nr_chars_max = 1000;
enum {upper_left, upper, left};
int c[nr_chars_max + 1][nr_chars_max + 1], b[nr_chars_max + 1][nr_chars_max + 1];

struct cs { // common subsequence
  int i_, j_;
} css[nr_chars_max + 1];

void trace_lcs(const char* s, int i, int j, int& ctr)
{
  if (!i || !j)
    return;
  if (b[i][j] == upper_left) {
    trace_lcs(s, i - 1, j - 1, ctr);
    ctr++;
    css[ctr].i_ = i, css[ctr].j_ = j;
#ifdef DEBUG
    printf("s[%d] t[%d]:%c ", i, j, s[i]);
#endif
  }
  else if (b[i][j] == upper)
    trace_lcs(s, i - 1, j, ctr);
  else
    trace_lcs(s, i, j - 1, ctr);
}

int main()
{
  char s[nr_chars_max + 2], t[nr_chars_max + 2];
  while (gets(s + 1)) {
    int n = strlen(s + 1);
    if (!n) {
      puts("0");
      continue;
    }
    reverse_copy(s + 1, s + n + 1, t + 1);
    t[n + 1] = '\0';
    // calculate the Longest Common Subsequrnce of s and t
    for (int i = 0; i <= n; i++)
      for (int j = 0; j <= n; j++)
        c[i][j] = 0;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (s[i] == t[j]) {
          c[i][j] = c[i - 1][j - 1] + 1;
          b[i][j] = upper_left;
        }
        else if (c[i - 1][j] > c[i][j - 1]) {
          c[i][j] = c[i - 1][j];
          b[i][j] = upper;
        }
        else {
          c[i][j] = c[i][j - 1];
          b[i][j] = left;
        }
#ifdef DEBUG
    printf("%s\n%s\n", s + 1, t + 1);
    printf("%d\n", c[n][n]);
#endif
    int ctr = 0;
    trace_lcs(s, n, n, ctr);
#ifdef DEBUG
    putchar('\n');
#endif
    printf("%d ", n - ctr);
    char u[nr_chars_max * 2 + 2];
    int i = 1, j = 1, k = 1;
    for (int csi = 1; csi <= ctr; csi++) {
      if (i < css[csi].i_)
        do
          u[k++] = s[i++];
        while (i < css[csi].i_);
      if (j < css[csi].j_)
        do
          u[k++] = t[j++];
        while (j < css[csi].j_);
      u[k++] = s[css[csi].i_];
      i++, j++;
    }
    if (i <= n)
      do
        u[k++] = s[i++];
      while (i <= n);
    if (j <= n)
      do
        u[k++] = t[j++];
      while (j <= n);
    u[k] = '\0';
    printf("%s\n", u + 1);
  }
  return 0;
}

UVa 10164 - Number Game

Accepted date: 2015-10-10
Ranking (as of 2015-10-10): 10 out of 481
Language: C++

/*
  UVa 10164 - Number Game

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

#include <cstdio>

const int N_max = 1024;
int N, n, numbers[2 * N_max], solutions[N_max];

bool number_game(int ni, int nr, int s)
{
  if (nr == N)
    return !(s % N);
  else if (ni < n) {
    solutions[nr] = numbers[ni];
    if (number_game(ni + 1, nr + 1, s + numbers[ni]))
      return true;
    if (number_game(ni + 1, nr, s))
      return true;
  }
  return false;
}

int main()
{
  while (true) {
    scanf("%d", &N);
    if (!N)
      break;
    n = 2 * N - 1;
    for (int i = 0; i < n; i++)
      scanf("%d", &numbers[i]);
    if (number_game(0, 0, 0)) {
      puts("Yes");
      for (int i = 0; i < N; i++)
        printf("%d%c", solutions[i], ((i < N - 1) ? ' ' : '\n'));
    }
    else
      puts("No");
  }
  return 0;
}

UVa 10817 - Headmaster's Headache

Accepted date: 2015-10-07
Ranking (as of 2015-10-07): 13 out of 636
Language: C++

/*
  UVa 10817 - Headmaster's Headache

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

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#ifdef DEBUG
#include <cstdio>
#endif
using namespace std;

const int N_max = 100, S_max = 8;
const int pow3s[S_max + 1] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561};

void read_input(int& c, vector<int>& subjects)
{
  string line;
  getline(cin, line);
  istringstream iss(line);
  iss >> c;
  int s;
  while (iss >> s)
    subjects[s - 1]++;
}

int get_index(int s, const vector<int>& subjects)
{
  int index = 0;
  for (int i = 0; i < s; i++)
    index += ((subjects[i] > 2) ? 2 : subjects[i]) * pow3s[i];
  return index;
}

void get_subjects(int index, int s, vector<int>& subjects)
{
  int i;
  for (i = 0; i < s && index; i++, index /= 3)
    subjects[i] = index % 3;
  for ( ; i < s; i++)
    subjects[i] = 0;
}

#ifdef DEBUG
void print_cost(int s, const vector<int>& subjects, int cost)
{
  putchar('[');
  for (int i = 0; i < s; i++) {
    if (i)
      putchar(' ');
    printf("%d", subjects[i]);
  }
  printf("]:%d ", cost);
}
#endif

int main()
{
  while (true) {
    string line;
    getline(cin, line);
    istringstream iss(line);
    int S, m, n;
    iss >> S >> m >> n;
    iss.clear();
    if (!S)
      break;
    int icost = 0;
    vector<int> isubjects(S, 0);
    while (m--) {
      int c;
      read_input(c, isubjects);
      icost += c;
    }
#ifdef DEBUG
    printf("%3d ", 0);
    print_cost(S, isubjects, icost);
    putchar('\n');
#endif
    int s = pow3s[S];
    vector< vector<int> > costs(n + 1, vector<int>(s, -1));
    costs[0][get_index(S, isubjects)] = icost;
    for (int i = 1; i <= n; i++) {
      int c;
      vector<int> subjects(S, 0), psubjects(S);
      read_input(c, subjects);
      for (int j = 0; j < s; j++)
        if (costs[i - 1][j] != -1) {
          if (costs[i][j] == -1)
            costs[i][j] = costs[i - 1][j];
          else
            costs[i][j] = min(costs[i][j], costs[i - 1][j]);
          get_subjects(j, S, psubjects);
          bool employ = false;
          for (int k = 0; k < S; k++)
            if (subjects[k] && psubjects[k] < 2) {
              employ = true;
              psubjects[k]++;
            }
          if (employ) {
            int k = get_index(S, psubjects);
            if (costs[i][k] == -1)
              costs[i][k] = costs[i - 1][j] + c;
            else
              costs[i][k] = min(costs[i][k], costs[i - 1][j] + c);
          }
        }
#ifdef DEBUG
      printf("%3d ", i);
      for (int j = 0; j < s; j++) {
        if (costs[i][j] != -1) {
          get_subjects(j, S, subjects);
          print_cost(S, subjects, costs[i][j]);
        }
      }
      putchar('\n');
#endif
    }
    cout << costs[n][s - 1] << endl;
  }
  return 0;
}

UVa 11055 - Homogeneous squares

Accepted date: 2015-09-29
Ranking (as of 2015-09-29): 10 out of 412
Language: C++

/*
  UVa 11055 - Homogeneous squares

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

#include <cstdio>

const int n_max = 1000;
int diffs[n_max];

int main()
{
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    bool homogeneous = true;
    int i, j, k, pk;
    for (j = 0; j < n; j++, pk = k) {
      scanf("%d", &k);
      if (j)
        diffs[j] = k - pk;
    }
    for (i = 1; i < n; i++) {
      for (j = 0; j < n && homogeneous; j++, pk = k) {
        scanf("%d", &k);
        if (j && k - pk != diffs[j])
          homogeneous = false;
      }
      for ( ; j < n; j++)
        scanf("%*d");
    }
    puts((homogeneous) ? "homogeneous" : "not homogeneous");
  }
  return 0;
}

UVa 12027 - Very Big Perfect Squares

Accepted date: 2015-09-25
Ranking (as of 2015-09-25): 8 out of 228
Language: C++

/*
  UVa 12027 - Very Big Perfect Squares

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

#include <cstdio>
#include <cstring>
#include <cmath>

int main()
{
  const int sqrts[] = {
    0,
    1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4,
    4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6,
    6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
    7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
    9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9
  };
  while (true) {
    const int nr_digits_max = 1001;
    char N[nr_digits_max + 1], A[nr_digits_max + 1];
    scanf("%s", N);
    if (N[0] == '0')
      break;
    int nr_digits = strlen(N), nr_zeros = (nr_digits - 1) / 2, n = N[0] - '0';
    if (!(nr_digits & 1)) {
      n *= 10;
      n += N[1] - '0';
    }
    A[0] = sqrts[n] + '0';
    memset(A + 1, '0', nr_zeros);
    A[nr_zeros + 1] = '\0';
    puts(A);
  }
  return 0;
}

UVa 11800 - Determine the Shape

Accepted date: 2015-09-16
Ranking (as of 2015-09-16): 7 out of 471
Language: C++

/*
  UVa 11800 - Determine the Shape

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

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

const int nr_points = 4;

struct point {
  int x_, y_;

  point() {}
  point(int x, int y) : x_(x), y_(y) {}
  point(const point &p) : x_(p.x_), y_(p.y_) {}
} points[nr_points];

bool left_lower(const point& p, const point& q)
{
  if (p.x_ < q.x_)
    return true;
  else if (p.x_ > q.x_)
    return false;
  else if (p.y_ < q.y_)
    return true;
  else
    return false;
}

int cross_product(const point& o, const point& p, const point& q)
{
  return (p.x_ - o.x_) * (q.y_ - o.y_) - (q.x_ - o.x_) * (p.y_ - o.y_);
}

bool ccw(const point& p, const point& q, const point& r)
{
  // see if the point r is to the left of p -> q (or, p - q - r are counter-clorkwise)
  return cross_product(p, q, r) > 0;
}

struct smaller_angle {
  const point& first;

  smaller_angle(const point& _first) : first(_first) {}
  bool operator() (const point& p, const point& q) const {return ccw(first, p, q);}
};

int square_distance(const point& p, const point& q)
{
  int dx = p.x_ - q.x_, dy = p.y_ - q.y_;
  return dx * dx + dy * dy;
}

bool diagonals_bisect()
{
  return points[0].x_ + points[2].x_ == points[1].x_ + points[3].x_ &&
    points[0].y_ + points[2].y_ == points[1].y_ + points[3].y_;
}

bool diagonals_equal()
{
return square_distance(points[0], points[2]) == square_distance(points[1], points[3]);
}

bool adjacent_sides_equal()
{
return square_distance(points[0], points[1]) == square_distance(points[1], points[2]);
}

bool two_line_seguments_parallel(const point& lp, const point& lq,
  const point& mp, const point& mq)
{
  if (lp.x_ == lq.x_) // vertical line
    return mp.x_ == mq.x_;
  else if (mp.x_ == mq.x_)
    return lp.x_ == lq.x_;
  else
    return (lp.x_ - lq.x_) * (mp.y_ - mq.y_) == (mp.x_ - mq.x_) * (lp.y_ - lq.y_);
}

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    for (int i = 0; i < nr_points; i++)
      scanf("%d %d", &points[i].x_, &points[i].y_);
    sort(points, points + nr_points, left_lower);
      // sort the points in leftmost-lowest order
    sort(points + 1, points + nr_points, smaller_angle(points[0]));
      // sort the second and later points in increasing angular order
    printf("Case %d: ", t);
    if (diagonals_bisect()) {
      if (adjacent_sides_equal()) {
        if (diagonals_equal())
          puts("Square");
        else
          puts("Rhombus");
      }
      else if (diagonals_equal())
        puts("Rectangle");
      else
        puts("Parallelogram");
    }
    else if (two_line_seguments_parallel(points[0], points[1], points[2], points[3])
      || two_line_seguments_parallel(points[1], points[2], points[3], points[0]))
      puts("Trapezium");
    else
      puts("Ordinary Quadrilateral");
  }
  return 0;
}

UVa 11660 - Look-and-Say sequences

Accepted date: 2015-09-15
Ranking (as of 2015-09-15): 1 out of 275
Language: C++

/*
  UVa 11660 - Look-and-Say sequences

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

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

const int i_max = 1000;

void look_and_say_sequence(const char* s, char* t)
{
  int ctr = 1;
  char d = *s++;
  char* u = t;
  for ( ; *s; s++) {
    if (*s != d) {
      *t++ = ctr + '0';
      *t++ = d;
      if (t - u >= i_max) {
        *t = '\0';
        return;
      }
      ctr = 1;
      d = *s;
    }
    else
      ctr++;
  }
  *t++ = ctr + '0';
  *t++ = d;
  *t = '\0';
}

int main()
{
  while (true) {
    int i, j;
    char s[i_max + 1], t[i_max + 1];
    scanf("%s %d %d", s, &i, &j);
    if (s[0] == '0' && !i && !j)
      break;
    char *p = s, *q = t;
    for (int k = 1; k < i; k++) {
      look_and_say_sequence(p, q);
      swap(p, q);
#ifdef DEBUG
      printf("%s\n", p);
#endif
    }
    printf("%c\n", *(p + j - 1));
  }
  return 0;
}

UVa 11666 - Logarithms

Accepted date: 2015-09-14
Ranking (as of 2015-09-14): 3 out of 433
Language: C++

/*
  UVa 11666 - Logarithms

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

#include <cstdio>
#include <cmath>
#include <climits>

/*
  n / exp(L) = 1 - abs(x) < 1
  if x >= 0
    n / exp(L) = 1 - x < 1
  else if x < 0
    n / exp(L) = 1 - x > 1
  else
    n / exp(L) = 1
*/

int main()
{
  const int L_max = 21 /* static_cast<int>(log(static_cast<double>(INT_MAX))) */;
  double exp_Ls[L_max + 1];
  for (int i = 0; i <= L_max; i++)
    exp_Ls[i] = exp(static_cast<double>(i));
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    for (int L = 0; L <= L_max; L++) {
      double x = 1.0 - n / exp_Ls[L];
      if (fabs(x) < 1.0 &&
        (n < exp_Ls[L] && x > 0.0 || n > exp_Ls[L] && x < 0.0 ||
        n == exp_Ls[L] && x == 0.0)) {
        printf("%d %.8lf\n", L, x);
        break;
      }
    }
  }
  return 0;
}

UVa 11968 - In The Airport

Accepted date: 2015-09-14
Ranking (as of 2015-09-14): 4 out of 226
Language: C++

/*
  UVa 11968 - In The Airport

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

#include <cstdio>
#include <cstdlib>

const int N_max = 1000;
int prices[N_max];

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    long long s = 0;
    for (int i = 0; i < N; i++) {
      scanf("%d", &prices[i]);
      s += prices[i];
    }
    int ci = 0, di = M;
    long long n = N, dc = llabs(n * prices[ci] - s), dd = llabs(n * prices[di] - s);
    for (int i = 1; i < M; i++) {
      long long d = llabs(n * prices[i] - s);
      if (d < dc || d == dc && prices[i] < prices[ci]) {
        ci = i;
        dc = d;
      }
    }
    for (int i = M + 1; i < M + K; i++) {
      long long d = llabs(n * prices[i] - s);
      if (d < dd || d == dd && prices[i] < prices[di]) {
        di = i;
        dd = d;
      }
    }
    printf("Case #%d: %d %d\n", t, prices[ci], prices[di]);
  }
  return 0;
}

UVa 12461 - Airplane

Accepted date: 2015-09-03
Ranking (as of 2015-09-03): 63 out of 769
Language: C++

/*
  UVa 12461 - Airplane

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

/*
    probability = 2^(n - 2) / 2^(n - 1) = 1/2

n: 2
  1 2
  2 1 *
                  1/2
n: 3
  1 2 3
  2 1 3
  2 3 1 *
  3 2 1 *
                  2/4

n: 4
  1 2 3 4
  2 1 3 4
  2 3 1 4
  2 3 4 1 *
  2 4 3 1 *
  3 2 1 4
  3 2 4 1 *
  4 2 3 1 *
                  4/8

n: 5
  1 2 3 4 5
  2 1 3 4 5
  2 3 1 4 5
  2 3 4 1 5
  2 3 4 5 1 *
  2 3 5 4 1 *
  2 4 3 1 5
  2 4 3 5 1 *
  2 5 3 4 1 *
  3 2 1 4 5
  3 2 4 1 5
  3 2 4 5 1 *
  3 2 5 4 1 *
  4 2 3 1 5
  4 2 3 5 1 *
  5 2 3 4 1 *
                  8/16

n: 6
  1 2 3 4 5 6
  2 1 3 4 5 6
  2 3 1 4 5 6
  2 3 4 1 5 6
  2 3 4 5 1 6
  2 3 4 5 6 1 *
  2 3 4 6 5 1 *
  2 3 5 4 1 6
  2 3 5 4 6 1 *
  2 3 6 4 5 1 *
  2 4 3 1 5 6
  2 4 3 5 1 6
  2 4 3 5 6 1 *
  2 4 3 6 5 1 *
  2 5 3 4 1 6
  2 5 3 4 6 1 *
  2 6 3 4 5 1 *
  3 2 1 4 5 6
  3 2 4 1 5 6
  3 2 4 5 1 6
  3 2 4 5 6 1 *
  3 2 4 6 5 1 *
  3 2 5 4 1 6
  3 2 5 4 6 1 *
  3 2 6 4 5 1 *
  4 2 3 1 5 6
  4 2 3 5 1 6
  4 2 3 5 6 1 *
  4 2 3 6 5 1 *
  5 2 3 4 1 6
  5 2 3 4 6 1 *
  6 2 3 4 5 1 *
                  16/32

*/

#include <cstdio>

int main()
{
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    puts("1/2");
  }
  return 0;
}

UVa 11536 - Smallest Sub-Array

Accepted date: 2015-08-26
Ranking (as of 2015-08-26): 11 out of 503
Language: C++

/*
  UVa 11536 - Smallest Sub-Array

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

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

const int N_max = 1000000, K_max = 100;
int seq[N_max + 1], freqs[K_max + 1]; // freqs[i] is the number of occurences of i

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    if (K < 4) {
      printf("Case %d: %d\n", t, K);
      continue;
    }
    for (int i = 1; i <= K; i++)
      freqs[i] = 0;
    seq[1] = 1, seq[2] = 2, seq[3] = 3;
    freqs[1] = freqs[2] = freqs[3] = 1;
    int k = 3, min_length = N + 1;
    for (int i = 4, pi = 1; i <= N; i++) {
      int s = (seq[i - 1] + seq[i - 2] + seq[i - 3]) % M + 1;
      seq[i] = s;
      if (s <= K) {
        if (!freqs[s]++) {
          if (++k == K)
            min_length = min(min_length, i - pi + 1);
        }
        else {
          for ( ; pi < i; pi++) {
            int p = seq[pi];
            if (p > K)
              continue;
            if (freqs[p] < 2)
              break;
            freqs[p]--;
          }
          if (k == K)
            min_length = min(min_length, i - pi + 1);
        }
      }
    }
    printf("Case %d: ", t);
    if (min_length > N)
      puts("sequence nai");
    else
      printf("%d\n", min_length);
  }
  return 0;
}

UVa 1121 - Subsequence

Accepted date: 2015-08-24
Ranking (as of 2015-08-24): 14 out of 658
Language: C++

/*
  UVa 1121 - Subsequence

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

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

const int n_max = 100000;
int integers[n_max];

int main()
{
  int N, S;
  while (scanf("%d %d", &N, &S) != EOF) {
    int s = 0, min_length = N + 1;
    for (int i = 0, pi = 0; i < N; i++) {
      scanf("%d", &integers[i]);
      if ((s += integers[i]) >= S) {
        for ( ; pi < i; pi++) {
          if (s - integers[pi] < S)
            break;
          s -= integers[pi];
        }
        min_length = min(min_length, i - pi + 1);
      }
    }
    if (min_length > N)
      min_length = 0;
    printf("%d\n", min_length);
  }
  return 0;
}

UVa 1584 - Circular Sequence

Accepted date: 2015-08-19
Ranking (as of 2015-08-19): 71 out of 636
Language: C++

/*
  UVa 1584 - Circular Sequence

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

#include <cstdio>
#include <cstring>

int compare_string(const char* s, int length, int i, int j)
{
  for (int k = length; k; k--, i = (i + 1) % length, j = (j + 1) % length) {
    if (s[i] > s[j])
      return 1;
    else if (s[i] < s[j])
      return -1;
  }
  return 0;
}

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    const int nr_chars_max = 100;
    char s[nr_chars_max + 1];
    scanf("%s", s);
    int min_i = 0, length = strlen(s);
    for (int i = 1; i < length; i++)
      if (compare_string(s, length, i, min_i) < 0)
        min_i = i;
    printf("%s", &s[min_i]);
    if (min_i) {
      s[min_i] = '\0';
      printf("%s", s);
    }
/*
    for (int k = length; k; k--, min_i = (min_i + 1) % length)
      putchar(s[min_i]);
*/
    putchar('\n');
  }
  return 0;
}

UVa 1339 - Ancient Cipher

Accepted date: 2015-08-18
Ranking (as of 2015-08-18): 68 out of 761
Language: C++

/*
  UVa 1339 - Ancient Cipher

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

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

const int nr_letters = 26, nr_chars_max = 100;

int main()
{
  char s[nr_chars_max + 1], t[nr_chars_max + 1];
  int sl[nr_letters], tl[nr_letters];
  while (scanf("%s", s) != EOF) {
    scanf("%s", t);
    memset(sl, 0, sizeof(sl));
    memset(tl, 0, sizeof(tl));
    for (const char* p = s; *p; p++)
      sl[*p - 'A']++;
    for (const char* p = t; *p; p++)
      tl[*p - 'A']++;
    sort(sl, sl + nr_letters, greater<int>());
    sort(tl, tl + nr_letters, greater<int>());
    bool yes = true;
    for (int i = 0; i < nr_letters && (sl[i] || tl[i]); i++)
      if (sl[i] != tl[i]) {
        yes = false;
        break;
      }
    puts((yes) ? "YES" : "NO");
  }
  return 0;
}

UVa 10898 - Combo Deal

Accepted date: 2015-08-13
Ranking (as of 2015-08-13): 24 out of 479
Language: C++

/*
  UVa 10898 - Combo Deal

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

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

const int nr_items_max = 6, nr_combos_max = 8;

int nr_items, nr_combos, prices[nr_items_max], quantities[nr_items_max], min_payment;
struct combo {
  int quantities_[nr_items_max];
  int price_;
} combos[nr_combos_max];

void combo_deal(int ci, int payment)
{
  if (ci == nr_combos) {
    for (int i = 0; i < nr_items; i++)
      if (quantities[i])
        payment += prices[i] * quantities[i];
      min_payment = min(min_payment, payment);
  }
  else {
    combo& c = combos[ci];
    for (int i = 1; ; i++) {
      int j;
      for (j = 0; j < nr_items; j++)
      if (c.quantities_[j] * i > quantities[j])
        break;
      if (j < nr_items || payment + c.price_ * i >= min_payment)
        break;
      for (j = 0; j < nr_items; j++)
        quantities[j] -= c.quantities_[j] * i;
      combo_deal(ci + 1, payment + c.price_ * i);
      for (j = 0; j < nr_items; j++)
        quantities[j] += c.quantities_[j] * i;
    }
    if (payment < min_payment)
      combo_deal(ci + 1, payment);
  }
}

int main()
{
  while (scanf("%d", &nr_items) != EOF) {
    for (int i = 0; i < nr_items; i++)
      scanf("%d", &prices[i]);
    scanf("%d", &nr_combos);
    for (int i = 0; i < nr_combos; i++) {
      combo& c = combos[i];
      for (int j = 0; j < nr_items; j++)
        scanf("%d", &c.quantities_[j]);
      scanf("%d", &c.price_);
    }
    int nr_orders;
    scanf("%d", &nr_orders);
    while (nr_orders--) {
      min_payment = 0;
      for (int i = 0; i < nr_items; i++) {
        scanf("%d", &quantities[i]);
        min_payment += prices[i] * quantities[i];
      }
      int payment = 0;
      combo_deal(0, payment);
      printf("%d\n", min_payment);
    }
  }
  return 0;
}

UVa 10350 - Liftless EME

Accepted date: 2015-08-07
Ranking (as of 2015-08-07): 8 out of 483
Language: C++

/*
  UVa 10350 - Liftless EME

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

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

const int nr_chars_max = 12, n_max = 120, m_max = 15, ladder = 2;
int times[n_max][m_max][m_max];
  // times[i][j][k] is the time from the i-th floor's j-th hole 
  // to the (i + 1)-th floor's k-th hole
int min_times[n_max][m_max];
  // min_times[i][j] is the min. time needed to reach i-th floor's j-th hole

int main()
{
  char s[nr_chars_max + 1];
  while (scanf("%s", s) != EOF) {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n - 1; i++)
      for (int j = 0; j < m; j++)
        for (int k = 0; k < m; k++)
          scanf("%d", ×[i][j][k]);
    for (int j = 0; j < m; j++)
      min_times[0][j] = 0;
    for (int i = 1; i < n; i++)
      for (int j = 0; j < m; j++) {
        int min_t = numeric_limits<int>::max();
        for (int k = 0; k < m; k++)
          min_t = min(min_t, min_times[i - 1][k] + times[i - 1][k][j]);
        min_times[i][j] = min_t;
      }
    int min_t = numeric_limits<int>::max();
    for (int j = 0; j < m; j++)
      min_t = min(min_t, min_times[n - 1][j]);
    min_t += ladder * (n - 1);
    printf("%s\n%d\n", s, min_t);
  }
  return 0;
}

UVa 1388 - Graveyard

Accepted date: 2015-08-06
Ranking (as of 2015-08-06): 17 out of 489
Language: C++

/*
  UVa 1388 - Graveyard

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

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

const double perimeter = 10000.0;
const int n_max = 1000, m_max = 1000;
double cds[n_max], nds[n_max + m_max]; // current / new distances

int main()
{
  int n, m;
  while (scanf("%d %d", &n, &m) != EOF) {
    m += n;
    for (int i = 0; i < n; i++)
      cds[i] = (perimeter * (i + 1)) / n;
    for (int i = 0; i < m; i++)
      nds[i] = (perimeter * (i + 1)) / m;
    double d = 0.0;
    for (int i = 0, j = 0; i < n - 1; ) {
      if (cds[i] < nds[j]) {
        d += min(cds[i] - nds[j - 1], nds[j] - cds[i]);
        i++;
      }
      else if (cds[i] > nds[j])
        j++;
      else {
        i++, j++;
      }
    }
    printf("%.4lf\n", d);
  }
  return 0;
}

UVa 11088 - End up with More Teams

Accepted date: 2015-08-05
Ranking (as of 2015-08-05): 14 out of 488
Language: C++

/*
  UVa 11088 - End up with More Teams

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

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

const int n_max = 15, members_max = 3, promising = 20;
int integers[n_max];
int sums[n_max]; // sums[i] is the sum between integers[i] and integers[n - 1]
int members[n_max / members_max]; // members[i] is the number of members of i-th team
int points[n_max / members_max]; // ability points of i-th team

bool more_teams(int n, int m, int ti, int nr_teams, int& max_nr_teams)
{
  if (ti == n) {
    max_nr_teams = max(max_nr_teams, nr_teams);
    return max_nr_teams == m;
  }
  else if (n - ti + nr_teams > max_nr_teams) {
    bool more = false;
    for (int i = 0; i < m; i++)
      if (members[i] < members_max && points[i] + sums[ti] >= promising) {
        more = true;
        members[i]++;
        int nr = nr_teams;
        points[i] += integers[ti];
        if (members[i] == members_max && points[i] >= promising)
          nr++;
        if (more_teams(n, m, ti + 1, nr, max_nr_teams))
          return true;
        members[i]--;
        points[i] -= integers[ti];
      }
    if (!more) {
      max_nr_teams = max(max_nr_teams, nr_teams);
      return max_nr_teams == m;
    }
  }
  return false;
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  for (int cn = 1; ; cn++) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    int m = n / members_max; // number of teams
    for (int i = 0; i < n; i++)
      scanf("%d", &integers[i]);
    for (int i = 0; i < m; i++)
      members[i] = points[i] = 0;
    sort(integers, integers + n, greater<int>());
    for (int i = n - 1, s = 0; i >= 0; i--) {
      s += integers[i];
      sums[i] = s;
    }
    int max_nr_teams = 0;
    more_teams(n, m, 0, 0, max_nr_teams);
    printf("Case %d: %d\n", cn, max_nr_teams);
  }
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0;
}

UVa 12896 - Mobile SMS

Accepted date: 2015-08-01
Ranking (as of 2015-08-01): 23 out of 499
Language: C++

/*
  UVa 12896 - Mobile SMS

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

#include <cstdio>

const int L_max = 100, N_max = 9, P_max = 4;

const char keys[N_max + 1][P_max + 1] = {
  {'\0', ' '},
  {'\0', '.', ',', '?', '"'},
  {'\0', 'a', 'b', 'c'},
  {'\0', 'd', 'e', 'f'},
  {'\0', 'g', 'h', 'i'},
  {'\0', 'j', 'k', 'l'},
  {'\0', 'm', 'n', 'o'},
  {'\0', 'p', 'q', 'r', 's'},
  {'\0', 't', 'u', 'v'},
  {'\0', 'w', 'x', 'y', 'z'}
};

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int L, Ns[L_max];
    scanf("%d", &L);
    for (int i = 0; i < L; i++)
      scanf("%d", &Ns[i]);
    char message[L_max + 1];
    for (int i = 0; i < L; i++) {
      int P;
      scanf("%d", &P);
      message[i] = keys[Ns[i]][P];
    }
    message[L] = '\0';
    puts(message);
  }
}

UVa 12068 - Harmonic Mean

Accepted date: 2015-07-31
Ranking (as of 2015-07-31): 16 out of 634
Language: C++

/*
  UVa 12068 - Harmonic Mean

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

#include <cstdio>

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

int main()
{
  int S;
  scanf("%d", &S);
  for (int s = 1; s <= S; s++) {
    const int N_max = 8;
    int N, numbers[N_max];
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
      scanf("%d", &numbers[i]);
    long long numerator = N, denominator = 0;
    for (int i = 0; i < N; i++) {
      numerator *= numbers[i];
      long long d = 1;
      for (int j = 0; j < N - 1; j++)
        d *= numbers[(i + j) % N];
      denominator += d;
    }
    long long g = gcd(numerator, denominator);
    printf("Case %d: %lld/%lld\n", s, numerator / g, denominator / g);
  }
  return 0;
}

UVa 11752 - The Super Powers

Accepted date: 2015-07-31
Ranking (as of 2015-07-31): 4 out of 498
Language: C++

/*
  UVa 11752 - The Super Powers

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

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

const int n_max = 65536;
const int composite_numbers[] = {
  4, 6, 8, 9, 10,
  12, 14, 15, 16, 18, 20,
  21, 22, 24, 25, 26, 27, 28, 30,
  32, 33, 34, 35, 36, 38, 39, 40,
  42, 44, 45, 46, 48, 49, 50,
  51, 52, 54, 55, 56, 57, 58, 60,
  62, 63, 64
};

inline unsigned long long square(unsigned long long n)
{
  return n * n;
}

unsigned long long power(unsigned long long base, int exp)
{
  if (!exp)
    return 1;
  else if (!(exp & 1))
    return square(power(base, exp >>= 1));
  else
    return base * power(base, exp - 1);
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  const double log10_max =
    log10(static_cast<double>(numeric_limits<unsigned long long>::max()));
  vector<unsigned long long> super_powers;
  for (int i = 2; i < n_max; i++) {
    double c_max = log10_max / log10(static_cast<double>(i));
    for (int j = 0; composite_numbers[j] < c_max; j++) {
      super_powers.push_back(power(i, composite_numbers[j]));
#ifdef DEBUG
      printf("%d %d %llu\n", i, composite_numbers[j], super_powers.back());
#endif
    }
  }
#ifdef DEBUG
  printf("%d\n", super_powers.size());
#endif
  sort(super_powers.begin(), super_powers.end());
  vector<unsigned long long>::iterator se =
    unique(super_powers.begin(), super_powers.end());
  super_powers.resize(distance(super_powers.begin(), se));
#ifdef DEBUG
  printf("%d\n", super_powers.size());
#endif
  puts("1");
  for (size_t i = 0; i < super_powers.size(); i++)
    printf("%llu\n", super_powers[i]);
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0;
}

UVa 11347 - Multifactorials

Accepted date: 2015-07-27
Ranking (as of 2015-07-27): 2 out of 353
Language: C++

/*
  UVa 11347 - Multifactorials

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

#include <cstdio>
#include <cstring>
#include <cmath>

const int n_max = 1000, k_max = 20;
const long long infinity = 1000000000000000000;
int exps[n_max + 1];

void divisors(int n)
{
  int i, j, e = 0;
  for ( ; !(n & 1); n >>= 1)
    e++;
  if (e) {
    exps[2] += e;
    e = 0;
  }
  for (i = 3, j = static_cast<int>(ceil(sqrt(static_cast<double>(n)))); i <= j; ) {
    if (!(n % i)) {
      e++;
      n /= i;
    }
    else {
      if (e) {
        exps[i] += e;
        e = 0;
      }
      i += 2;
    }
  }
  if (e)
    exps[i] += e;
  if (n > 1)
    exps[n] += 1;
}

int main()
{
  int N;
  scanf("%d", &N);
  for (int cn = 1; cn <= N; cn++) {
    int n;
    char s[k_max + 1];
    scanf("%d%s", &n, s);
    int k = strlen(s);
    for (int i = 2; i <= n; i++)
      exps[i] = 0;
    for (int i = n; i > 1; i -= k)
      divisors(i);
    long long nr = 1;
    for (int i = 2; i <= n; i++)
      if (exps[i] && (nr *= exps[i] + 1) > infinity) {
        nr = 0;
        break;
      }
    printf("Case %d: ", cn);
    if (nr)
      printf("%lld\n", nr);
    else
      puts("Infinity");
  }
  return 0;
}

UVa 11395 - Sigma Function

Accepted date: 2015-07-26
Ranking (as of 2015-07-26): 32 out of 228
Language: C++

/*
  UVa 11395 - Sigma Function

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

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

/*
Sigma Function of n is odd if and only if n is square or twice square.
*/

int main()
{
  while (true) {
    long long N;
    cin >> N;
    if (!N)
      break;
    int i = static_cast<int>(sqrt(static_cast<double>(N))),
      j = static_cast<int>(sqrt(static_cast<double>(N / 2)));
    cout << N - (i + j) << endl;
  }
  return 0;
}

UVa 10212 The Last Non-zero Digit

Accepted date: 2015-07-25
Ranking (as of 2015-07-25): 188 out of 1126
Language: C++

/*
  UVa 10212 The Last Non-zero Digit

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

#include <cstdio>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif

const int N_max = 20000000;
const int pow2s[] = {1,
  2, 4, 8, 16, 32, 64, 128, 256,
  512, 1024, 2048, 4096, 8192, 16384, 32768, 65536,
  131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216,
  33554432
};
const int p2s[] = {6, 2, 4, 8};
const int pow5s[] = {1,
  5, 25, 125, 625, 3125, 15625, 78125, 390625,
  1953125, 9765625, 48828125
};
char twos[N_max + 1], fives[N_max + 1];
char integers[N_max + 1];

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  for (int i = 1; i < sizeof(pow2s) / sizeof(int) - 1; i++)
    for (long long j = pow2s[i]; j <= N_max; j += pow2s[i]) {
      twos[j]++;
    }
  for (int i = 1; i < sizeof(pow5s) / sizeof(int) - 1; i++)
    for (long long j = pow5s[i]; j <= N_max; j += pow5s[i])
      fives[j]++;
  for (int i = 1; i <= N_max; i++)
    integers[i] = static_cast<char>(i / pow2s[twos[i]] / pow5s[fives[i]] % 10);
  int N, M;
  while (scanf("%d %d", &N, &M) != EOF) {
    int p = 1;
    int t = 0, f = 0;
    for (int i = N, j = N - M; i > j; i--) {
      p *= integers[i];
      p %= 10;
      t += twos[i]; f += fives[i];
    }
#ifdef DEBUG
    printf("%d %d %d\n", p, t, f);
#endif
    if (t || f) {
      if (t > f) {
        p *= p2s[(t - f) % 4];
        p %= 10;
      }
      else if (t < f) {
        p *= 5;
        p %= 10;
      }
    }
    printf("%d\n", p);
  }
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0;
}

UVa 10680 - LCM

Accepted date: 2015-07-23
Ranking (as of 2015-07-23): 2 out of 1034
Language: C++

/*
  UVa 10680 - LCM

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

#include <cstdio>
#include <cmath>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif

const int n_max = 1000000,
  sqrt_n_max = static_cast<int>(sqrt(static_cast<double>(n_max)));
bool not_primes[n_max + 1]; // not_primes[i] is true if i is not a prime
int power_of_primes[n_max + 1];
  // power_of_primes[i] is a positive number p if i is a power of prime number p, 
  // otherwise 0
long long lcms[n_max + 1]; // lcms[i] is the last nonzero digit of LCM of 1 to i

void sieve_of_eratosthenes()
{
  not_primes[0] = not_primes[1] = true;
  for (int i = 2; i <= sqrt_n_max; i++)
    if (!not_primes[i]) {
      for (int j = i * i; j <= n_max; j += i)
        not_primes[j] = true;
    }
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  sieve_of_eratosthenes();
  for (int i = 2; i <= sqrt_n_max; i++)
    if (!not_primes[i]) {
      for (long long j = static_cast<long long>(i) * i; j <= n_max; j *= i)
        power_of_primes[j] = i;
    }
  lcms[1] = 1; lcms[2] = 2;
  long long l = lcms[2];
  for (int i = 3; i <= n_max; i++) {
    if (!not_primes[i] || power_of_primes[i]) {
      if (!not_primes[i])
        l *= i;
      else
        l *= power_of_primes[i];
      while (!(l % 10))
        l /= 10;
      l %= n_max;
#ifdef DEBUG
      printf("%d: %lld\n", i, l);
#endif
    }
    lcms[i] = l % 10;
  }
#ifdef DEBUG
  printf("%lld\n", lcms[n_max]);
#endif
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    printf("%lld\n", lcms[n]);
  }
  return 0;
}

UVa 911 - Multinomial Coefficients

Accepted date: 2015-07-22
Ranking (as of 2015-07-22): 63 out of 263
Language: C++

/*
  UVa 911 - Multinomial Coefficients

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

#include <cstdio>

int main()
{
  const int k_max = 100;
  long long bc[k_max + 1][k_max + 1]; // binomial coefficient
  for (int i = 0; i <= k_max; i++)
    bc[i][0] = 1;
  for (int j = 0; j <= k_max; j++)
    bc[j][j] = 1;
  for (int i = 1; i <= k_max; i++)
    for (int j = 1; j < i; j++)
      bc[i][j] = bc[i - 1][j - 1] + bc[i - 1][j];

  int n;
  while (scanf("%d", &n) != EOF) {
    int k;
    scanf("%d", &k);
    long long mc = 1;
    while (k--) {
      int i;
      scanf("%d", &i);
      mc *= bc[n][i];
      n -= i;
    }
    printf("%lld\n", mc);
  }
  return 0;
}

UVa 11254 - Consecutive Integers

Accepted date: 2015-07-21
Ranking (as of 2015-07-21): 180 out of 744
Language: C++

/*
  UVa 11254 - Consecutive Integers

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

/*
  See Wikipedia for Polite number.
*/

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

const int nr_sums_max = 44721;
int sums[nr_sums_max + 1];
int power_of_2s[] = {
  2, 4, 8, 16, 32, 64, 128, 256,
  512, 1024, 2048, 4096, 8192, 16384, 32768, 65536,
  131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216,
  33554432, 67108864, 134217728, 268435456, 536870912
};

int main()
{
  for (int i = 1; i <= nr_sums_max; i++)
    sums[i] = sums[i - 1] + i;
#ifdef DEBUG
  printf("%d\n", sums[nr_sums_max]); // 1000006281
#endif
  while (true) {
    int n;
    scanf("%d", &n);
    if (n == -1)
      break;
    if (binary_search(power_of_2s, power_of_2s + sizeof(power_of_2s) / sizeof(int), n))
      printf("%d = %d + ... + %d\n", n, n, n);
    else {
      for (int i = distance(sums, lower_bound(sums, sums + nr_sums_max + 1, n)); ; i--)
        if (!((n - sums[i]) % i)) {
          int j = (n - sums[i]) / i;
          printf("%d = %d + ... + %d\n", n, j + 1, i + j);
          break;
        }
    }
  }
  return 0;
}

UVa 11955 - Binomial Theorem

Accepted date: 2015-07-16
Ranking (as of 2015-07-16): 11 out of 499
Language: C++

/*
  UVa 11955 - Binomial Theorem

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

#include <cstdio>
#include <cstdlib>

int main()
{
  const int k_max = 50;
  long long bc[k_max + 1][k_max + 1]; // binomial coefficient
  for (int i = 0; i <= k_max; i++)
    bc[i][0] = 1;
  for (int j = 0; j <= k_max; j++)
    bc[j][j] = 1;
  for (int i = 1; i <= k_max; i++)
    for (int j = 1; j < i; j++)
      bc[i][j] = bc[i - 1][j - 1] + bc[i - 1][j];

  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    const int nr_chars_max = 100;
    char s[nr_chars_max + 1], a[nr_chars_max + 1], b[nr_chars_max + 1];
    scanf("%s", s);
    const char* p = s + 1;
    char* q;
    for (q = a; *p != '+'; p++, q++)
      *q = *p;
    p++;
    *q = '\0';
    for (q = b; *p != ')'; p++, q++)
      *q = *p;
    p += 2;
    *q = '\0';
    int k = atoi(p);
#ifdef DEBUG
    printf("%s %s %d\n", a, b, k);
#endif
    printf("Case %d: ", t);
    for (int i = k, j = 0; i >= 0; i--, j++) {
      if (bc[k][j] > 1)
        printf("%lld*", bc[k][j]);
      if (i) {
        printf("%s", a);
        if (i > 1)
          printf("^%d", i);
      }
      if (i && j)
        putchar('*');
      if (j) {
        printf("%s", b);
        if (j > 1)
          printf("^%d", j);
      }
      if (i)
        putchar('+');
    }
    putchar('\n');
  }
  return 0;
}

UVa 11103 - WFF 'N PROOF

Accepted date: 2015-07-06
Ranking (as of 2015-07-06): 50 out of 390
Language: C++

/*
  UVa 11103 - WFF 'N PROOF

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

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

const int nr_chars_max = 100;
char symbols[nr_chars_max + 1];
int indices[nr_chars_max];

bool compare_symbol(int i, int j)
{
  char ci = symbols[i], cj = symbols[j];
  if (isupper(ci) && isupper(cj)) {
    if (ci == 'N' && cj == 'N')
      return i < j;
    else if (ci == 'N')
      return true;
    else if (cj == 'N')
      return false;
    else
      return i < j;
  }
  else if (islower(ci) && islower(cj))
    return i < j;
  else
    return ci < cj;
}

int main()
{
  while (true) {
    scanf("%s", symbols);
    if (!strcmp(symbols, "0"))
      break;
    int nr_symbols = strlen(symbols), nr_Ns = 0, nr_KACEs = 0, nr_variables = 0;
    for (int i = 0; i < nr_symbols; i++) {
      indices[i] = i;
      switch (symbols[i]) {
      case 'N':
        nr_Ns++; break;
      case 'K': case 'A': case 'C': case 'E':
        nr_KACEs++; break;
      case 'p': case 'q': case 'r': case 's': case 't':
        nr_variables++; break;
      }
    }
    sort(indices, indices + nr_symbols, compare_symbol);
#ifdef DEBUG
    for (int i = 0; i < nr_symbols; i++)
      putchar(symbols[indices[i]]);
    putchar('\n');
#endif
    int nr_wff_KACEs = nr_KACEs, nr_wff_variables = nr_variables;
    if (nr_wff_variables) {
      if (nr_wff_KACEs > nr_wff_variables - 1)
        nr_wff_KACEs = nr_wff_variables - 1;
      else
        nr_wff_variables = nr_wff_KACEs + 1;
      for (int i = 0; i < nr_Ns; i++)
        putchar('N');
      for (int i = nr_Ns, j = nr_wff_KACEs; j; i++, j--)
        putchar(symbols[indices[i]]);
      for (int i = nr_Ns + nr_KACEs, j = nr_wff_variables; j; i++, j--)
        putchar(symbols[indices[i]]);
      putchar('\n');
    }
    else
      puts("no WFF possible");
  }
  return 0;
}

UVa 11108 - Tautology

Accepted date: 2015-07-05
Ranking (as of 2015-07-05): 27 out of 437
Language: C++

/*
  UVa 11108 - Tautology

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

#include <cstdio>
#include <cstring>
#include <cctype>
#include <stack>
using namespace std;

char get_op(stack<char>& st, int variables[], int values)
{
  char op = st.top(); st.pop();
  if (islower(op))
    op = (values & (1 << variables[op - 'p'])) ? 1 : 0;
  return op;
}

bool evaluate(const char wff[], int wlength, int variables[], int values)
{
  stack<char> st;
  char op1, op2;
  for (int i = wlength - 1; i >= 0; i--) {
    switch (wff[i]) {
    case 'K':
      op1 = get_op(st, variables, values), op2 = get_op(st, variables, values);
      st.push(op1 & op2);
      break;
    case 'A':
      op1 = get_op(st, variables, values), op2 = get_op(st, variables, values);
      st.push(op1 | op2);
      break;
    case 'N':
      op1 = get_op(st, variables, values);
      st.push((op1) ? 0 : 1);
      break;
    case 'C':
      op1 = get_op(st, variables, values), op2 = get_op(st, variables, values);
      st.push((op1 == 1 && op2 == 0) ? 0 : 1);
      break;
    case 'E':
      op1 = get_op(st, variables, values), op2 = get_op(st, variables, values);
      st.push((op1 == op2) ? 1 : 0);
      break;
    default:
      st.push(wff[i]);
      break;
    }
  }
  return get_op(st, variables, values) == 1;
}

int main()
{

  while (true) {
    const int nr_chars_max = 100;
    char wff[nr_chars_max + 1];
    scanf("%s", wff);
    if (wff[0] == '0')
      break;
    int variables['t' - 'p' + 1];
    memset(variables, -1, sizeof(variables));
    int length = strlen(wff), nr_variables = 0;
    for (int i = 0; i < length; i++)
      if (islower(wff[i])) {
        int j = wff[i] - 'p';
        if (variables[j] == -1)
          variables[j] = nr_variables++;
      }
    bool tautology = true;
    for (int i = 0, j = 1 << nr_variables; i < j && tautology; i++)
      if (!evaluate(wff, length, variables, i))
        tautology = false;
    puts((tautology) ? "tautology" : "not");
  }
  return 0;
}

UVa 10659 - Fitting Text into Slides

Accepted date: 2015-07-02
Ranking (as of 2015-07-02): 50 out of 220
Language: C++

/*
  UVa 10659 - Fitting Text into Slides

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

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

const int P_min = 8, P_max = 28;

int fit(int M, int p_max, int X, int Y, const vector< vector<int> >& paragraphs)
{
  for (int p = p_max; p >= P_min; p--) {
    int y = 0;
    for (int i = 0; i < M; i++) {
      const vector<int>& paragraph = paragraphs[i];
      int x = 0;
      for (size_t j = 0, je = paragraph.size(); j < je; j++) {
        int k = paragraph[j] * p;
        if (k > X) {
          if (j < je - 1) { // exclude a space
            if (x + k - p <= X) {
              x = 0;
              y += p;
            }
            else if (k - p <= X) {
              if (x) {
                x = 0;
                y += p;
              }
              y += p;
            }
            else
              y = Y + 1;
            if (y > Y)
              break;
          }
          else {
            y = Y + 1;
            break;
          }
        }
        else if (x + k > X) {
          if (j < je - 1 && x + k - p <= X) { // exclude a space
            x = 0;
            y += p;
          }
          else {
            x = k;
            y += p;
          }
          if (y > Y)
            break;
        }
        else {
          x += k;
          if (x == X) {
            x = 0;
            y += p;
          }
        }
      }
      if (x)
        y += p;
      if (y > Y)
        break;
    }
    if (y <= Y)
      return p;
  }
  return -1;
}

int main()
{
  int N;
  cin >> N;
  while (N--) {
    int M;
    cin >> M;
    string s;
    getline(cin, s);
    int max_length = 0;
    vector< vector<int> > paragraphs(M);
    for (int i = 0; i < M; i++) {
      getline(cin, s);
      vector<int>& paragraph = paragraphs[i];
      for (const char *p = s.c_str(); *p; ) {
        const char* q = p;
        while (*p)
          if (*p++ == ' ')
            break;
        int length = p - q;
        paragraph.push_back(length);
        if (*p)
          length--; // exclude a space
        max_length = max(max_length, length);
      }
    }
    int X, Y;
    cin >> X >> Y;
    int p = -1, p_max = min(P_max, X / max_length);
    if (p_max >= P_min)
      p = fit(M, p_max, X, Y, paragraphs);
    if (p != -1)
      cout << p << endl;
    else
      cout << "No solution\n";
  }
  return 0;
}

UVa 11987 - Almost Union-Find

Accepted date: 2015-06-25
Language: C++

/*
  UVa 11987 - Almost Union-Find

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

#include <cstdio>

const int n_max = 100000 + 1;

class almost_union_find {
public:
  void make_set(int i);
  int find_set(int i) const;
  void move(int i, int j);
  void do_union(int i, int j);
  int size(int i) const;
  long long sum(int i) const;

private:
  struct set {
    int size_;
    int head_, tail_;
  };

  struct element {
    int set_;
    int prev_, next_;
  };

  int n_;
  set sets_[n_max];
  element elements_[n_max];
};

void almost_union_find::make_set(int i)
{
  sets_[i].size_ = 1;
  sets_[i].head_ = sets_[i].tail_ = i;
  elements_[i].set_ = i;
  elements_[i].prev_ = elements_[i].next_ = -1;
}

int almost_union_find::find_set(int i) const
{
  return sets_[elements_[i].set_].head_;
}

void almost_union_find::do_union(int i, int j)
{
  if (elements_[i].set_ == elements_[j].set_)
    return;
  set &si = sets_[elements_[i].set_], &sj = sets_[elements_[j].set_];
  if (si.size_ >= sj.size_) {
    si.size_ += sj.size_;
    elements_[sj.head_].prev_ = si.tail_;
    elements_[si.tail_].next_ = sj.head_;
    si.tail_ = sj.tail_;
    for (int next = sj.head_; next != -1; next = elements_[next].next_)
      elements_[next].set_ = elements_[i].set_;
  }
  else {
    sj.size_ += si.size_;
    elements_[si.head_].prev_ = sj.tail_;
    elements_[sj.tail_].next_ = si.head_;
    sj.tail_ = si.tail_;
    for (int next = si.head_; next != -1; next = elements_[next].next_)
      elements_[next].set_ = elements_[j].set_;
  }
}

void almost_union_find::move(int i, int j)
{
  if (elements_[i].set_ == elements_[j].set_)
    return;
  int prev, next;
  set &si = sets_[elements_[i].set_], &sj = sets_[elements_[j].set_];
  if (si.size_ > 1) {
    si.size_--;
    if (si.head_ == i) {
      next = elements_[i].next_;
      si.head_ = next;
      elements_[next].prev_ = -1;
    }
    else if (si.tail_ == i) {
      prev = elements_[i].prev_;
      si.tail_ = prev;
      elements_[prev].next_ = -1;
    }
    else {
      prev = elements_[i].prev_, next = elements_[i].next_;
      elements_[prev].next_ = next, elements_[next].prev_ = prev;
    }
  }
  sj.size_++;
  elements_[i].set_ = elements_[j].set_;
  elements_[sj.tail_].next_ = i;
  elements_[i].prev_ = sj.tail_, elements_[i].next_ = -1;
  sj.tail_ = i;
}

int almost_union_find::size(int i) const
{
  return sets_[elements_[i].set_].size_;
}

long long almost_union_find::sum(int i) const
{
  long long s = 0;
  for (int next = sets_[elements_[i].set_].head_;
    next != -1; next = elements_[next].next_)
    s += next;
  return s;
}

almost_union_find auf;

int main()
{
  int n, m;
  while (scanf("%d %d", &n, &m) != EOF) {
    for (int i = 1; i <= n; i++)
      auf.make_set(i);
    while (m--) {
      int c, p, q;
      scanf("%d", &c);
      switch (c) {
      case 1:
        scanf("%d %d", &p, &q);
        auf.do_union(p, q);
        break;
      case 2:
        scanf("%d %d", &p, &q);
        auf.move(p, q);
        break;
      case 3:
        scanf("%d", &p);
        printf("%d %lld\n", auf.size(p), auf.sum(p));
        break;
      }
    }
  }
  return 0;
}

UVa 12348 - Fun Coloring

Accepted date: 2015-06-23
Ranking (as of 2015-06-23): 10 out of 119
Language: C++

/*
  UVa 12348 - Fun Coloring

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

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

const int n_max = 22, m_max = 111, nr_members_max = 3;

struct set {
  int nr_members_;
  int members_[nr_members_max];
} sets[m_max];

int k, n, m;
char colors[n_max + 1];

bool coloring(int mi);

inline bool coloring(int mi, int ci, char rbi)
{
  char pci = colors[ci];
  colors[ci] = rbi;
  bool result = coloring(mi + 1);
  colors[ci] = pci;
  return result;
}

inline bool coloring(int mi, int ci, char rbi, int cj, char rbj)
{
  char pci = colors[ci], pcj = colors[cj];
  colors[ci] = rbi; colors[cj] = rbj;
  bool result = coloring(mi + 1);
  colors[ci] = pci; colors[cj] = pcj;
  return result;
}

inline bool coloring(int mi, int ci, char rbi, int cj, char rbj, int ck, char rbk)
{
  char pci = colors[ci], pcj = colors[cj], pck = colors[ck];
  colors[ci] = rbi; colors[cj] = rbj; colors[ck] = rbk;
  bool result = coloring(mi + 1);
  colors[ci] = pci; colors[cj] = pcj; colors[ck] = pck;
  return result;
}

bool coloring(int mi)
{
  if (mi == m) {
#ifdef DEBUG
    for (int i = 1; i <= n; i++)
      cout << colors[i] << ' ';
    cout << endl;
#endif
    return true;
  }
  else {
    set& st = sets[mi];
    if (st.nr_members_ < 1)
      return false;
    int ci = st.members_[0];
    if (st.nr_members_ < 2) {
      if (colors[ci])
        return coloring(mi + 1);
      else {
        if (coloring(mi, ci, 'R'))
          return true;
        return coloring(mi, ci, 'B');
      }
    }
    int cj = st.members_[1];
    if (st.nr_members_ < 3) {
      if (colors[ci] && colors[cj]) {
        if (colors[ci] == colors[cj])
          return false;
        else
          return coloring(mi + 1);
      }
      else if (!colors[ci] && colors[cj])
        return coloring(mi, ci, (colors[cj] == 'R') ? 'B': 'R');
      else if (colors[ci] && !colors[cj])
        return coloring(mi, cj, (colors[ci] == 'R') ? 'B': 'R');
      else {
        if (coloring(mi, ci, 'R', cj, 'B'))
          return true;
        return coloring(mi, ci, 'B', cj, 'R');
      }
    }
    int ck = st.members_[2];
    char rb;
    if (colors[ci] && colors[cj] && colors[ck]) {
      if (colors[ci] == colors[cj] && colors[ci] == colors[ck])
        return false;
      else
        return coloring(mi + 1);
    }
    else if (!colors[ci] && colors[cj] && colors[ck]) {
      if (colors[cj] ==  colors[ck])
        return coloring(mi, ci, (colors[cj] == 'R') ? 'B' : 'R');
      else {
        if (coloring(mi, ci, 'R'))
          return true;
        return coloring(mi, ci, 'B');
      }
    }
    else if (colors[ci] && !colors[cj] && colors[ck]) {
      if (colors[ci] == colors[ck])
        return coloring(mi, cj, (colors[ci] == 'R') ? 'B' : 'R');
      else {
        if (coloring(mi, cj, 'R'))
          return true;
        return coloring(mi, cj, 'B');
      }
    }
    else if (colors[ci] && colors[cj] && !colors[ck]) {
      if (colors[ci] == colors[cj])
        return coloring(mi, ck, (colors[ci] == 'R') ? 'B' : 'R');
      else {
        if (coloring(mi, ck, 'R'))
          return true;
        return coloring(mi, ck, 'B');
      }
    }
    else if (!colors[ci] && !colors[cj] && colors[ck]) {
      rb = (colors[ck] == 'R') ? 'B' : 'R';
      if (coloring(mi, ci, rb, cj, rb))
        return true;
      if (coloring(mi, ci, 'R', cj, 'B'))
        return true;
      return coloring(mi, ci, 'B', cj, 'R');
    }
    else if (!colors[ci] && colors[cj] && !colors[ck]) {
      rb = (colors[cj] == 'R') ? 'B' : 'R';
      if (coloring(mi, ci, rb, ck, rb))
        return true;
      if (coloring(mi, ci, 'R', ck, 'B'))
        return true;
      return coloring(mi, ci, 'B', ck, 'R');
    }
    else if (colors[ci] && !colors[cj] && !colors[ck]) {
      rb = (colors[ci] == 'R') ? 'B' : 'R';
      if (coloring(mi, cj, rb, ck, rb))
        return true;
      if (coloring(mi, cj, 'R', ck, 'B'))
        return true;
      return coloring(mi, cj, 'B', ck, 'R');
    }
    else {
      if (coloring(mi, ci, 'R', cj, 'R', ck, 'B'))
        return true;
      if (coloring(mi, ci, 'R', cj, 'B', ck, 'R'))
        return true;
      if (coloring(mi, ci, 'B', cj, 'R', ck, 'R'))
        return true;
      if (coloring(mi, ci, 'B', cj, 'B', ck, 'R'))
        return true;
      if (coloring(mi, ci, 'B', cj, 'R', ck, 'B'))
        return true;
      return coloring(mi, ci, 'R', cj, 'B', ck, 'B');
    }
  }
}

int main()
{
  cin >> k;
  while (k--) {
    cin >> n >> m;
    string s;
    getline(cin, s);
    for (int i = 0; i < m; i++) {
      getline(cin, s);
      istringstream iss(s);
      set& st = sets[i];
      st.nr_members_ = 0;
      while (iss >> st.members_[st.nr_members_])
        st.nr_members_++;
    }
    memset(colors, 0, sizeof(colors));
    cout << ((coloring(0)) ? 'Y' : 'N');
  }
  return 0;
}

UVa 12043 - Divisors

Accepted date: 2015-06-21
Ranking (as of 2015-06-21): 183 out of 501
Language: C++

/*
  UVa 12043 - Divisors

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

#include <cstdio>
#include <cmath>

/*
  for n = p1^e1 * p2^e2 * p3^e3 * ... * pn^en
  number of divisors = (e1 + 1) * (e2 + 1) * (e3 + 1) * ... * (en + 1)
  sum of divisors = ((p1^(e1 + 1) - 1) / (p1 - 1)) * ((p2^(e2 + 1) - 1) / (p2 - 1)) *
    ((p3^(e3 + 1) - 1) / (p3 - 1)) * ... * ((pn^(en + 1) - 1) / (pn - 1))
*/

const int n_max = 100000;
int number_of_divisors[n_max + 1], sum_of_divisors[n_max + 1];
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif

void divisors(int n)
{
  int nn = n, nd = 1, e = 0, i, j;
  long long sd = 1, p = 1;
  for ( ; !(n & 1); n >>= 1) {
    e++;
    p *= 2;
  }
  if (e) {
    nd *= e + 1;
    sd *= p * 2 - 1;
    e = 0, p = 1;
  }
  for (i = 3, j = static_cast<int>(ceil(sqrt(static_cast<double>(n)))); i <= j; ) {
    if (!(n % i)) {
      e++;
      p *= i;
      n /= i;
    }
    else {
      if (e) {
        nd *= e + 1;
        sd *= (p * i - 1) / (i - 1);
        e = 0, p = 1;
      }
      i += 2;
    }
  }
  if (e) {
    nd *= e + 1;
    sd *= (p * i - 1) / (i - 1);
  }
  if (n > 1) {
    nd *= 2;
    sd *= (static_cast<long long>(n) * n - 1) / (n - 1);
  }
  number_of_divisors[nn] = nd;
  sum_of_divisors[nn] = sd;
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  for (int i = 1; i <= n_max; i++)
    divisors(i);
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
#ifdef DEBUG
  for (int i = 1; i <= n_max; i++)
    printf("%d: %d %lld\n", i, number_of_divisors[i], sum_of_divisors[i]);
#endif
  int T;
  scanf("%d", &T);
  while (T--) {
    int a, b, k;
    scanf("%d %d %d", &a, &b, &k);
    int snd = 0;
    long long ssd = 0;
    for ( ; a <= b; a++)
      if (!(a % k)) {
        snd += number_of_divisors[a];
        ssd += sum_of_divisors[a];
      }
    printf("%d %lld\n", snd, ssd);
  }
  return 0;
}

UVa 433 - Bank (Not Quite O.C.R.)

Accepted date: 2015-06-20
Ranking (as of 2015-06-20): 6 out of 342
Language: C++

/*
  UVa 433 - Bank (Not Quite O.C.R.)

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

#include <cstdio>
#include <cstring>

const int nr_digit_columns = 3, nr_digit_rows = 3, nr_digits = 10,
  nr_account_digits = 9;
  char segs[nr_digit_rows][nr_digit_columns * nr_account_digits + 1];
const int digit_patterns[nr_digits] =
  {0x3f, 0x06, 0x5b, 0x4f, 0x66, 0x6d, 0x7d, 0x07, 0x7f, 0x6f};
/*
individual segments of seven-segment display
   GFEDCBA
0: 0111111 3f
1: 0000110 06
2: 1011011 5b
3: 1001111 4f
4: 1100110 66
5: 1101101 6d
6: 1111101 7d
7: 0000111 07
8: 1111111 7f
9: 1101111 6f
*/

struct digit {
  int pattern_, number_, deduced_;
} digits[nr_account_digits];


int read_digit(int di, int ci)
{
  int p = 0;
  if (segs[0][ci + 1] == '_')
    p |= 0x01;
  if (segs[1][ci + 2] == '|')
    p |= 0x02;
  if (segs[2][ci + 2] == '|')
    p |= 0x04;
  if (segs[2][ci + 1] == '_')
    p |= 0x08;
  if (segs[2][ci] == '|')
    p |= 0x10;
  if (segs[1][ci] == '|')
    p |= 0x20;
  if (segs[1][ci + 1] == '_')
    p |= 0x40;
  digits[di].pattern_ = p;
  digits[di].number_ = -1;
  for (int i = 0; i < nr_digits; i++)
    if (digit_patterns[i] == p) {
      digits[di].number_ = i;
      break;
    }
  return digits[di].number_;
}

bool checksum()
{
  int s = 0;
  for (int i = 0, j = 9; i < nr_account_digits; i++, j--) {
    if (digits[i].number_ == -1)
      return false;
    s += digits[i].number_ * j;
  }
  return (s % 11) ? false : true;
}

void print_digits()
{
  for (int i = 0; i < nr_account_digits; i++)
    printf("%c", ((digits[i].number_ != -1) ? '0' + digits[i].number_ : '?'));
  putchar('\n');
}

int main()
{
  int nr_numbers;
  scanf("%d", &nr_numbers);
  while (getchar() != '\n')
    ;
  while (nr_numbers--) {
    memset(segs, 0, sizeof(segs));
    for (int i = 0; i < nr_digit_rows; i++)
      gets(segs[i]);
    int garbled = -1;
    for (int i = 0; i < nr_account_digits; i++)
      if (read_digit(i, i * nr_digit_columns) == -1)
        garbled = i;
#ifdef DEBUG
    print_digits();
#endif
    int ctr = 0;
    if (garbled != -1) {
      digit& d = digits[garbled];
      for (int i = 0; i < nr_digits; i++)
        if (!d.pattern_ ||
          d.pattern_ & digit_patterns[i] && !(d.pattern_ & ~digit_patterns[i])) {
          d.number_ = i;
          if (checksum()) {
            d.deduced_ = i;
            ctr++;
          }
        }
      if (ctr == 1)
        d.number_ = d.deduced_;
    }
    else if (checksum())
      ctr = 1;
    else {
      int di;
      for (int i = 0; i < nr_account_digits && ctr < 2; i++) {
        digit&d = digits[i];
        if (digits[i].pattern_ == 0x7f)
          continue;
        int n = d.number_;
        for (int j = 0; j < nr_digits && ctr < 2; j++)
          if (d.pattern_ & digit_patterns[j] && !(d.pattern_ & ~digit_patterns[j])) {
            d.number_ = j;
            if (checksum()) {
              di = i;
              d.deduced_ = j;
              ctr++;
            }
          }
        d.number_ = n;
      }
      if (ctr == 1)
        digits[di].number_ = digits[di].deduced_;
    }
    if (ctr > 1)
      puts("ambiguous");
    else if (ctr == 1)
      print_digits();
    else
      puts("failure");
  }
  return 0;
}