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