UVa 11526 - H(n)

Accepted date: 2013-02-04
Ranking (as of 2013-02-05): 121
Language: C++

/*
  UVa 11526 - H(n)

  To build using Visual Studio 2008:
    cl -EHsc -O2 UVa_11526_Hn.cpp
*/

#include <cstdio>
#include <cmath>

long long H(int n)
{
  if (n < 0)
    return 0;
  if (n == 1)
    return 1;
  long long result = n;
  int cur_divisor = 2, cur_quoitent, prev_divisor = 1, prev_quoitent = n;
  while (true) {
    cur_quoitent = n / cur_divisor;
    result +=
      static_cast<long long>(prev_quoitent - cur_quoitent) * prev_divisor;
    if (cur_quoitent >= cur_divisor)
      result += cur_quoitent;
    if (cur_quoitent <= cur_divisor)
      break;
    prev_divisor = cur_divisor++;
    prev_quoitent = cur_quoitent;
  }
  return result;
}

int main()
{
  int t;
  scanf("%d",& t);
  while (t--) {
    int n;
    scanf("%d", &n);
    printf("%lld\n", H(n));
  }
  return 0;
}

UVa 10908 - Largest Square

Accepted date: 2013-02-04
Ranking (as of 2013-02-05): 165
Language: C++

/*
  UVa 10908 - Largest Square

  To build using Visual Studio 2008:
    cl -EHsc -O2 UVa_10908_Largest_Square.cpp
*/

#include <cstdio>

const int n_max = 100, m_max = 100;
char grid[n_max][m_max + 1];

int largest_square(int m, int n, int r, int c)
{
  if (r < 0 || r >= m || c < 0 || c >= n)
    return 0;
  char sc = grid[r][c];
  int s;
  for (s = 3; ; s += 2) {
    int i_min = r - s / 2, i_max = r + s / 2,
      j_min = c - s / 2, j_max = c + s / 2;
    if (i_min < 0 || i_max >= m || j_min < 0 || j_max >= n)
      break;
    for (int j = j_min; j <= j_max; j++)
      if (grid[i_min][j] != sc || grid[i_max][j] != sc)
        goto done;
    for (int i = i_min + 1; i < i_max; i++)
      if (grid[i][j_min] != sc || grid[i][j_max] != sc)
        goto done;
  }
done:
  return s - 2;
}

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int m, n, q;
    scanf("%d %d %d", &m, &n, &q);
    getchar();
    for (int i = 0; i < m; i++)
      gets(grid[i]);
    printf("%d %d %d\n", m, n, q);
    while (q--) {
      int r, c;
      scanf("%d %d", &r, &c);
      printf("%d\n", largest_square(m, n, r, c));
    }
  }
  return 0;
}

UVa 10533 - Digit Primes

Accepted date: 2012-08-29
Ranking (as of 2013-02-02): 137
Language: C++

/*
  UVa 10533 - Digit Primes

  To build using Visual Studio 2008:
    cl -EHsc -O2 digit_primes.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_digit_primes[n_max + 1];
  // nr_digit_primes[i] is the number of digit primes between 1 and i

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

int sum_of_digits(int n)
{
  int s = 0;
  for ( ; n; n /= 10)
    s += n % 10;
  return s;
}

int main()
{
  sieve_of_eratosthenes();
  int nr = 1;
  nr_digit_primes[2] = nr;
  for (int i = 3; i <= n_max; i += 2) {
    if (!not_primes[i] && !not_primes[sum_of_digits(i)])
      nr++;
    nr_digit_primes[i] = nr_digit_primes[i + 1] = nr;
  }
  int n;
  scanf("%d", &n);
  while (n--) {
    int t1, t2;
    scanf("%d %d", &t1, &t2);
    printf("%d\n", nr_digit_primes[t2] - nr_digit_primes[t1 - 1]);
  }
  return 0;
}

UVa 10611 - The Playboy Chimp

Accepted date: 2012-09-04
Ranking (as of 2013-02-02): 215
Language: C++

/*
  UVa 10611 - The Playboy Chimp

  To build using Visucal Studio 2008:
    cl -EHsc -O2 the_playboy_chimp.cpp
*/

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

const int n_max = 50000;
int heights[n_max];

int main()
{
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; i++)
    scanf("%d", &heights[i]);
  int q;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int h;
    scanf("%d", &h);
    int li = distance(heights, lower_bound(heights, heights + n, h));
    if (li < n) {
      while (li >= 0 && heights[li] >= h)
        li--;
    }
    else
      li = n - 1;
    if (li >= 0)
      printf("%d ", heights[li]);
    else
      printf("X ");
    int hi = distance(heights, upper_bound(heights, heights + n, h));
    if (hi < n)
      printf("%d\n", heights[hi]);
    else
      printf("X\n");
  }
  return 0;
}

UVa 498 - Polly the Polynomial

Accepted date: 2012-09-08
Ranking (as of 2013-02-02): 316
Language: C++

/*
  UVa 498 - Polly the Polynomial

  To build using Visucal Studio 2008:
    cl -EHsc -O2 polly_the_polynomial.cpp
*/

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

int main()
{
  string line;
  istringstream iss;
  while (getline(cin, line)) {
    vector<long long> coefficients;
    iss.str(line);
    long long c;
    while (iss >> c)
      coefficients.push_back(c);
    iss.clear();
    int n = coefficients.size();
    getline(cin, line);
    iss.str(line);
    long long x;
    bool printed = false;
    while (iss >> x) {
      long long s = coefficients[0];
      for (int i = 1; i < n; i++) {
        s *= x;
        s += coefficients[i];
      }
      if (printed)
        cout << ' ';
      else
        printed = true;
      cout << s;
    }
    cout << endl;
    iss.clear();
  }
  return 0;
}

UVa 271 - Simply Syntax

Accepted date: 2012-09-08
Ranking (as of 2013-02-02): 76
Language: C++

/*
  UVa 271 - Simply Syntax

  To build using Visucal Studio 2008:
    cl -EHsc -O2 simply_syntax.cpp
*/

#include <cstdio>
#include <cstring>

int get_sentence(const char* s, int i, int length)
{
  if (i >= length)
    return -1;
  char c = s[i];
  if (c == 'N') {
    int j = get_sentence(s, i + 1, length);
    return (j == -1) ? j : j + 1;
  }
  else if (c == 'C' || c == 'D' || c == 'E' || c == 'I') {
    int j = get_sentence(s, i + 1, length);
    if (j == -1)
      return -1;
    int k = get_sentence(s, i + j + 1, length);
    return (k == -1) ? -1 : j + k + 1;
  }
  else
    return 1;
}

int main()
{
  const int nr_chars_max = 256;
  char s[nr_chars_max + 1];
  while (gets(s)) {
    int length = strlen(s);
    printf("%s\n", ((get_sentence(s, 0, length) == length) ? "YES" : "NO"));
  }
  return 0;
}

UVa 11057 - Exact Sum

Accepted date: 2012-09-21
Ranking (as of 2013-02-02): 303
Language: C++

/*
  UVa 11057 - Exact Sum

  To build using Visual Studio 2008:
    cl -EHsc -O2 exact_sum.cpp
*/

#include <cstdio>
#include <cstdlib>

const int n_max = 10000;
int prices[n_max];

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

int main()
{
  int n;
  while (scanf("%d", &n) != EOF) {
    for (int i = 0; i < n; i++)
      scanf("%d", &prices[i]);
    int m;
    scanf("%d", &m);
    qsort(prices, n, sizeof(int), compare_price);
    int pi, pj;
    for (int i = 0; i < n - 1; i++) {
      int p = m - prices[i];
      if (p < prices[i])
        break;
      int* pp = reinterpret_cast<int*>(
        bsearch(&p, &prices[i + 1], n - (i + 1), sizeof(int), compare_price));
      if (pp) {
        pi = i; pj = pp - prices;
      }
    }
    printf("Peter should buy books whose prices are %d and %d.\n\n",
      prices[pi], prices[pj]);
  }
  return 0;
}

UVa 739 - Soundex Indexing

Accepted date: 2012-09-25
Ranking (as of 2013-02-02): 56
Language: C++

/*
  UVa 739 - Soundex Indexing

  To build using Visual Studio 2008:
    cl -EHsc -O2 soundex_indexing.cpp
*/

#include <cstdio>

char soundex_code(char c)
{
  char cc = 0;
  switch (c) {
  case 'B': case 'P': case 'F': case 'V':
    cc = '1'; break;
  case 'C': case 'S': case 'K': case'G': case 'J': case 'Q': case 'X': case 'Z':
    cc = '2'; break;
  case 'D': case 'T':
    cc = '3'; break;
  case 'L':
    cc = '4'; break;
  case 'M': case 'N':
    cc = '5'; break;
  case 'R':
    cc = '6'; break;
  default:
    break;
  }
  return cc;
}

int main()
{
  printf("         NAME                     SOUNDEX CODE\n");
  const int nr_chars_max = 20, nr_coded_length = 4;
  char name[nr_chars_max + 1], code[nr_chars_max + 1];
  while (scanf("%s", name) != EOF) {
    const char* p = name;
    char pcc = soundex_code(*p);
    int coded_length = 0;
    code[coded_length++] = *p++;
    for ( ; *p; *p++) {
      char cc = soundex_code(*p);
      if (cc && cc != pcc)
        code[coded_length++] = cc;
      pcc = cc;
    }
    while (coded_length < nr_coded_length)
      code[coded_length++] = '0';
    code[nr_coded_length] = '\0';
    printf("         %-25s%s\n", name, code);
  }
  printf("                   END OF OUTPUT\n");
  return 0;
}

UVa 10001 - Garden of Eden

Accepted date: 2011-03-03
Ranking (as of 2013-01-27): 152
Language: C++

Backtrack without explicit pruning.

/*
  8.6.6 Garden of Eden
  PC/UVa IDs: 110806/10001, Popularity: B, Success rate: average Level: 2

  To build using Visucal Studio 2008:
    cl -EHsc garden_of_eden.cpp
*/

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

#ifdef DEBUG
void print_cr(int li, int lcr)
{
  for (int i = 0; i < li; i++)
    cout << "  ";
  for (int i = 1; i >= 0; i--)
    cout << ((lcr & (1 << i)) ? '1' : '0');
  cout << endl;
}
#endif

bool find_ancestor(int n /* number of bits in the lattice */,
  int li /* lattice index */, unsigned int lattice,
  int identifier, int fcr /* cell and right bits of the first cell */,
  int plc /* left and cell bits of the previous cell */)
{
  int id = (lattice & (static_cast<unsigned int>(1) << li))
    /* the value of current cell is 1 */ ?
    identifier : ~identifier;
  for (int i = 0; i < 4; i++, id >>= 2)
    if (id & 3) {
      int lc_0 = -1, lc_1 = -1;
        // left, cell, and right bits whose new state is equal 
        // to the current value
      if (id & 1)
        lc_0 = i * 2;
      if (id & 2)
        lc_1 = i * 2 + 1;
      if (!li) { // for the first cell
#ifdef DEBUG
        print_cr(li, i);
#endif
        // pass the cell and right bits of the first cell
        if (id & 1 &&
          find_ancestor(n, li + 1, lattice, identifier, lc_0 & 3, i) ||
          id & 2 &&
          find_ancestor(n, li + 1, lattice, identifier, lc_1 & 3, i))
          return true;
      }
      else if (li == n - 1) { // for the last cell
#ifdef DEBUG
        print_cr(li, i);
#endif
        if (lc_0 != -1 && (lc_0 >> 1) == fcr &&
          (lc_0 & 3) == plc ||
          lc_1 != -1 && (lc_1 >> 1) == fcr && (lc_1 & 3) == plc)
          return true;
      }
      else if (lc_0 != -1 && (lc_0 & 3) == plc ||
        lc_1 != -1 && (lc_1 & 3) == plc) {
#ifdef DEBUG
        print_cr(li, i);
#endif
        if (find_ancestor(n, li + 1, lattice, identifier, fcr, i))
          // cell and right bits of the current cell are equal 
          // to the left ant cell bits of the previous cell
          return true;
      }
    }
  return false;
}

int main(int /* argc */, char** /* argv */)
{
  int identifier, n;
  string s;
  while (cin >> identifier >> n >> s) {
    unsigned int lattice = 0;
      // for the 32-bit unsigned int, the value of the i-th cell 
      // (i >= 0) is stored in i-th bit
    for (int i = 0; i < n; i++)
      if (s[i] == '1')
        lattice |= static_cast<unsigned int>(1) << (n - i - 1);
    cout << ((find_ancestor(n, 0, lattice, identifier, -1, -1)) ?
      "REACHABLE\n" : "GARDEN OF EDEN\n");
  }
  return 0;
}