UVa 10061 - How many zero's and how many digits ?

Accepted date: 2012-03-03
Ranking (as of 2013-05-25): 217 out of 1024
Language: C++

/*
  UVa 10061 - How many zero's and how many digits ?

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

#include <iostream>
#include <limits>
#include <algorithm>
#include <cmath>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

int how_many_zeros(int n, int b)
{
  int nr_occurrences_max = numeric_limits<int>::max();
  for (int i = 2; i <= b; i++) {
    int nr_occurrences_in_b = 0; // number of occurrences of i in b
    for ( ; !(b % i); b /= i)
      nr_occurrences_in_b++;
    if (!nr_occurrences_in_b)
      continue;
    int nr_occurrences_in_f = 0; // number of occurrences of i in n!
    for (int j = i; j <= n; j *= i)
      nr_occurrences_in_f += n / j;
    nr_occurrences_max =
      min(nr_occurrences_max, nr_occurrences_in_f / nr_occurrences_in_b);
  }
  return nr_occurrences_max;
}

int how_many_digits(int n, int b)
{
  double f = 0.0;
  for (int i = 2; i <= n; i++)
    f += log10(static_cast<double>(i));
  f /= log10(static_cast<double>(b));
  return (f != 0.0) ? static_cast<int>(ceil(f + 1.0e-10)) : 1;
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  int n, b;
  while (cin >> n >> b) {
    if (n == 1)
      cout << 0 << ' ' << 1 << endl;
    else
      cout << how_many_zeros(n, b) << ' ' << how_many_digits(n, b) << endl;
  }
#ifdef __ELAPSED_TIME__
  cerr << "elapsed time = " <<
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC << " sec.\n";
#endif
  return 0;
}

UVa 196 - Spreadsheet

Accepted date: 2012-03-28
Ranking (as of 2013-05-25): 130 out of 771
Language: C++

/*
  UVa 196 - Spreadsheet

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

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <cstdlib>
#include <cctype>
using namespace std;

void topologica_sort(int n, vector<int>& in_degrees,
  const vector< vector<int> >& adjacency_list, vector<int>& cells)
{
  queue<int> q;
  for (int i = 0; i < n; i++)
    if (!in_degrees[i])
      q.push(i);
  while (!q.empty()) {
    int i = q.front(); q.pop();
    const vector<int>& al = adjacency_list[i];
    for (size_t j = 0, e = al.size(); j < e; j++) {
      int k = al[j];
      cells[k] += cells[i];
      if (!--in_degrees[k])
        q.push(k);
    }
  }
}

int main()
{
  const int nr_uppers = 'Z' - 'A' + 1;
  int nr_sheets;
  cin >> nr_sheets;
  while (nr_sheets--) {
    int nr_columns, nr_rows;
    cin >> nr_columns >> nr_rows;
    int n = nr_rows * nr_columns;
    vector<int> cells(n, 0);
    vector<int> in_degrees(n, 0);
    vector< vector<int> > adjacency_list(n, vector<int>());
    for (int i = 0; i < nr_rows; i++)
      for (int j = 0; j < nr_columns; j++) {
        int k = i * nr_columns + j;
        string s;
        cin >> s;
        const char* p = s.c_str();
        if (*p == '=') { // formula
          for (p++; *p; ) {
            int c = 0;
            for ( ; isupper(*p); p++) { // get a column number
              c *= nr_uppers;
              c += *p - 'A' + 1;
            }
            int r = 0;
            for ( ; isdigit(*p); p++) { // get a row number
              r *= 10;
              r += *p - '0';
            }
            in_degrees[k]++;
            adjacency_list[(--r) * nr_columns + (--c)].push_back(k);
            if (*p) // '+'
              p++;
          }
        }
        else // number
          cells[k] = atoi(p);
      }
    topologica_sort(n, in_degrees, adjacency_list, cells);
    for (int i = 0; i < nr_rows; i++)
      for (int j = 0; j < nr_columns; j++) {
        int k = i * nr_columns + j;
        cout << cells[k] << ((j == nr_columns - 1) ? '\n' : ' ');
      }
  }
  return 0;
}

UVa 184 - Laser Lines

Accepted date: 2013-04-29
Ranking (as of 2013-05-25): 92 out of 909
Language: C++

/*
  UVa 184 - Laser Lines

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

#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

struct point {
  int x, y;

  bool operator<(const point& p) const;
};

bool point::operator<(const point& p) const
{
  if (x < p.x)
    return true;
  else if (x > p.x)
    return false;
  else
    return y < p.y;
}

bool collinear(const point& p1, const point& p2, const point& p3)
{
  return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x) == 0;
}

int main()
{
  while (true) {
    point p;
    cin >> p.x >> p.y;
    if (!p.x && !p.y)
      break;
    vector<point> points;
    points.push_back(p);
    while (true) {
      cin >> p.x >> p.y;
      if (!p.x && !p.y)
        break;
      points.push_back(p);
    }
    sort(points.begin(), points.end());
    bool found = false;
    size_t nr_points = points.size();
    vector< pair<size_t, size_t> > lines;
      // pair of indices that form 'longer' lines
    for (size_t i = 0; i < nr_points - 2; i++)
      for (size_t j = i + 1; j < nr_points - 1; j++) {
        int nr_found = 0;
        for (size_t k = 0; k < lines.size(); k++)
          if (collinear(points[lines[k].first], points[lines[k].second], points[i]) &&
            collinear(points[lines[k].first], points[lines[k].second], points[j])) {
            nr_found = -1; break;
          }
        if (nr_found == -1)
          continue;

        for (size_t k = j + 1; k < nr_points; k++) {
          if (collinear(points[i], points[j], points[k])) {
            if (!found) {
              found = true;
              cout << "The following lines were found:\n";
            }
            if (!nr_found)
              cout << setfill(' ') << '(' <<
                setw(4) << points[i].x << ',' <<
                setw(4) << points[i].y << ')' <<
                '(' << setw(4) << points[j].x << ',' <<
                setw(4) << points[j].y << ')';
            cout << '(' << setw(4) << points[k].x <<
              ',' << setw(4) << points[k].y << ')';
            nr_found++;
          }
        }
        if (nr_found) {
          cout << endl;
          if (nr_found > 1)
            lines.push_back(make_pair(i, j));
        }
      }
    if (!found)
      cout <<"No lines were found\n";
  }
  return 0;
}