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