UVa 10912 - Simple Minded Hashing

Accepted date: 2014-01-15
Ranking (as of 2014-01-15): 257 out of 839
Language: C++

/*
  UVa 10912 - Simple Minded Hashing

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

#include <cstdio>

const int L_max = 26, S_max = 351;
int nsc[L_max + 1][S_max + 1][L_max + 1];
  // nsc[l][s][c] is the number of strings of length l, that maps to s 
  // and has a max value of c
int ns[L_max + 1][S_max + 1];
  // ns[l][s] is the number of strings of length l, that maps to s

int main()
{
  for (int s = 1; s <= L_max; s++)
    nsc[1][s][s] = 1;
  for (int l = 2; l <= L_max; l++)
    for (int s = 1; s <= S_max; s++)
      for (int c = 1; c <= L_max; c++)
        for (int i = 1; i < c; i++)
          nsc[l][s][c] += nsc[l - 1][s - c][i];
  for (int l = 1; l <= L_max; l++)
    for (int s = 1; s <= S_max; s++)
      for (int c = 1; c <= L_max; c++)
        ns[l][s] += nsc[l][s][c];

  for (int c = 1; ; c++) {
    int L, S;
    scanf("%d %d", &L, &S);
    if (!L && !S)
      break;
    printf("Case %d: %d\n", c,
      ((L > 0 && L <= L_max && S > 0 && S <= S_max) ? ns[L][S] : 0));
  }
  return 0;
}

UVa 741 - Burrows Wheeler Decoder

Accepted date: 2014-01-12
Ranking (as of 2014-01-12): 226 out of 585
Language: C++

/*
  UVa 741 - Burrows Wheeler Decoder

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

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

int main()
{
  const int nr_chars_max = 300;
  char d[nr_chars_max + 1], s[nr_chars_max + 1], t[nr_chars_max + 1];
  bool printed = false;
  while (true) {
    int di;
    scanf("%s%d", d, &di);
    if (!strcmp(d, "END") && !di)
      break;
    if (printed)
      putchar('\n');
    di--;
    int length = strlen(d);
    strcpy(s, d);
    sort(s, s + length);
    t[0] = s[di];
#ifdef DEBUG
    printf("%c ", s[di]);
#endif
    int pi;
    for (pi = 0, di--; di >= 0 && s[di] == t[0]; di--)
      pi++;
    for (int ti = 1; ti < length; ti++) {
      for (di = 0; di < length; di++)
        if (d[di] == t[ti - 1]) {
          if (!pi--)
            break;
        }
      t[ti] = s[di];
#ifdef DEBUG
      printf("%c ", s[di]);
#endif
      for (pi = 0, di--; di >= 0 && s[di] == t[ti]; di--)
        pi++;
    }
    t[length] = '\0';
    printed = true;
    printf("%s\n", t);
  }
}

UVa 1260 - Sales

Accepted date: 2014-01-08
Ranking (as of 2014-01-08): 112 out of 600
Language: C++

/*
  UVa 1260 - Sales

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

#include <cstdio>

const int n_max = 1000;

int sales[n_max];

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
      scanf("%d", &sales[i]);
    int c = 0;
    for (int i = 1; i < n; i++)
      for (int j = 0; j < i; j++)
        if (sales[j] <= sales[i])
          c++;
    printf("%d\n", c);
  }
  return 0;
}

UVa 10325 - The Lottery

Accepted date: 2014-01-04
Ranking (as of 2014-01-04): 230 out of 654
Language: C++

/*
  UVa 10325 - The Lottery

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_10325_The_Lottery.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);
}

long long lcm(long long x, long long y)
{
  long long l = x;
  return (l / gcd(x, y)) * y;
}

int main()
{
  const int m_max = 15;
  const int power_of_2s[m_max + 1] = { // power_of_2s[i] is 2^i
    1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768
  };
  int N, M;
  while (scanf("%d %d", &N, &M) != EOF) {
    int numbers[m_max];
    for (int m = 0; m < M; m++)
      scanf("%d", &numbers[m]);
    long long nr = N;
    for (int i = 1; i < power_of_2s[M]; i++) {
      int j = 0, k = 0;
      long long l;
      for (int b = 1; k < M; k++, b <<= 1)
        if (i & b) {
          j++;
          if (j > 1) {
            if ((l = lcm(l, numbers[k])) > N)
              break; // Since N doesn't have factors of l, 
                     // calculating the LCM any further isn't needed.
          }
          else
            l = numbers[k];
        }
      if (k == M) {
        if (j & 1)
          nr -= N / l;
        else
          nr += N / l;
      }
    }
    printf("%lld\n", nr);
  }
  return 0;
}

UVa 10527 - Persistent Numbers

Accepted date: 2014-01-04
Ranking (as of 2014-01-04): 372 out of 638
Language: JAVA

/*
  UVa 10527 - Persistent Numbers
*/

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

class Main {
  static final BigInteger TWO = BigInteger.valueOf(2),
    THREE = BigInteger.valueOf(3),
    FIVE = BigInteger.valueOf(5), SEVEN = BigInteger.valueOf(7);

  public static void main(String[] args) {
    final BigInteger MINUSONE = BigInteger.valueOf(-1);
    int[] numberOfFactors = new int[9 - 0 + 1];
      // numberOfFactors[i] is the number of prime factors for i
      Scanner sc = new Scanner(System.in);
    while (true) {
      BigInteger n = sc.nextBigInteger();
      if (n.equals(MINUSONE))
        break;
      else if (n.equals(BigInteger.ZERO))
        System.out.println("10");
      else if (n.equals(BigInteger.ONE))
        System.out.println("11");
      else if (getNumberOfPrimeFactors(n, numberOfFactors)) {
        StringBuilder sb = new StringBuilder();
        while (true) {
          int d = getNextDidit(numberOfFactors);
          if (d == 0)
            break;
          sb.append((char)(d + '0'));
        }
        if (sb.length() == 1)
          sb.append('1');
        sb.reverse();
        System.out.println(sb);
      }
      else
        System.out.println("There is no such number.");
    }
  }

  static boolean getNumberOfPrimeFactors(BigInteger n, int[] numberOfFactors) {
    numberOfFactors[2] = numberOfFactors[3] =
    numberOfFactors[5] = numberOfFactors[7] = 0;
    while (n.mod(TWO).equals(BigInteger.ZERO)) {
      numberOfFactors[2]++;
      n = n.divide(TWO);
    }
    while (n.mod(THREE).equals(BigInteger.ZERO)) {
      numberOfFactors[3]++;
      n = n.divide(THREE);
    }
    while (n.mod(FIVE).equals(BigInteger.ZERO)) {
      numberOfFactors[5]++;
      n = n.divide(FIVE);
    }
    while (n.mod(SEVEN).equals(BigInteger.ZERO)) {
      numberOfFactors[7]++;
      n = n.divide(SEVEN);
    }
    return n.equals(BigInteger.ONE);
  }

  static int getNextDidit(int[] numberOfFactors) {
    if (numberOfFactors[3] >= 2) {
      numberOfFactors[3] -= 2; return 9;
    }
    else if (numberOfFactors[2] >= 3) {
      numberOfFactors[2] -= 3; return 8;
    }
    else if (numberOfFactors[7] != 0) {
      numberOfFactors[7]--; return 7;
    }
    else if (numberOfFactors[2] != 0 && numberOfFactors[3] != 0) {
      numberOfFactors[2]--; numberOfFactors[3]--; return 6;
    }
    else if (numberOfFactors[5] != 0) {
      numberOfFactors[5]--; return 5;
    }
    else if (numberOfFactors[2] >= 2) {
      numberOfFactors[2] -= 2; return 4;
    }
    else if (numberOfFactors[3] != 0) {
      numberOfFactors[3]--; return 3;
    }
    else if (numberOfFactors[2] != 0) {
      numberOfFactors[2]--; return 2;
    }
    else
      return 0;
  }
}

UVa 10856 - Recover Factorial

Accepted date: 2014-01-03
Ranking (as of 2014-01-03): 235 out of 686
Language: C++

/*
  UVa 10856 - Recover Factorial

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

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

const int n_max = 2703663 /* 10000001 */;
int nr_pfs[n_max + 1];
  // nr_pfs[i] is the nmber of prime factors of i
int total_nr_pfs[n_max + 1];
  // total_nr_pfs[i] is the total number of prime factors up to i

int compare_int(const void* i, const void* j)
{
  return *reinterpret_cast<const int*>(i) - *reinterpret_cast<const int*>(j);
}

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

  for (int tc = 1; ; tc++) {
    int n;
    scanf("%d", &n);
    if (n < 0)
      break;
    printf("Case %d: ", tc);
    int* pi = total_nr_pfs;
    if (n)
      pi = reinterpret_cast<int*>(
        bsearch(&n, total_nr_pfs, n_max + 1, sizeof(int), compare_int));
    if (pi)
      printf("%d!\n", pi - total_nr_pfs);
    else
      puts("Not possible.");
  }
  return 0;
}

UVa 10721 - Bar Codes

Accepted date: 2014-01-02
Ranking (as of 2014-01-02): 598 out of 1156
Language: C++

/*
  UVa 10721 - Bar Codes

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

#include <iostream>
using namespace std;

const int nkm_max = 50;
long long bc[nkm_max + 1][nkm_max + 1][nkm_max + 1];

int main()
{
  int n, k, m;
  for (n = 1; n <= nkm_max; n++)
    for (m = 1; m <= nkm_max; m++)
      if (n <= m)
        bc[n][1][m] = 1;
  for (n = 1; n <= nkm_max; n++)
    bc[n][n][1] = 1;
  for (k = 2; k <= nkm_max; k++)
    for (n = 2; n <= nkm_max; n++)
      for (m = 2; m <= nkm_max; m++)
        if (n >= k && n <= k * m) {
          if (n - k + 1 >= m)
            for (int i = 1; i <= m; i++)
              bc[n][k][m] += bc[n - i][k - 1][m];
          else
            bc[n][k][m] = bc[n][k][m - 1];
        }

  while (cin >> n >> k >> m)
    cout << bc[n][k][m] << endl;
  return 0;
}