UVa 12955 - Factorial

Accepted date: 2019-04-15
Run Time: 0.000
Ranking (as of 2019-04-16): 344 out of 415
Language: C++

/*
  UVa 12955 - Factorial

  To build using Visual Studio 2015:
    cl -EHsc -O2 UVa_12955_Factorial.cpp
*/

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

const int N_max = 100000, nr_factorials = 8;
const int factorials[nr_factorials] = {40320, 5040, 720, 120, 24, 6, 2, 1}; 
int min_nr_sums;

void sum_of_factorials(int n, int nr_sums)
{
  if (!n) {
    min_nr_sums = min(min_nr_sums, nr_sums);
    return;
  }
  if (n + nr_sums <= min_nr_sums) {
    for (int i = 0; i < nr_factorials; i++)
      if (n >= factorials[i])
        sum_of_factorials(n - factorials[i], nr_sums + 1);
  }
}

int main()
{
  int N;
  while (scanf("%d", &N) != EOF) {
    min_nr_sums = N;
    sum_of_factorials(N, 0);
    printf("%d\n", min_nr_sums);
  }
  return 0;
}

UVa 211 - The Domino Effect

Accepted date: 2019-04-14
Run Time: 0.110
Ranking (as of 2019-04-14): 243 out of 557
Language: C++

/*
  UVa 211 - The Domino Effect

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

#include <cstdio>
#include <cstring>

const int nr_bones = 28, nr_rows = 7, nr_cols = 8;

const int bones[nr_bones][2] = {
  {0, 0}, {0, 1}, {0, 2}, {0, 3}, {0, 4}, {0, 5}, {0, 6},
  {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6},
  {2, 2}, {2, 3}, {2, 4}, {2, 5}, {2, 6},
  {3, 3}, {3, 4}, {3, 5}, {3, 6},
  {4, 4}, {4, 5}, {4, 6},
  {5, 5}, {5, 6},
  {6, 6}
};

int grid[nr_rows][nr_cols], nr_maps, map[nr_rows][nr_cols];

void print_grid_or_map(int grid_or_map[nr_rows][nr_cols])
{
  for (int i = 0; i < nr_rows; i++) {
    for (int j = 0; j < nr_cols; j++)
      printf("%4d", grid_or_map[i][j]);
    putchar('\n');
  }
  putchar('\n');
}

void domino_effect(int bi)
{
  if (bi == nr_bones) {
    nr_maps++;
    print_grid_or_map(map);
    return;
  }
  int pf = bones[bi][0], ps = bones[bi][1], bn = bi + 1;
  for (int i = 0; i < nr_rows; i++)
    for (int j = 0; j < nr_cols; j++) {
      if (j < nr_cols - 1 && !map[i][j] && !map[i][j + 1] &&
        (grid[i][j] == pf && grid[i][j + 1] == ps || grid[i][j] == ps && grid[i][j + 1] == pf)) {
        map[i][j] = map[i][j + 1] = bn;
        domino_effect(bi + 1);
        map[i][j] = map[i][j + 1] = 0;
      }
      if (i < nr_rows - 1 && !map[i][j] && !map[i + 1][j] &&
        (grid[i][j] == pf && grid[i + 1][j] == ps || grid[i][j] == ps && grid[i + 1][j] == pf)) {
        map[i][j] = map[i + 1][j] = bn;
        domino_effect(bi + 1);
        map[i][j] = map[i + 1][j] = 0;
      }
    }
}

int main()
{
  for (int ln = 1; ; ln++) {
    if (scanf("%d", &grid[0][0]) == EOF)
      break;
    for (int j = 1; j < nr_cols; j++)
      scanf("%d", &grid[0][j]);
    for (int i = 1; i < nr_rows; i++)
      for (int j = 0; j < nr_cols; j++)
        scanf("%d", &grid[i][j]);
    if (ln > 1)
      printf("\n\n\n");
    printf("Layout #%d:\n\n", ln);
    print_grid_or_map(grid);
    printf("Maps resulting from layout #%d are:\n\n", ln);
    nr_maps = 0;
    memset(map, 0, sizeof(map));
    domino_effect(0);
    printf("There are %d solution(s) for layout #%d.\n", nr_maps, ln);
  }
  return 0;
}

UVa 12412 - A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)

Accepted date: 2019-04-10
Run Time: 0.000
Ranking (as of 2019-04-10): 310 out of 425
Language: C++11

/*
  UVa 12412 - A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)

  To build using Visual Studio 2015:
    cl -EHsc -O2 UVa_12412_A_Typical_Homework.cpp
*/

#include <vector>
#include <map>
#include <functional>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

const int sid_chrs = 10, max_cid = 20, max_name_chrs = 10, nr_scores = 4;
const double eps = 1.0e-5;

struct student {
  long long sid;
  int cid;
  char name[max_name_chrs + 1];
  int scores[nr_scores];
  int total, nr_passed;
};

vector<student> students;

struct score {
  int total;
  int nr, nr_passed, nr_failed;
};

struct statistic {
  int overall[nr_scores + 1]; // overall[i] is the number of students who passed i subjects
  score scores[nr_scores];
} statistics[max_cid + 1];

statistic& whole_statistic = statistics[0];

multimap<int, int, greater<int>> total_scores; // key is a total score, value is an index to students[]

void add_students()
{
  while (true) {
    puts("Please enter the SID, CID, name and four scores. Enter 0 to finish.");
    char ssid[sid_chrs + 1];
    scanf("%s", ssid);
    if (!strcmp(ssid, "0"))
      return;
    student s;
    s.sid = strtoll(ssid, nullptr, 10);
    scanf("%d %s %d %d %d %d", &s.cid, s.name, &s.scores[0], &s.scores[1], &s.scores[2], &s.scores[3]);
    size_t i, n = students.size();
    for (i = 0; i < n; i++)
      if (s.sid == students[i].sid)
        break;
    if (i < n) {
      puts("Duplicated SID.");
      continue;
    }
    s.total = 0, s.nr_passed = 0;
    statistic& st = statistics[s.cid];
    for (int i = 0; i < nr_scores; i++) {
      s.total += s.scores[i], st.scores[i].total += s.scores[i], st.scores[i].nr++,
        whole_statistic.scores[i].total += s.scores[i], whole_statistic.scores[i].nr++;;
      if (s.scores[i] >= 60)
        s.nr_passed++, st.scores[i].nr_passed++, whole_statistic.scores[i].nr_passed++;
      else
        st.scores[i].nr_failed++, whole_statistic.scores[i].nr_failed++;
    }
    st.overall[s.nr_passed]++, whole_statistic.overall[s.nr_passed]++;
    students.push_back(s);
    total_scores.insert(make_pair(s.total, n));
  }
}

void remove_student(int si)
{
  student& s = students[si];
  statistic& st = statistics[s.cid];
  for (int i = 0; i < nr_scores; i++) {
    st.scores[i].total -= s.scores[i], st.scores[i].nr--,
      whole_statistic.scores[i].total -= s.scores[i], whole_statistic.scores[i].nr--;
    if (s.scores[i] >= 60)
      st.scores[i].nr_passed--, whole_statistic.scores[i].nr_passed--;
    else
      st.scores[i].nr_failed--, whole_statistic.scores[i].nr_failed--;
  }
  st.overall[s.nr_passed]--, whole_statistic.overall[s.nr_passed]--;
  for (auto j = total_scores.begin(); j != total_scores.end(); ) {
    if (j->second == si)
      total_scores.erase(j++);
    else {
      if (j->second > si)
        j->second--;
      ++j;
    }
  }
}

void remove_students()
{
  while (true) {
    puts("Please enter SID or name. Enter 0 to finish.");
    char sid_or_name[sid_chrs + 1];
    scanf("%s", sid_or_name);
    if (!strcmp(sid_or_name, "0"))
      return;
    int nr_removed = 0;
    if (isdigit(sid_or_name[0])) { // sid
      long long sid = strtoll(sid_or_name, nullptr, 10);
      for (auto i = students.begin(); i != students.end(); ) {
        if (i->sid == sid) {
          remove_student(i - students.begin());
          students.erase(i);
          nr_removed++;
          break;
        }
        else
          ++i;
      }
    }
    else { // name
      for (auto i = students.begin(); i != students.end(); ) {
        if (!strcmp(i->name, sid_or_name)) {
          remove_student(i - students.begin());
          students.erase(i);
          nr_removed++;
        }
        else
          ++i;
      }
    }
    printf("%d student(s) removed.\n", nr_removed);
  }
}

void query_student(int si, int rank)
{
  const student& s = students[si];
  printf("%d %010lld %d %s %d %d %d %d %d %.2lf\n",
    rank, s.sid, s.cid, s.name, s.scores[0], s.scores[1], s.scores[2], s.scores[3],
    s.total, s.total / 4.0 + eps);
}

void query_students()
{
  map<int, int> ranks; // key is an index to students[], value is the rank

  int n = 0, rank = 0, score = -1;
  for (auto i = total_scores.cbegin(); i != total_scores.cend(); i++) {
    n++;
    if (i->first != score) {
      rank = n;
      score = i->first;
    }
    ranks.insert(make_pair(i->second, rank));
  }
  while (true) {
    puts("Please enter SID or name. Enter 0 to finish.");
    char sid_or_name[sid_chrs + 1];
    scanf("%s", sid_or_name);
    if (!strcmp(sid_or_name, "0"))
      return;
    if (isdigit(sid_or_name[0])) { // sid
      long long sid = strtoll(sid_or_name, nullptr, 10);
      for (size_t i = 0, n = students.size(); i < n; i++)
        if (students[i].sid == sid) {
          query_student(i, ranks[i]);
          break;
        }
    }
    else { // name
      for (size_t i = 0, n = students.size(); i < n; i++)
        if (!strcmp(students[i].name, sid_or_name))
          query_student(i, ranks[i]);
    }
  }
}

void show_statistics(void)
{
  const char* courses[nr_scores] = {"Chinese", "Mathematics", "English", "Programming"};
  puts("Please enter class ID, 0 for the whole statistics.");
  int cid;
  scanf("%d", &cid);
  statistic& st = statistics[cid];
  for (int i = 0; i < nr_scores; i++) {
    const score& sc = st.scores[i];
    printf("%s\n", courses[i]);
    printf("Average Score: %.2lf\n", ((sc.nr) ? static_cast<double>(sc.total) / sc.nr : 0.0) + eps);
    printf("Number of passed students: %d\n", sc.nr_passed);
    printf("Number of failed students: %d\n\n", sc.nr_failed);
  }
  int overall = st.overall[4];
  printf("Overall:\nNumber of students who passed all subjects: %d\n", overall);
  overall += st.overall[3];
  printf("Number of students who passed 3 or more subjects: %d\n", overall);
  overall += st.overall[2];
  printf("Number of students who passed 2 or more subjects: %d\n", overall);
  overall += st.overall[1];
  printf("Number of students who passed 1 or more subjects: %d\n", overall);
  printf("Number of students who failed all subjects: %d\n\n", st.overall[0]);
}

#ifdef DEBUG
void print_students()
{
  for (size_t i = 0, n = students.size(); i < n; i++) {
    const student& s = students[i];
    if (s.sid != -1)
      printf("%d: %010lld %d %s %d %d %d %d %d %.2lf\n",
        i, s.sid, s.cid, s.name, s.scores[0], s.scores[1], s.scores[2], s.scores[3],
        s.total, s.total / 4.0 + eps);
  }
  for (auto j = total_scores.cbegin(); j != total_scores.cend(); ++j)
    printf("%d %d\n", j->first, j->second);
}
#endif

int main()
{
  while (true) {
    puts("Welcome to Student Performance Management System (SPMS).\n\n"
      "1 - Add\n2 - Remove\n3 - Query\n4 - Show ranking\n5 - Show Statistics\n0 - Exit\n");
    int c, sc;
    scanf("%d", &c);
    switch (c) {
    case 0:
      break;
    case 1:
      add_students();
#ifdef DEBUG
      print_students();
#endif
      break;
    case 2:
      remove_students();
#ifdef DEBUG
      print_students();
#endif
      break;
    case 3:
      query_students();
      break;
    case 4:
      puts("Showing the ranklist hurts students' self-esteem. Don't do that.");
      break;
    case 5:
      show_statistics();
      break;
    }
    if (!c)
      break;
  }
  return 0;
}

UVa 11291 - Smeech

Accepted date: 2018-06-17
Run Time: 0.000
Ranking (as of 2018-06-17): 186 out of 391
Language: C++

/*
  UVa 11291 - Smeech

  To build using Visual Studio 2015:
    cl -EHsc -O2 UVa_11291_Smeech.cpp
*/

#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

double smeech(char* ss, char** se)
{
  while (isspace(*ss))
    ss++;
  if (*ss == '(') {
    ss++;
    double p = strtod(ss, se);
    ss = *se;
    double e1 = smeech(ss, se);
    ss = *se;
    double e2 = smeech(ss, se);
    ss = *se;
    while (*ss != ')')
      ss++;
    *se = ss + 1;
    return p * (e1 + e2) + (1.0 - p) * (e1 - e2);
  }
  else
    return strtod(ss, se);
}

int main()
{
  while (true) {
    string s;
    getline(cin, s);
    if (s == "()")
      break;
    char* ss = new char[s.length() + 1];
    strcpy(ss, s.c_str());
    char* se;
    printf("%.2lf\n", smeech(ss, &se));
    delete[] ss;
  }
  return 0;
}

UVa 822 - Queue and A

Accepted date: 2018-02-11
Run Time: 0.310
Ranking (as of 2018-02-11): 141 out of 199
Language: C++

/*
  UVa 822 - Queue and A

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

#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <limits>
#include <cstdio>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif
using namespace std;

const int infinite = numeric_limits<int>::max();
const int nr_topics_max = 20, nr_personnel_max = 5;

struct person {
  int id_, nr_topics_;
  int t_last_start_, t_last_end_;
  int topics_[nr_topics_max];
} persons[nr_personnel_max];

struct person_comparator
{
  bool operator() (int i, int j) const
  {
    const person& pi = persons[i];
    const person& pj = persons[j];
    if (pi.t_last_start_ > pj.t_last_start_)
      return true;
    else if (pi.t_last_start_ < pj.t_last_start_)
      return false;
    else
      return i > j;
  }
};

struct topic {
  int nr_reqs_, t_first_req_, t_service_req_, t_between_reqs_;
  int t_arrived_;
  priority_queue<int, vector<int>, person_comparator> persons_;
    // candidate persons to handle a request

  topic() {}
  topic(int nr_reqs, int t_first_req, int t_service_req, int t_between_reqs) :
    nr_reqs_(nr_reqs), t_first_req_(t_first_req), t_service_req_(t_service_req),
    t_between_reqs_(t_between_reqs), t_arrived_(t_first_req_) {}
};

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  for (int scn = 1; ; scn++) {
    int nr_topics;
    scanf("%d", &nr_topics);
    if (!nr_topics)
      break;
    map<int, topic> topics;
    while (nr_topics--) {
      int id, nr_reqs, t_first_req, t_service_req, t_between_reqs;
      scanf("%d %d %d %d %d", &id, &nr_reqs, &t_first_req, &t_service_req, &t_between_reqs);
      topics[id] = topic(nr_reqs, t_first_req, t_service_req, t_between_reqs);
    }
    int nr_personnel;
    scanf("%d", &nr_personnel);
    for (int i = 0; i < nr_personnel; i++) {
      person& p = persons[i];
      p.t_last_start_ = p.t_last_end_ = 0;
      scanf("%d %d", &p.id_, &p.nr_topics_);
      for (int j = 0; j < p.nr_topics_; j++)
        scanf("%d", &p.topics_[j]);
    }
    for (int t = 0; ; t++) {
      int t_arrived = infinite;
      for (map<int, topic>::const_iterator i = topics.begin(); i != topics.end(); ++i)
        if (i->second.nr_reqs_)
          t_arrived = min(t_arrived, i->second.t_arrived_);
      if (t_arrived == infinite) // no more requests
        break;
      if (t < t_arrived)
        t = t_arrived;
#ifdef DEBUG
      printf("%d: arrived: %d\n", t, t_arrived);
#endif
      for (int i = 0; i < nr_personnel; i++) {
        person& p = persons[i];
        if (p.t_last_end_ <= t) {
          // add a person to the topic queue that the person can handle
          for (int j = 0; j < p.nr_topics_; j++)
            if (topics[p.topics_[j]].nr_reqs_ && topics[p.topics_[j]].t_arrived_ <= t)
              topics[p.topics_[j]].persons_.push(i);
        }
      }
      for (map<int, topic>::iterator i = topics.begin(); i != topics.end(); ++i) {
        topic& tp = i->second;
        if (tp.nr_reqs_ && tp.t_arrived_ <= t) {
          priority_queue<int, vector<int>, person_comparator>& pq = tp.persons_;
          while (!pq.empty()) {
            int j = pq.top();
            pq.pop();
            if (persons[j].t_last_end_ <= t) {
              persons[j].t_last_start_ = t, persons[j].t_last_end_ = t + tp.t_service_req_;
#ifdef DEBUG
              printf("  topic %d is dispatched to person %d, start: %d, end: %d\n",
                i->first, persons[j].id_, persons[j].t_last_start_, persons[j].t_last_end_);
#endif
              if (--(tp.nr_reqs_))
                tp.t_arrived_ += tp.t_between_reqs_;
              break;
            }
          }
          while (!pq.empty())
            pq.pop();
        }
      }
    }
    int m = 0;
    for (int i = 0; i < nr_personnel; i++)
      m = max(m, persons[i].t_last_end_);
    printf("Scenario %d: All requests are serviced within %d minutes.\n", scn, m);
  }
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  return 0;
}

UVa 1597 - Searching the Web

Accepted date: 2018-02-05
Run Time: 0.100
Ranking (as of 2018-02-05): 24 out of 188
Language: C++

/*
  UVa 1597 - Searching the Web

  To build using Visual Studio 2015:
    cl -EHsc -O2 UVa_1597_Searching_the_Web.cpp
*/

#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <cctype>
using namespace std;

const int N_max = 100, nr_chars_max = 80, nr_lines_max = 1500;

int N, M, nr_lines;
string lines[nr_lines_max + 1];

pair<int, int> doc_lines[N_max]; // first is the first line, second is the (last line) + 1
enum {op_NONE, op_AND, op_OR, op_NOT};
map< string, set< pair<int, int> > > inverted_index; // key is a term, value is its buckets

const string not_found = "Sorry, I found nothing.\n", separator = "----------\n",
  terminator = "==========\n";

#ifdef DEBUG
void print_inverted_index()
{
  cout << inverted_index.size() << " words\n";
  for (map< string, set < pair<int, int> > >::const_iterator i =
    inverted_index.begin(); i != inverted_index.end(); ++i) {
    cout << i->first << ':';
    for (set < pair<int, int> >::const_iterator j = i->second.begin(); j != i->second.end(); ++j)
      cout << " (" << j->first << ", " << j->second << ')';
    cout << endl;
  }
}
#endif

void get_docs(set<int>& docs, const string& term)
{
  map< string, set< pair<int, int> > >::const_iterator i = inverted_index.find(term);
  if (i != inverted_index.end())
    for (set< pair<int, int> >::const_iterator j = i->second.begin(); j != i->second.end(); ++j)
      docs.insert(j->first);
}

void get_buckets(set< pair <int, int> >& buckets, const string& term)
{
  map< string, set< pair<int, int> > >::const_iterator i = inverted_index.find(term);
  if (i != inverted_index.end()) {
    if (buckets.empty())
      buckets = i->second;
    else {
      for (set< pair<int, int> >::const_iterator j = i->second.begin(); j != i->second.end(); ++j)
        buckets.insert(*j);
    }
  }
}

void get_buckets(set<int>& docs, set< pair <int, int> >& buckets, const string& term)
{
  map< string, set< pair<int, int> > >::const_iterator i = inverted_index.find(term);
  if (i != inverted_index.end()) {
    if (buckets.empty()) {
      buckets = i->second;
      for (set< pair<int, int> >::const_iterator j = i->second.begin(); j != i->second.end(); ++j)
        docs.insert(j->first);
    }
    else {
      for (set< pair<int, int> >::const_iterator j = i->second.begin(); j != i->second.end(); ++j) {
        docs.insert(j->first);
        buckets.insert(*j);
      }
    }
  }
}

void print_lines(const set< pair <int, int> >& buckets)
{
  if (buckets.empty())
    cout << not_found;
  else {
    set< pair <int, int> >::const_iterator i = buckets.begin();
    int j = i->first;
    cout << lines[i->second] << endl;
    for (++i ; i != buckets.end(); ++i) {
      if (i->first != j) {
        j = i->first;
        cout << separator;
      }
      cout << lines[i->second] << endl;
    }
  }
}

void print_lines(const set<int>& docs, const set< pair <int, int> >& buckets)
{
  if (docs.empty())
    cout << not_found;
  else {
    int k = docs.size();
    set< pair <int, int> >::const_iterator i = buckets.begin();
    while (true) {
      while (i != buckets.end() && docs.find(i->first) == docs.end())
        ++i;
      if (i == buckets.end())
        break;
      int j = i->first;
      cout << lines[i->second] << endl;
      for (++i ; i != buckets.end(); ++i) {
        if (i->first != j) {
          if (--k)
            cout << separator;
          break;
        }
        cout << lines[i->second] << endl;
      }
    }
  }
}

int main()
{
  string s;
  istringstream iss;
  getline(cin, s);
  iss.str(s);
  iss >> N;
  iss.clear();
  nr_lines = 0;
  for (int i = 0; i < N; i++) { // read N documents
    doc_lines[i].first = nr_lines;
    while (true) { // read one document
      string& line = lines[nr_lines];
      getline(cin, line);
      if (line == "**********")
        break;
      char word[nr_chars_max + 1];
      for (const char* p = line.c_str(); *p; ) {
        if (isalpha(*p)) {
          char* q = word;
          *q++ = tolower(*p++);
          while (isalpha(*p))
            *q++ = tolower(*p++);
          *q = '\0';
          inverted_index[word].insert(make_pair(i, nr_lines));
        }
        else
          p++;
      }
      nr_lines++;
    }
    doc_lines[i].second = nr_lines;
  }
#ifdef DEBUG
  print_inverted_index();
#endif
  getline(cin, s);
  iss.str(s);
  iss >> M;
  iss.clear();
  while (M--) {
    getline(cin, s);
    iss.str(s);
    string term1, term2;
    iss >> term1;
    int op = op_NONE;
    if (term1 == "NOT") {
      op = op_NOT;
      iss >> term1;
    }
    else if (iss >> term2) {
      op = (term2 == "AND") ? op_AND : op_OR;
      iss >> term2;
    }
    iss.clear();
    switch (op) {
    case op_NONE: // term1
    {
      set< pair <int, int> > buckets;
      get_buckets(buckets, term1);
      print_lines(buckets);
    }
      break;
    case op_AND: // term1 AND term2
    {
      set<int> docs, another_docs, and_docs;
      set< pair <int, int> > buckets;
      get_buckets(docs, buckets, term1);
      get_buckets(another_docs, buckets, term2);
      set_intersection(docs.begin(), docs.end(), another_docs.begin(), another_docs.end(),
                  inserter(and_docs, and_docs.begin()));
      print_lines(and_docs, buckets);
    }
      break;
    case op_OR: // term1 OR term2
    {
      set< pair <int, int> > buckets;
      get_buckets(buckets, term1);
      get_buckets(buckets, term2);
      print_lines(buckets);
    }
      break;
    case op_NOT: // NOT term1
    {
      set<int> docs;
      get_docs(docs, term1);
      int k = N - docs.size();
      if (!k)
        cout << not_found;
      else {
        for (int i = 0; i < N; i++)
          if (docs.find(i) == docs.end()) {
            for (int j = doc_lines[i].first; j < doc_lines[i].second; j++)
              cout << lines[j] << endl;
            if (--k)
              cout << separator;
          }
      }
    }
      break;
    }
    cout << terminator;
  }
  return 0;
}

UVa 207 - PGA Tour Prize Money

Accepted date: 2018-02-01
Run Time: 0.020
Ranking (as of 2018-02-01): 72 out of 186
Language: C++

/*
  UVa 207 - PGA Tour Prize Money

  To build using Visual Studio 2015:
    cl -EHsc -O2 UVa_207_PGA_Tour_Prize_Money.cpp
*/

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

const int infinite = numeric_limits<int>::max() / 2;
const int nr_purses = 70;
double total_purse, purses[nr_purses], prizes[nr_purses];
const int nr_rounds = 4, nr_players_max = 144, nr_chars_player_max = 20,
  nr_chars_line_max = 33;
char player_names[nr_players_max][nr_chars_player_max + 1];
int nr_players;
struct player {
  int i_;
  int amateur_;
  int rd_[nr_rounds], first_, total_;
  int place_;
  bool tie_, prized_;
  double prize_;
} players[nr_players_max];

bool compare_by_first(const player& i, const player& j)
{
  if (i.first_ < j.first_)
    return true;
  else if (i.first_ > j.first_)
    return false;
  else
    return strcmp(player_names[i.i_], player_names[j.i_]) < 0;
}

bool compare_by_total(const player& i, const player& j)
{
  if (i.total_ < j.total_)
    return true;
  else if (i.total_ > j.total_)
    return false;
  else if (i.total_ < infinite && j.total_ < infinite)
    return strcmp(player_names[i.i_], player_names[j.i_]) < 0;
  else if (i.first_ + i.rd_[2] < j.first_ + j.rd_[2])
    return true;
  else if (i.first_ + i.rd_[2] > j.first_ + j.rd_[2])
    return false;
  else
    return strcmp(player_names[i.i_], player_names[j.i_]) < 0;
}

int main()
{
  int nr_cases;
  scanf("%d", &nr_cases);
  while (nr_cases--) {
    scanf("%lf", &total_purse);
    for (int i = 0; i < nr_purses; i++) {
      scanf("%lf", &purses[i]);
      prizes[i] = purses[i] / 100.0 * total_purse;
    }
    int nr;
    scanf("%d", &nr);
    while (getchar() != '\n')
      ;
    nr_players = 0;
    while (nr--) {
      char line[nr_chars_line_max + 1];
      fgets(line, nr_chars_line_max + 1, stdin);
      memcpy(player_names[nr_players], line, nr_chars_player_max);
      player& p = players[nr_players];
      p.i_ = nr_players;
      const char* pn = &player_names[nr_players][nr_chars_player_max - 1];
      while (*pn == ' ')
        pn--;
      p.amateur_ = (*pn == '*') ? 1 : 0;
      p.rd_[0] = p.rd_[1] = p.rd_[2] = p.rd_[3] = p.first_ = p.total_ = infinite;
      for (int i = 0; i < nr_rounds; i++) {
        char rd[3];
        sscanf(line + 20 + i * 3, "%s", rd);
        if (rd[0] == 'D') // "DQ"
          break;
        p.rd_[i] = atoi(rd);
      }
      if (p.rd_[0] != infinite && p.rd_[1] != infinite) {
        p.first_ = p.rd_[0] + p.rd_[1];
        if (p.rd_[2] != infinite && p.rd_[3] != infinite)
          p.total_ = p.first_ + p.rd_[2] + p.rd_[3];
        p.tie_ = p.prized_ = false, p.prize_ = 0.0;
        nr_players++;
      }
    }
    sort(players, players + nr_players, compare_by_first);
    if (nr_players > nr_purses) { // cut the number of players to 70 with ties
      nr = nr_purses;
      while (nr < nr_players && players[nr].first_ == players[nr_purses - 1].first_)
        nr++;
      nr_players = nr;
    }
    sort(players, players + nr_players, compare_by_total);
    for (int i = 0, place = 1; i < nr_players && players[i].total_ < infinite; ) {
      players[i].place_ = place;
      int j;
      for (j = i + 1; j < nr_players && players[j].total_ == players[i].total_; j++)
        players[j].place_ = place;
      place += j - i;
      i = j;
    }
    for (int i = 0, j = 0; i < nr_players && j < nr_purses && players[i].total_ < infinite; ) {
      if (players[i].amateur_) {
        i++;
        continue;
      }
      double prize = prizes[j];
      int ci = 1, cp = 1, cj = 1;
      for ( ; i + ci < nr_players && players[i + ci].total_ == players[i].total_; ci++)
        if (!players[i + ci].amateur_) {
          cp++;
          if (j + cj < nr_purses)
            prize += prizes[j + cj++];
        }
      for (int k = 0; k < ci; k++)
        if (!players[i + k].amateur_)
          players[i + k].tie_ = cp > 1, players[i + k].prized_ = true, players[i + k].prize_ = prize / cp;
      i += ci, j += cj;
    }
    printf("Player Name          Place     RD1  RD2  RD3  RD4  TOTAL     Money Won\n"
      "-----------------------------------------------------------------------\n");
    for (int i = 0; i < nr_players; i++) {
      const player& p = players[i];
      printf("%-21s", player_names[p.i_]);
      if (p.total_ == infinite)
        printf("          ");
      else {
        char s[5];
        sprintf(s, "%d%c", p.place_, ((p.tie_) ? 'T' : ' '));
        printf("%-10s", s);
      }
      printf("%-5d%-5d", p.rd_[0], p.rd_[1]);
      if (p.rd_[2] != infinite) {
        printf("%-5d", p.rd_[2]);
        if (p.rd_[3] != infinite) {
          if (p.amateur_ || !p.prized_)
            printf("%-5d%d\n", p.rd_[3], p.total_);
          else
            printf("%-5d%-10d$%9.2lf\n", p.rd_[3], p.total_, p.prize_);
        }
        else
          printf("     DQ\n");
      }
      else
        printf("          DQ\n");
    }
    if (nr_cases)
      putchar('\n');
  }
  return 0;
}