UVa 11105 - Semi-prime H-numbers

Accepted date: 2013-12-28
Ranking (as of 2013-12-28): 121 out of 608
Language: C++

/*
  UVa 11105 - Semi-prime H-numbers

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

#include <iostream>
using namespace std;

const int h_nr_max = 1000001;

int h_numbers[h_nr_max + 1];
  // h_numbers[i] is the number of product of H-numbers
int semi_prime_h_numbers[h_nr_max + 1];
  // semi_prime_h_numbers[i] is the number of semi-prime H-numbers up to i

int main()
{
  for (int i = 5; i <= h_nr_max; i += 4) {
    if (!h_numbers[i])
      h_numbers[i] = 1;
    for (int j = 5; j <= i && i * j <= h_nr_max; j += 4)
      h_numbers[i * j] = h_numbers[i] + h_numbers[j];
  }
#ifdef DEBUG
  int prime_h_numbers = 0;
#endif
  for (int i = 5; i <= h_nr_max; i += 4) {
    semi_prime_h_numbers[i] = semi_prime_h_numbers[i - 4];
    if (h_numbers[i] == 2)
      semi_prime_h_numbers[i]++;
#ifdef DEBUG
    else if (h_numbers[i] == 1)
      prime_h_numbers++;
#endif
  }
#ifdef DEBUG
  cout << prime_h_numbers << ' ' << semi_prime_h_numbers[h_nr_max] << endl;
#endif
  while (true) {
    int h;
    cin >> h;
    if (!h)
      break;
    cout << h << ' ' << semi_prime_h_numbers[h] << endl;
  }
  return 0;
}

UVa 12478 - Hardest Problem Ever (Easy)

Accepted date: 2013-12-27
Language: C++

/*
  UVa 12478 - Hardest Problem Ever (Easy)

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

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

const char* names[] = {
  "RAKIBUL", "ANINDYA", "MOSHIUR", "SHIPLU", "KABIR", "SUNNY", "OBAIDA", "WASI"
};

const int nr_rows = 9, nr_columns = 9;

const char grid[nr_rows][nr_columns] = {
  {'O', 'B', 'I', 'D', 'A', 'I', 'B', 'K', 'R'},
  {'R', 'K', 'A', 'U', 'L', 'H', 'I', 'S', 'P'},
  {'S', 'A', 'D', 'I', 'Y', 'A', 'N', 'N', 'O'},
  {'H', 'E', 'I', 'S', 'A', 'W', 'H', 'I', 'A'},
  {'I', 'R', 'A', 'K', 'I', 'B', 'U', 'L', 'S'},
  {'M', 'F', 'B', 'I', 'N', 'T', 'R', 'N', 'O'},
  {'U', 'T', 'O', 'Y', 'Z', 'I', 'F', 'A', 'H'},
  {'L', 'E', 'B', 'S', 'Y', 'N', 'U', 'N', 'E'},
  {'E', 'M', 'O', 'T', 'I', 'O', 'N', 'A', 'L'}
};

#ifdef DEBUG
bool search_name(const char* name, int length)
{
  for (int r = 0; r < nr_rows; r++)
    for (int c = 0; c <= nr_columns - length; c++) {
      int ci;
      for (ci = 0; ci < length; ci++)
        if (name[ci] != grid[r][c + ci])
          break;
      if (ci == length) {
        printf("  horozontal %d %d: %s\n", r, c, name);
        return true;
      }
    }
  for (int r = 0; r <= nr_rows - length; r++)
    for (int c = 0; c < nr_columns; c++) {
      int ri;
      for (ri = 0; ri < length; ri++)
        if (name[ri] != grid[r + ri][c])
          break;
      if (ri == length) {
        printf(" vertical    %d %d: %s\n", r, c, name);
        return true;
      }
    }
  return false;
}
#endif

int main()
{
#ifdef DEBUG
  for (size_t i = 0; i < sizeof(names) / sizeof(const char*); i++) {
    char name[8];
    strcpy(name, names[i]);
    puts(name);
    int length = strlen(name);
    sort(name, name + length);
    int nr_found = 0;
    do {
      if (search_name(name, length)) {
        if (++nr_found == 2)
          break;
      }
    } while (next_permutation(name, name + length));
/*
    if (nr_found == 2) {
      puts(names[i]);
      break;
    }
*/
  }
#else
  puts(names[4]);
#endif
  return 0;
}

UVa 10482 - The Candyman Can

Accepted date: 2013-12-23
Ranking (as of 2013-12-23): 91 out of 648
Language: C++

/*
  UVa 10482 - The Candyman Can

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

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

const int n_max = 32, weight_max = 20;
const int sum_of_weights_max = n_max * weight_max;

int weights[n_max + 1];
int sum_of_weights[n_max + 1]; // sum of weghts up to i
bool subset_sums[sum_of_weights_max + 1][sum_of_weights_max + 1];
  // subset_sums[a][b] is true if there is a subset of weights 
  // whose sums are a, b

int badness(int s, int a, int b)
{
  int c = s - (a + b);
  return max(max(a, b), c) - min(min(a, b), c);
}

int main()
{
  int t;
  cin >> t;
  for (int c = 1; c <= t; c++) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
      cin >> weights[i];
      sum_of_weights[i] = sum_of_weights[i - 1] + weights[i];
    }
    int s = sum_of_weights[n];
    for (int a = 0; a <= s; a++)
      for (int b = 0; b <= s; b++)
          subset_sums[a][b] = false;
    subset_sums[0][0] = true;
    for (int i = 1; i <= n; i++) {
      int si = sum_of_weights[i], wi = weights[i];
      for (int a = si; a >= 0; a--)
        for (int b = si; b >= 0; b--)
          if (a >= wi && subset_sums[a - wi][b] ||
            b >= wi && subset_sums[a][b - wi])
            subset_sums[a][b] = true;
#ifdef DEBUG
      cout << i << ':';
      for (int a = 0; a <= si; a++)
        for (int b = 0; b <= si; b++)
          if (subset_sums[a][b]) 
            cout << " [" << a << ", " << b << ']';
      cout << endl;
#endif
    }
    int min_badness = s;
    for (int a = 0; a <= s; a++)
      for (int b = 0; b <= s; b++)
        if (subset_sums[a][b])
          min_badness = min(min_badness, badness(s, a, b));
    cout << "Case " << c << ": " << min_badness << endl;
  }
  return 0;
}

UVa 139 - Telephone Tangles

Accepted date: 2013-12-21
Ranking (as of 2013-12-21): 65 out of 592
Language: C++

/*
  UVa 139 - Telephone Tangles

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

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

const int nr_chars_number = 15, nr_chars_locality = 25, nr_chars_max = 1023;

struct telephone_code {
  int code_length_;
  char code_[nr_chars_number + 1];
  char locality_[nr_chars_locality + 1];
  double cost_;
};

int main()
{
  vector<telephone_code> telephone_codes;
  while (true) {
    char s[nr_chars_max + 1];
    gets(s);
    if (!strcmp(s, "000000"))
      break;
    telephone_code tc;
    char* p = strchr(s, ' ');
    *p++ = '\0';
    strcpy(tc.code_, s);
    tc.code_length_ = strlen(tc.code_);
    char *q = strchr(p, '$');
    *q++ = '\0';
    strcpy(tc.locality_, p);
    sscanf(q, "%lf", &tc.cost_);
    tc.cost_ /= 100.0;
    telephone_codes.push_back(tc);
  }
  int nr_tc_codes = static_cast<int>(telephone_codes.size());
  while (true) {
    char number[nr_chars_number + 1];
    scanf("%s", number);
    if (number[0] == '#')
      break;
    int duration;
    scanf("%d", &duration);
    int tci = -1;
    if (number[0] == '0') {
      for (tci = 0; tci < nr_tc_codes; tci++)
        if (!strncmp(number, telephone_codes[tci].code_,
          telephone_codes[tci].code_length_)) {
          int length = strlen(&number[telephone_codes[tci].code_length_]);
          if (length < 4)
            continue;
          if (telephone_codes[tci].code_[1] == '0') { // IDD
            if (length <= 10)
              break;
          }
          else { // STD
            if (length <= 7)
              break;
          }
        }
    }
    if (tci == -1)
      printf("%-15s %-5s%30s%5d%6.2lf%7.2lf\n",
        number, "Local", number, duration, 0.0, 0.0);
    else if (tci < nr_tc_codes)
      printf("%-15s %-25s%10s%5d%6.2lf%7.2lf\n",
        number, telephone_codes[tci].locality_,
        &number[telephone_codes[tci].code_length_], duration,
        telephone_codes[tci].cost_, telephone_codes[tci].cost_ * duration);
    else
      printf("%-15s %-35s%5d%13.2lf\n", number, "Unknown", duration, -1.0);
  }
  return 0;
}

UVa 10819 - Trouble of 13-Dots

Accepted date: 2013-12-19
Ranking (as of 2013-12-19): 93 out of 805
Language: C++

/*
  UVa 10819 - Trouble of 13-Dots

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

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

const int m_max = 10000 + 200, n_max = 100;
int max_favours[m_max + 1];
  // max_favours[i] is the max. total favour valus for the expense of i

int main()
{
  int m, n;
  while (scanf("%d %d", &m, &n) != EOF) {
    int expense = m;
    if (m > 1800) // m + 200 > 2000
      expense += 200;
    memset(max_favours, 0, sizeof(max_favours));
    for (int i = 0; i < n; i++) {
      int p, f;
      scanf("%d %d", &p, &f);
      for (int j = expense; j > p; j--)
        if (max_favours[j - p])
          max_favours[j] = max(max_favours[j], max_favours[j - p] + f);
      max_favours[p] = max(max_favours[p], f);
#ifdef DEBUG
    for (int j = 0; j <= expense; j++)
      if (max_favours[j])
        printf("\t%d %d\n", j, max_favours[j]);
#endif
    }
    int max_f = 0;
    for (int i = 1; i <= expense; i++) {
      if (m <= 2000 && i > m && i <= 2000)
        continue;
      if (max_favours[i] > max_f)
        max_f = max_favours[i];
    }
    printf("%d\n", max_f);
  }
  return 0;
}

UVa 967 - Circular

Accepted date: 2013-12-16
Ranking (as of 2013-12-16): 180 out of 601
Language: C++

/*
  UVa 967 - Circular

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

#include <cstdio>
#include <cmath>

const int n_max = 1000000;
bool not_primes[n_max + 1]; // not_primes[i] is true if i is not a prime
int nr_circular_primes[n_max + 1];
  // nr_circular_primes[i] is the number of circular primes up to i

void sieve_of_eratosthenes()
{
  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;
    }
}

int get_number(int length, int* digits)
{
  int n = 0;
  for (int i = 0; i < length; i++, digits++) {
    if (i)
      n *= 10;
    n += *digits;
  }
  return n;
}

bool is_circular_prime(int n)
{
  if (not_primes[n])
    return false;
  const int nr_digits_max = 8;
  int digits[nr_digits_max * 2];
  int length;
  for (length = 1; ; length++) {
    digits[nr_digits_max - length] = n % 10;
    n /= 10;
    if (!n)
      break;
  }
  for (int i = nr_digits_max - length, j = nr_digits_max, k = length - 1;
    k; k--) {
    digits[j++] = digits[i++];
    if (not_primes[get_number(length, &digits[i])])
      return false;
  }
  return true;
}

int main()
{
  sieve_of_eratosthenes();
  int nr = 0;
  for (int n = 100; n <= n_max; n++) {
    if (is_circular_prime(n))
      nr++;
    nr_circular_primes[n] = nr;
  }
  while (true) {
    int i, j;
    scanf("%d", &i);
    if (i == -1)
      break;
    scanf("%d", &j);
    nr = nr_circular_primes[j] - nr_circular_primes[i - 1];
    if (!nr)
      puts("No Circular Primes.");
    else if (nr == 1)
      puts("1 Circular Prime.");
    else
      printf("%d Circular Primes.\n", nr);
  }
  return 0;
}

UVa 944 - Happy Numbers

Accepted date: 2013-12-15
Ranking (as of 2013-12-15): 62 out of 603
Language: C++

/*
  UVa 944 - Happy Numbers

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

#include <cstdio>
#include <cstring>

const int n_max = 99999, sum_of_squares_max = 405;

enum {unknown, happy, unhappy};

struct happy_number {
  int happy_; // 0 for unknown, 1 for happy, 2 for unhappy
  int nr_iterations_;
} happy_numbers[n_max + 1];

int sum_of_squares[sum_of_squares_max + 1];
  // sum_of_squares[i] is the number whose sum of squares is i

int calculate_sum_of_squares(int n)
{
  int d, s = 0;
  do {
    d = n % 10;
    s += d * d;
    n /= 10;
  } while (n);
  return s;
}

void set_happy_numbers(int number, int nr_iterations)
{
  do {
    happy_numbers[number].happy_ = happy;
    happy_numbers[number].nr_iterations_ = nr_iterations++;
    number = sum_of_squares[number];
  } while (number != -1);
}

void set_unhappy_numbers(int number)
{
  do {
    happy_numbers[number].happy_ = unhappy;
    number = sum_of_squares[number];
  } while (number != -1);
}

int main()
{
  int n;
  for (n = 1; n <= sum_of_squares_max; n++) {
    if (happy_numbers[n].happy_ == unknown) {
      int m = n;
      memset(sum_of_squares, 0, sizeof(sum_of_squares));
      sum_of_squares[m] = -1;
      while (true) {
        int s = calculate_sum_of_squares(m);
        if (s == 1 || happy_numbers[s].happy_ == happy) {
          set_happy_numbers(m, happy_numbers[s].nr_iterations_ + 1);
          break;
        }
        else if (sum_of_squares[s] || happy_numbers[s].happy_ == unhappy) {
          set_unhappy_numbers(m);
          break;
        }
        sum_of_squares[s] = m;
        m = s;
      }
    }
#ifdef DEBUG
    if (happy_numbers[n].happy_ == happy)
      printf("%d %d\n", n, happy_numbers[n].nr_iterations_);
#endif
  }
  for ( ; n <= n_max; n++) {
    int s = calculate_sum_of_squares(n);
    if (happy_numbers[s].happy_ == happy) {
      happy_numbers[n].happy_ = happy;
      happy_numbers[n].nr_iterations_ = happy_numbers[s].nr_iterations_ + 1;
#ifdef DEBUG
      printf("%d %d\n", n, happy_numbers[n].nr_iterations_);
#endif
    }
    else
      happy_numbers[n].happy_ = unhappy;
  }
  bool printed = false;
  int l, h;
  while (scanf("%d %d", &l, &h) != EOF) {
    if (printed)
      putchar('\n');
    else
      printed = true;
    for (n = l; n <= h; n++)
      if (happy_numbers[n].happy_ == happy)
        printf("%d %d\n", n, happy_numbers[n].nr_iterations_);
  }
  return 0;
}

UVa 11678 - Cards' Exchange

Accepted date: 2013-12-03
Ranking (as of 2013-12-03): 66 out of 606
Language: C++

/*
  UVa 11678 - Cards' Exchange

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

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

const int nr_cards_max = 10000;
int alice_cards[nr_cards_max], betty_cards[nr_cards_max];

int skip_cards(int nc, int ic, const int cards[])
{
  int c = cards[ic++];
  for ( ; ic < nc; ic++)
    if (cards[ic] != c)
        break;
  return ic;
}

int main()
{
  while (true) {
    int na, nb;
    scanf("%d %d", &na, &nb);
    if (!na & !nb)
      break;
    for (int i = 0; i < na; i++)
      scanf("%d", &alice_cards[i]);
    for (int i = 0; i < nb; i++)
      scanf("%d", &betty_cards[i]);
    int xa = 0, xb = 0;
    for (int ia = 0, ib = 0; ia < na || ib < nb; ) {
      if (ia < na && ib < nb) {
        if (alice_cards[ia] < betty_cards[ib]) {
          xa++;
          ia = skip_cards(na, ia, alice_cards);
        }
        else if (alice_cards[ia] > betty_cards[ib]) {
          xb++;
          ib = skip_cards(nb, ib, betty_cards);
        }
        else {
          ia = skip_cards(na, ia, alice_cards);
          ib = skip_cards(nb, ib, betty_cards);
        }
      }
      else if (ia < na) {
        xa++;
        ia = skip_cards(na, ia, alice_cards);
      }
      else {
        xb++;
        ib = skip_cards(nb, ib, betty_cards);
      }
    }
    printf("%d\n", min(xa, xb));
  }
  return 0;
}

UVa 11258 - String Partition

Accepted date: 2013-12-02
Ranking (as of 2013-12-03): 219 out of 630
Language: C++

/*
  UVa 11258 - String Partition

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

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

const int nr_digits_max = 200;
#ifdef ONLINE_JUDGE
long long max_sum[nr_digits_max];
  // max_s[i] is the max. sum of digits up to i
#else
long long max_sum[nr_digits_max][nr_digits_max];
  // max_s[i][j] is the max. sum of digits bewteen i-th and j-th
#endif

int get_integer(const char s[], int si, int sj)
{
  long long i = s[si++] - '0';
  for ( ; si <= sj; si++) {
    i *= 10;
    i += s[si] - '0';
    if (i > INT_MAX)
      return -1;
  }
  return i;
}

int main()
{
  int n;
  scanf("%d", &n);
  while (n--) {
    char digits[nr_digits_max + 1];
    scanf("%s", digits);
    int n = strlen(digits);
#if ONLINE_JUDGE
    max_sum[0] = digits[0] - '0';
    for (int i = 1; i < n; i++) {
      long long max_s = get_integer(digits, 0, i);
      for (int j = 1; j <= 10 && j <= i; j++) {
        int k = get_integer(digits, i - j + 1, i);
        if (k != -1)
          max_s = max(max_s, max_sum[i - j] + k);
      }
      max_sum[i] = max_s;
    }
    printf("%lld\n", max_sum[n - 1]);
#else
    for (int i = 0; i < n; i++)
      max_sum[i][i] = digits[i] - '0';
    for (int k = 0; k < n; k++)
      for (int i = 0; i < n - k; i++) {
        long long max_s = get_integer(digits, i, i + k);
        for (int j = i; j < i + k; j++)
          max_s = max(max_s, max_sum[i][j] + max_sum[j + 1][i + k]);
        max_sum[i][i + k] = max_s;
      }
#ifdef DEBUG
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
      printf("%lld%c", max_sum[i][j], ((j < n - 1) ? ' ' : '\n'));
#endif
    printf("%lld\n", max_sum[0][n - 1]);
#endif
  }
  return 0;
}