UVa 11582 - Colossal Fibonacci Numbers!

Accepted date: 2016-10-30
Run Time: 0.010
Ranking (as of 2016-10-30): 24 out of 440
Language: C++

/*
  UVa 11582 - Colossal Fibonacci Numbers!

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

#include <cstdio>

const int pisano_periods[] = {
  0,
  1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, 24, 18, 60,
  16, 30, 48, 24, 100, 84, 72, 48, 14, 120, 30, 48, 40, 36, 80, 24, 76, 18, 56, 60,
  40, 48, 88, 30, 120, 48, 32, 24, 112, 300, 72, 84, 108, 72, 20, 48, 72, 42, 58, 120,
  60, 30, 48, 96, 140, 120, 136, 36, 48, 240, 70, 24, 148, 228, 200, 18, 80, 168, 78, 120,
  216, 120, 168, 48, 180, 264, 56, 60, 44, 120, 112, 48, 120, 96, 180, 48, 196, 336, 120, 300,
  50, 72, 208, 84, 80, 108, 72, 72, 108, 60, 152, 48, 76, 72, 240, 42, 168, 174, 144, 120,
  110, 60, 40, 30, 500, 48, 256, 192, 88, 420, 130, 120, 144, 408, 360, 36, 276, 48, 46, 240,
  32, 210, 140, 24, 140, 444, 112, 228, 148, 600, 50, 36, 72, 240, 60, 168, 316, 78, 216, 240,
  48, 216, 328, 120, 40, 168, 336, 48, 364, 180, 72, 264, 348, 168, 400, 120, 232, 132, 178, 120,
  90, 336, 120, 48, 380, 120, 180, 96, 144, 180, 190, 96, 388, 588, 280, 336, 396, 120, 22, 300,
  136, 150, 112, 72, 40, 624, 48, 168, 90, 240, 42, 108, 280, 72, 440, 72, 240, 108, 296, 60,
  252, 456, 448, 48, 600, 228, 456, 72, 114, 240, 80, 84, 52, 168, 160, 174, 312, 144, 238, 120,
  240, 330, 648, 60, 560, 120, 252, 60, 168, 1500, 250, 48, 240, 768, 360, 384, 516, 264, 304, 420,
  168, 390, 176, 120, 540, 144, 88, 408, 268, 360, 270, 72, 112, 276, 100, 48, 556, 138, 120, 240,
  56, 96, 568, 210, 360, 420, 80, 48, 612, 420, 392, 444, 588, 336, 580, 228, 360, 444, 336, 600,
  176, 150, 200, 72, 60, 72, 88, 240, 208, 60, 310, 168, 628, 948, 240, 78, 636, 216, 70, 480,
  72, 48, 36, 216, 700, 984, 216, 120, 32, 120, 110, 168, 456, 336, 680, 48, 676, 1092, 152, 180,
  30, 72, 784, 264, 240, 348, 232, 168, 174, 1200, 504, 240, 236, 696, 140, 132, 144, 534, 358, 120,
  342, 90, 440, 336, 740, 120, 736, 48, 120, 1140, 432, 120, 748, 180, 1000, 96, 28, 144, 378, 180,
  256, 570, 768, 192, 80, 1164, 264, 588, 388, 840, 144, 336, 520, 396, 780, 120, 796, 66, 144, 600,
  200, 408, 420, 150, 1080, 336, 380, 72, 408, 120, 552, 624, 464, 48, 840, 336, 184, 90, 418, 240,
  84, 42, 96, 108, 900, 840, 240, 72, 280, 1320, 430, 72, 868, 240, 280, 108, 144, 888, 438, 60,
  336, 252, 888, 456, 220, 1344, 296, 96, 448, 600, 40, 228, 200, 456, 560, 72, 916, 114, 72, 240,
  46, 240, 928, 168, 120, 156, 936, 168, 272, 480, 632, 348, 440, 312, 900, 144, 216, 714, 478, 240,
  532, 240, 48, 330, 980, 648, 976, 60, 328, 1680, 490, 120, 252, 252, 120, 120, 560, 168, 498, 1500,
  336, 750, 1008, 48, 100, 240, 728, 768, 254, 360, 592, 768, 72, 516, 1040, 264, 160, 912, 696, 420,
  26, 168, 1048, 390, 400, 528, 180, 120, 1104, 540, 696, 144, 280, 264, 360, 408, 712, 804, 560, 360,
  90, 270, 360, 144, 540, 336, 1096, 276, 120, 300, 126, 48, 624, 1668, 760, 138, 124, 120, 616, 240,
  360, 168, 376, 96, 380, 1704, 432, 420, 568, 360, 570, 420, 760, 240, 1200, 96, 1156, 612, 776, 420,
  336, 1176, 540, 444, 840, 588, 1176, 336, 90, 1740, 792, 456, 1188, 360, 720, 444, 88, 336, 598, 600,
  600, 528, 408, 150, 220, 600, 1216, 144, 112, 60, 224, 72, 1228, 264, 40, 240, 1236, 624, 206, 60,
  144, 930, 176, 168, 2500, 1884, 360, 948, 684, 240, 630, 156, 168, 636, 1280, 216, 112, 210, 840, 960,
  640, 72, 1288, 48, 440, 36, 1296, 216, 290, 2100, 240, 984, 1308, 216, 260, 120, 888, 96, 658, 120,
  220, 330, 504, 168, 720, 456, 336, 336, 448, 2040, 60, 48, 1348, 2028, 1800, 1092, 452, 456, 784, 180,
  456, 30, 1368, 72, 1380, 2352, 456, 264, 756, 240, 138, 348, 240, 696, 460, 168, 360, 174, 104, 1200,
  700, 504, 684, 480, 160, 708, 400, 696, 118, 420, 312, 132, 240, 144, 140, 534, 952, 1074, 718, 120,
  208, 342, 240, 90, 700, 1320, 1456, 336, 1944, 2220, 792, 120, 1468, 2208, 560, 48, 680, 120, 738, 1140,
  504, 432, 496, 120, 740, 2244, 168, 180, 144, 3000, 750, 96, 1000, 84, 100, 144, 1516, 378, 240, 180,
  380, 768, 432, 570, 360, 768, 812, 384, 192, 240, 1032, 1164, 1548, 264, 300, 588, 304, 1164, 360, 840,
  70, 144, 504, 336, 1580, 1560, 1576, 396, 176, 780, 304, 120, 420, 2388, 1080, 66, 228, 144, 288, 1200,
  264, 600, 740, 408, 240, 420, 536, 300, 202, 1080, 270, 336, 1080, 1140, 1640, 72, 792, 408, 336, 120,
  820, 552, 1648, 624, 200, 1392, 1656, 48, 276, 840, 1112, 672, 1008, 552, 1680, 90, 360, 1254, 838, 240,
  406, 84, 56, 42, 1820, 96, 880, 216, 568, 900, 912, 840, 1708, 240, 360, 72, 1716, 840, 78, 1320,
  80, 1290, 1728, 144, 1740, 2604, 1224, 240, 390, 840, 952, 108, 1176, 144, 2000, 888, 1756, 438, 1176, 120,
  176, 336, 1768, 252, 1160, 888, 1776, 456, 256, 660, 1080, 1344, 288, 888, 1780, 192, 336, 1344, 210, 600,
  108, 120, 176, 228, 180, 600, 1816, 456, 600, 1680, 70, 72, 840, 2748, 120, 114, 1040, 72, 102, 240,
  88, 138, 140, 240, 1900, 2784, 624, 336, 928, 120, 1008, 156, 1240, 936, 180, 168, 1876, 816, 1256, 480,
  470, 1896, 240, 696, 720, 1320, 1896, 312, 1036, 900, 1272, 144, 212, 216, 380, 714, 280, 1434, 1104, 480,
  930, 1596, 72, 240, 1940, 48, 176, 660, 72, 2940, 970, 648, 368, 2928, 1400, 120, 652, 984, 220, 1680,
  216, 1470, 1968, 120, 1980, 252, 32, 252, 528, 120, 198, 240, 440, 1680, 220, 168, 1996, 498, 1368, 1500
};

int modpow(unsigned long long base, unsigned long long exp, int modulas)
{
  int b = static_cast<int>(base % modulas);
  int result = 1;
  while (exp) {
    if (exp & 1)
      result = (result * b) % modulas;
    b = (b * b) % modulas;
    exp >>= 1;
  }
  return result;
}

int fibonacci(int n, int modulo)
{
  int fib[2][2] = {{1, 1}, {1, 0}}, result[2][2]= {{1, 0}, {0, 1}};
  while (n) {
    if(n & 1) {
      int r[2][2] = {};
      for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
          for (int k = 0; k < 2; k++)
            r[i][j] = (r[i][j] + result[i][k] * fib[k][j] % modulo) % modulo;
      for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
          result[i][j] = r[i][j];
        }
    int r[2][2] = {};
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        for (int k = 0; k < 2; k++)
          r[i][j] = (r[i][j] + fib[i][k] * fib[k][j] % modulo) % modulo;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        fib[i][j] = r[i][j];
    n /= 2;
  }
#ifdef DEBUG
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++)
        printf("[%d][%d]:%lld%c", i, j, result[i][j], ((j < 1) ?  ' ' : '\n'));
#endif
  return result[0][1];
}

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    unsigned long long a, b;
    int n;
    scanf("%llu %llu %d", &a, &b, &n);
    printf("%lld\n", fibonacci(modpow(a, b, pisano_periods[n]), n));
  }
  return 0;
}

UVa 10690 - Expression Again

Accepted date: 2016-10-28
Run Time: 0.160
Ranking (as of 2016-10-28): 35 out of 395
Language: C++

/*
  UVa 10690 - Expression Again

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

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

const int N_max = 50, M_max = 50, integer_min = -50, integer_max = 50;
const int first_term_min = (N_max + M_max) * integer_min,
  first_term_max = (N_max + M_max) * integer_max;
int integers[N_max + M_max + 1];

bool expressions[2][N_max + 1][first_term_max - first_term_min + 1];
  // expressions[i][j][k] is true for the product of up to (i % 2)-th integers 
  // with j integers for the first term and sum of j integers (the first term) being k

#ifdef DEBUG
void print_expressions(int i,int j, int k_min, int k_max, const bool exps[])
{
  printf("[%d][%d]:", i, j);
  for (int k = k_min; k <= k_max; k++)
    if (exps[k])
      printf(" %d", k + first_term_min);
  putchar('\n');
}
#endif

int main()
{
  int N, M;
  while (scanf("%d %d", &N, &M) != EOF) {
    int s = 0;
    for (int i = 1; i <= N + M; i++) {
      scanf("%d", &integers[i]);
      s += integers[i];
    }
    memset(&expressions[1], 0, sizeof(expressions[0]));
    int pj_min = 0, pj_max = 1, integer = integers[1];
    int pk_min = 0 - first_term_min, pk_max = integer - first_term_min;
    expressions[1][pj_min][pk_min] = expressions[1][pj_max][pk_max] = true;
#ifdef DEBUG
    print_expressions(1, pj_min, pk_min, pk_min, expressions[1][pj_min]);
    print_expressions(1, pj_max, pk_max, pk_max, expressions[1][pj_max]);
#endif
    if (pk_min > pk_max)
      swap(pk_min, pk_max);
    for (int i = 2; i <= N + M; i++) {
      int pi = (i - 1) %2, ci = i % 2;
      int cj_min = max(0, i - M), cj_max = min(i, N);
      int ck_min = pk_min, ck_max = pk_max;
      memset(&expressions[ci], 0, sizeof(expressions[0]));
      integer = integers[i];
      for (int j = pj_min; j <= pj_max; j++) {
        for (int k = pk_min; k <= pk_max; k++)
          if (expressions[pi][j][k]) {
            expressions[ci][j][k] = true;
            if (j < cj_max) {
              expressions[ci][j + 1][k + integer] = true;
              ck_min = min(ck_min, k + integer), ck_max = max(ck_max, k + integer);
            }
          }
      }
      pj_min = cj_min, pj_max = cj_max;
      pk_min = ck_min, pk_max = ck_max;
#ifdef DEBUG
      for (int j = pj_min; j <= pj_max; j++)
        print_expressions(i, j, pk_min, pk_max, expressions[ci][j]);
#endif
    }
    int ci = (N + M) % 2, p_min = (N_max + M_max) * integer_max + 1,
      p_max = (N_max + M_max) * integer_min - 1;
    for (int k = pk_min; k <= pk_max; k++)
      if (expressions[ci][pj_min][k]) {
        int p = k + first_term_min;
        p *= s - p;
        p_min = min(p_min, p), p_max = max(p_max, p);
      }
    printf("%d %d\n", p_max, p_min);
  }
  return 0;
}

UVa 11832 - Account Book

Accepted date: 2016-10-24
Run Time: 0.040
Ranking (as of 2016-10-24): 16 out of 384
Language: C++

/*
  UVa 11832 - Account Book

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

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

const int N_max = 40, F_min = -16000, F_max = 16000;

int Ti[N_max + 1];
bool cash_flow[N_max + 1][F_max - F_min + 1][2];
  // cash_flow[i][j][0/1] is the cash_flow of j, up to i-th transaction, 
  // with i-th transaction of income (1) or expense (0)
char transactions[N_max + 2];

void transaction(int n, int f)
{
  int t = Ti[n];
  if (cash_flow[n][f - F_min][0]) {
    cash_flow[n][f - F_min][0] = false;
    if (transactions[n] != '?')
      transactions[n] = (transactions[n] == '+') ? '?' : '-';
#ifdef DEBUG
    printf("[%d][%d][0]: %c\n", n, f, transactions[n]);
#endif
    if (n > 1)
      transaction(n - 1, f + t);
  }
  if (cash_flow[n][f - F_min][1]) {
    cash_flow[n][f - F_min][1] = false;
    if (transactions[n] != '?')
      transactions[n] = (transactions[n] == '-') ? '?' : '+';
#ifdef DEBUG
    printf("[%d][%d][1]: %c\n", n, f, transactions[n]);
#endif
    if (n > 1)
      transaction(n - 1, f - t);
  }
}

int main()
{
  while (true) {
    int N, F;
    scanf("%d %d", &N, &F);
    if (!N)
      break;
    for (int i = 1; i <= N; i++)
      scanf("%d", &Ti[i]);
    memset(cash_flow, 0, sizeof(cash_flow));
    int j_min = -Ti[1] - F_min, j_max = Ti[1] - F_min;
    cash_flow[1][j_min][0] = cash_flow[1][j_max][1] = true;
#ifdef DEBUG
    printf("[1][%d][0] [1][%d][1]\n", j_min + F_min, j_max + F_min);
#endif
    for (int i = 2; i <= N; i++) {
      int t = Ti[i];
      for (int j = j_min; j <= j_max; j++)
        if (cash_flow[i - 1][j][0] || cash_flow[i - 1][j][1]) {
          if (j - t >= 0)
            cash_flow[i][j - t][0] = true;
          if (j + t <= F_max - F_min)
          cash_flow[i][j + t][1] = true;
        }
      j_min = max(j_min - t, 0), j_max = min(j_max + t, F_max - F_min);
#ifdef DEBUG
      for (int j = j_min; j <= j_max; j++)
        for (int k = 0; k < 2; k++)
          if (cash_flow[i][j][k])
            printf("[%d][%d][%d] ", i, j + F_min, k);
      putchar('\n');
#endif
    }
    if (cash_flow[N][F - F_min][0] || cash_flow[N][F - F_min][1]) {
      memset(transactions, 0, sizeof(transactions));
      transaction(N, F);
      puts(transactions + 1);
    }
    else
      puts("*");
  }
  return 0;
}

UVa 10094 - Place the Guards

Accepted date: 2016-10-17
Run Time: 0.000
Ranking (as of 2016-10-17): 9 out of 422
Language: C++

For more information, see Wikipedia's article Eight queens puzzle.

/*
  UVa 10094 - Place the Guards

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

#include <cstdio>
#ifdef DEBUG
#include <cassert>
#include <cstdlib>
#endif

const int n_max = 1000;
int rows[n_max + 1]; // rows[i] is the row number for i-th column

#ifdef DEBUG
bool validate_rows(int n)
{
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (i != j) {
        if (rows[i] == rows[j] || abs(i - j) == abs(rows[i] - rows[j]))
          return false;
      }
  return true;
}
#endif

int main()
{
  int n;
  while (scanf("%d", &n) != EOF) {
    if (n < 4)
      puts("Impossible");
    else {
      int m = n;
      if (m & 1) { // odd
        rows[m] = m;
        m--;
      }
      int i, j, k;
      if ((m - 2) % 6)
        for (i = 1, j = m / 2; i <= j; i++) {
          k = 2 * i;
          rows[i] = k, rows[j + i] = k - 1;
        }
      else
        for (i = 1, j = m / 2; i <= j; i++) {
          k = (2 * i + j - 3) % m;
          rows[i] = 1 + k, rows[m + 1 - i] = m - k;
        }
#ifdef DEBUG
      assert(validate_rows(n));
#endif
      for (int i = 1; i <= n; i++)
        printf("%d%c", rows[i], ((i < n) ? ' ' : '\n'));
    }
  }
  return 0;
}

UVa 12101 - Prime Path

Accepted date: 2016-10-14
Run Time: 0.000
Ranking (as of 2016-10-14): 28 out of 378
Language: C++

/*
  UVa 12101 - Prime Path

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

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

const int n_min = 1000, n_max = 9999, nr_digits = '9' - '0' + 1;

bool not_primes[n_max + 1]; // not_primes[i] is true if i is not a prime
bool visited[n_max + 1];

void sieve_of_eratosthenes()
{
  not_primes[0] = not_primes[1] = true;
  for (int i = 2, e = static_cast<int>(sqrt(static_cast<double>(n_max))); i <= e; i++)
    if (!not_primes[i]) {
      for (int j = i * i; j <= n_max; j += i)
        not_primes[j] = true;
    }
}

struct path {
  int p_; // prime
  int s_; // steps

  path(int p, int s) : p_(p), s_(s) {}
};

void push_prime(queue<path>& q, int s, int d0, int d1, int d2, int d3)
{
  int p = d0 * 1000 + d1 * 100 + d2 * 10 + d3;
  if (!not_primes[p] && !visited[p]) {
    visited[p] = true;
    q.push(path(p, s));
  }
}

int bfs(int start, int end)
{
  queue<path> q;
  memset(visited, 0, sizeof(visited));
  visited[start] = true;
  q.push(path(start, 0));
  while (!q.empty()) {
    path p = q.front();
    q.pop();
    if (p.p_ == end)
      return p.s_;
    int d0 = p.p_ / 1000, d1 = p.p_ % 1000 / 100,
      d2 = p.p_ % 100 / 10, d3 = p.p_ % 10, s = p.s_ + 1;
    for (int d = 1; d < nr_digits; d++)
      push_prime(q, s, d, d1, d2, d3);
    for (int d = 0; d < nr_digits; d++)
      push_prime(q, s, d0, d, d2, d3);
    for (int d = 0; d < nr_digits; d++)
      push_prime(q, s, d0, d1, d, d3);
    for (int d = 1; d < nr_digits; d += 2)
      push_prime(q, s, d0, d1, d2, d);
  }
  return -1;
}

int main()
{
  sieve_of_eratosthenes();
  int t;
  scanf("%d", &t);
  while (t--) {
    int start, end;
    scanf("%d %d", &start, &end);
    int steps = bfs(start, end);
    if (steps != -1)
      printf("%d\n", steps);
    else
      puts("Impossible");
  }
  return 0;
}

UVa 718 - Skyscraper Floors

Accepted date: 2016-10-13
Run Time: 0.010
Ranking (as of 2016-10-13): 72 out of 415
Language: C++

/*
  UVa 718 - Skyscraper Floors

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

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

// extended Euclidean Algorithm
long long gcd_ex(long long a, long long b, long long& x, long long& y)
{
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  long long x1, y1;
  long long d = gcd_ex(b, a % b, x1, y1);
  x = y1, y = x1 - (a / b) * y1;
  return d;
}

bool linear_diophantine_equation(int a, int b, int c,
  long long& d, long long& x0, long long& y0)
{
  long long u, v;
  d = gcd_ex(a, b, u, v);
  if (c % d)
    return false;
  x0 = u * (c / d), y0 = v * (c / d);
  return true;
}

bool reachable(int Xi, int Xj, int Yi, int Yj, int F)
{
  long long d, x0, y0;
  if (!linear_diophantine_equation(Xi, -Xj, Yj - Yi, d, x0, y0))
    return false;
  int xi = static_cast<int>(Xi / d), xj = static_cast<int>(-Xj / d);
  double d_min = static_cast<double>(-x0) / xj,
    d_max = (static_cast<double>(F - 1 - Yi) / Xi - x0) / xj;
  if (xj < 0)
    swap(d_min, d_max);
  int ti_min = static_cast<int>(ceil(d_min)), ti_max = static_cast<int>(floor(d_max));
  d_min = (y0 - static_cast<double>(F - 1 - Yj) / Xj) / xi,
    d_max = static_cast<double>(y0) / xi;
  if (xi < 0)
    swap(d_min, d_max);
  int tj_min = static_cast<int>(ceil(d_min)), tj_max = static_cast<int>(floor(d_max));
  return (ti_min > tj_max || ti_max < tj_min) ? false : true;
}

const int E_max = 100;

int Xs[E_max], Ys[E_max];
bool A_reachables[E_max], B_reachables[E_max], reachables[E_max][E_max];

int main()
{
  int N;
  scanf("%d", &N);
  while (N--) {
    int F, E, A, B;
    scanf("%d %d %d %d", &F, &E, &A, &B);
    for (int i = 0; i < E; i++)
      scanf("%d %d", &Xs[i], &Ys[i]);
    for (int i = 0; i < E; i++) {
      A_reachables[i] = A >= Ys[i] && !((A - Ys[i]) % Xs[i]);
      B_reachables[i] = B >= Ys[i] && !((B - Ys[i]) % Xs[i]);
    }
    for (int i = 0; i < E - 1; i++)
      for (int j = i + 1; j < E; j++)
        reachables[i][j] = reachables[j][i] = reachable(Xs[i], Xs[j], Ys[i], Ys[j], F);
#ifdef DEBUG
    for (int i = 0; i < E - 1; i++)
      for (int j = i + 1; j < E; j++)
        if (reachables[i][j])
          printf("[%d][%d] ", i, j);
    putchar('\n');
#endif
    for (int k = 0; k < E; k++)
      for (int i = 0; i < E; i++)
        for (int j = 0; j < E; j++)
          reachables[i][j] |= reachables[i][k] && reachables[k][j];
    bool possible = false;
    for (int i = 0; i < E && !possible; i++)
      if (A_reachables[i])
        for (int j = 0; j < E && !possible; j++)
          if (B_reachables[j] && reachables[i][j])
            possible = true;
    puts((possible) ? "It is possible to move the furniture." :
      "The furniture cannot be moved.");
  }
  return 0;
}

UVa 11552 - Fewest Flops

Accepted date: 2016-10-06
Run Time: 0.000
Ranking (as of 2016-10-06): 27 out of 466
Language: C++

/*
  UVa 11552 - Fewest Flops

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

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

const int nr_letters = 26, nr_chars_max = 1000, infinite = nr_chars_max + 1;
int nr_chunks[nr_chars_max]; // number of chunks in Si
int freqs[nr_chars_max][nr_letters];
  // freqs[i][j] is the number of occurrences of ('a' + j) charactor in Si
int min_nr_chunks[nr_chars_max][nr_letters];
  // min_nr_chunks[i][j] min. number of chunks up to Si with the last character of of j

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int k;
    char S[nr_chars_max + 1];
    scanf("%d %s", &k, S);
    int length = strlen(S), n = length / k;
    for (int i = 0, si = 0; i < n; i++, si += k) {
      nr_chunks[i] = 0;
      memset(&freqs[i], 0, sizeof(freqs[0]));
      for (int j = 0; j < k; j++)
        if (!freqs[i][S[si + j] - 'a']++)
          nr_chunks[i]++;
    }
    for (int j = 0; j < nr_letters; j++)
      min_nr_chunks[0][j] = (freqs[0][j]) ? nr_chunks[0] : infinite;
    for (int i = 1; i < n; i++)
      for (int j = 0; j < nr_letters; j++)
        min_nr_chunks[i][j] = infinite;

#ifdef DEBUG
    for (int j = 0; j < nr_letters; j++)
      if (min_nr_chunks[0][j] < infinite)
        printf("[0][%c]: %d ", 'a' + j, min_nr_chunks[0][j]);
    putchar('\n');
#endif
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < nr_letters; j++) {
        if (freqs[i][j])
          for (int k = 0; k < nr_letters; k++)
            if (freqs[i + 1][k]) {
              int nr = 0;
              if (j != k)
                nr = (freqs[i + 1][j]) ? nr_chunks[i + 1] - 1 : nr_chunks[i + 1];
              else if (nr_chunks[i + 1] != 1) // j == k
                nr = nr_chunks[i + 1];
              min_nr_chunks[i + 1][k] = min(min_nr_chunks[i + 1][k], min_nr_chunks[i][j] + nr);
            }
      }
#ifdef DEBUG
      for (int j = 0; j < nr_letters; j++)
        if (min_nr_chunks[i + 1][j] < infinite)
          printf("[%d][%c]: %d ", i + 1, 'a' + j, min_nr_chunks[i + 1][j]);
      putchar('\n');
#endif
    }
    int min_nr = infinite;
    for (int j = 0; j < nr_letters; j++)
      min_nr = min(min_nr, min_nr_chunks[n - 1][j]);
    printf("%d\n", min_nr);
  }
  return 0;
}

UVa 10964 - Strange Planet

Accepted date: 2016-10-05
Run Time: 0.000
Ranking (as of 2016-10-05): 8 out of 378
Language: C++11

/*
  UVa 10964 - Strange Planet

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

#include <cstdio>
#include <cmath>

void get_coordinate(int c, int& x, int& y)
{
  int d = static_cast<int>((1.0 + sqrt(1.0 + static_cast<double>(c) * 2.0)) / 2.0);
    // c is in the d-th diamond shape from the origin
  if (2 * d * (d - 1) == c)
    d--;
  x = 1 - d, y = 1;
  int c_min = 2 * d * (d - 1) + 1, c_max = c_min + d - 1;
  if (c <= c_max)
    x += c - c_min, y += c - c_min;
  else {
    x += c_max - c_min, y += c_max - c_min;
    c_min = c_max, c_max += d;
    if (c <= c_max)
      x += c - c_min, y -= c - c_min;
    else {
      x += c_max - c_min, y -= c_max - c_min;
      c_min = c_max, c_max += d;
      if (c <= c_max)
        x -= c - c_min, y -= c - c_min;
      else {
        x -= c_max - c_min, y -= c_max - c_min;
        c_min = c_max, c_max += d;
        x -= c - c_min, y += c - c_min;
      }
    }
  }
#ifdef DEBUG
  printf("%d: (%d, %d)\n", c, x, y);
#endif
}

int main()
{
  while (true) {
    int a, b;
    scanf("%d %d", &a, &b);
    if (a == -1)
      break;
    int ax, ay, bx, by;
    get_coordinate(a, ax, ay);
    get_coordinate(b, bx, by);
    printf("%.2lf\n", hypot(static_cast<double>(ax - bx), static_cast<double>(ay - by)));
  }
  return 0;
}

UVa 493 - Rational Spiral

Accepted date: 2016-10-04
Run Time: 0.000
Ranking (as of 2016-10-04): 12 out of 479
Language: C++

/*
  UVa 493 - Rational Spiral

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

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

const int n_max = 650, nr_rationals_max = 514407;
int coprimes[n_max];

struct rational {
  int numerator_, denominator_;
} rationals[nr_rationals_max] = {
  {1, 1}, {0, 1}, {-1, 1}
};
int nr_rationals = 3;

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

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  for (int i = 2; i <= n_max; i++) {
    int nr_coprimes = 0;
    for (int j = 1; j < i; j++)
      if (gcd(i, j) == 1)
        coprimes[nr_coprimes++] = j;
    for (int j = nr_coprimes - 1; j >= 0; j--, nr_rationals++)
      rationals[nr_rationals].numerator_ = -i,
        rationals[nr_rationals].denominator_ = coprimes[j];
    for (int j = 0; j < nr_coprimes; j++, nr_rationals++)
      rationals[nr_rationals].numerator_ = i,
        rationals[nr_rationals].denominator_ = coprimes[j];
    for (int j = nr_coprimes - 1; j >= 0; j--, nr_rationals++)
      rationals[nr_rationals].numerator_ = coprimes[j],
        rationals[nr_rationals].denominator_ = i;
    for (int j = 0; j < nr_coprimes; j++, nr_rationals++)
      rationals[nr_rationals].numerator_ = -coprimes[j],
        rationals[nr_rationals].denominator_ = i;
  }
#ifdef DEBUG
  printf("%d\n", nr_rationals);
#endif
  int i;
  while (scanf("%d", &i) != EOF)
    printf("%d / %d\n", rationals[i].numerator_, rationals[i].denominator_);
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0;
}