UVa 10564 - Paths through the Hourglass

Accepted date: 2014-09-30
Ranking (as of 2014-09-30): 30 out of 599
Language: C++

/*
  UVa 10564 - Paths through the Hourglass

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

#include <cstdio>
#include <cstring>

/*
Let cells[r][c] is the value of cell at r-th row, c-th column, and, 
nr_paths[r][c][s] is the number of paths that leads to cells[r][c] with 
  the path value of s, then:
  nr_paths[r][c][s] = nr_paths[r - 1][left to c][s - cells[r][c]] +
    nr_paths[r - 1][right to c][s - cells[r][c]
*/

const int N_max = 20, S_max = 500;

int cells[N_max * 2 - 1][N_max];
long long nr_paths[N_max * 2 - 1][N_max][S_max];

#ifdef DEBUG
void print_s(int N, int S, int r)
{
  printf("%d\n", r);
  for (int c = 0; c < N; c++)
    for (int s = 0; s <= S; s++)
      printf("%3lld%c", nr_paths[r][c][s], ((s < S) ? ' ' : '\n'));
  putchar('\n');
}
#endif

/*
6 41      r   cs
6 7 2 3 6 8   0   0
  1 8 0 7 1   1   1
    2 6 5 7   2   2
      3 1 0   3   3
        7 6   4   4
          8   5   5
        8 8   6   4
      6 5 3   7   3
    9 5 9 5   8   2
  6 4 4 1 3   9   1
2 6 9 4 3 8   10  0
*/

void follow_paths(int N, int S)
{
  for (int c = 0; c < N; c++)
    for (int s = 0; s <= S; s++)
      nr_paths[2 * (N - 1)][c][s] = (s == cells[2 * (N - 1)][c]) ? 1 : 0;
#ifdef DEBUG
  print_s(N, S, 2 * (N - 1));
#endif
  for (int r = 2 * (N - 1) - 1, ci = 1; r >= 0; r--, ((r >= N - 1) ? ci++ : ci--)) {
    for (int c = ci; c < N; c++) {
      int cs = cells[r][c];
      for (int s = 0; s <= S; s++) {
        if (s < cs)
          nr_paths[r][c][s] = 0;
        else {
          long long np_left, np_right;
          if (r >= N - 1) {
            np_left = nr_paths[r + 1][c - 1][s - cs]; // from lower left
            np_right = nr_paths[r + 1][c][s - cs]; // from lower right
          }
          else {
            np_left = (c > ci) ? nr_paths[r + 1][c][s - cs] : 0;
              // from lower left
            np_right = (c < N - 1) ? nr_paths[r + 1][c + 1][s - cs] : 0;
              // from lower right
          }
          nr_paths[r][c][s] = np_left + np_right;
        }
      }
    }
#ifdef DEBUG
    print_s(N, S, r);
#endif
  }
}

void trace_path(int N, int r, int c, int s, char* path)
{
  int cs;
  if (r < N - 1) {
    cs = cells[r][c];
    if (c > r && nr_paths[r + 1][c][s - cs]) { // to lower left
      path[r] = 'L';
      trace_path(N, r + 1, c, s - cs, path);
    }
    else { // to lower right
      path[r] = 'R';
      trace_path(N, r + 1, c + 1, s - cs, path);
    }
  }
  else if (r < 2 * (N - 1)) {
    cs = cells[r][c];
    if (nr_paths[r + 1][c - 1][s - cs]) { // to lower left
      path[r] = 'L';
      trace_path(N, r + 1, c - 1, s - cs, path);
    }
    else { // to lower right
      path[r] = 'R';
      trace_path(N, r + 1, c, s - cs, path);
    }
  }
}

int main()
{
  while (true) {
    int N, S;
    scanf("%d %d", &N, &S);
    if (!N && !S)
      break;
    for (int r = 0, ci = 0; r < 2 * N - 1; r++, ((r < N) ? ci++ : ci--))
      for (int c = ci; c < N; c++)
        scanf("%d", &cells[r][c]);
    follow_paths(N, S);
    int first_c = -1;
    long long nr = 0;
    for (int c = 0; c < N; c++)
      if (nr_paths[0][c][S]) {
        if (first_c == -1)
          first_c = c;
        nr += nr_paths[0][c][S];
      }
    printf("%lld\n", nr);
    if (first_c != -1) {
      char path[N_max * 2 - 1];
      trace_path(N, 0, first_c, S, path);
      path[2 * (N - 1)] = '\0';
      printf("%d %s\n", first_c, path);
    }
    else
      putchar('\n');
  }
  return 0;
}

UVa 11227 - The silver bullet.

Accepted date: 2014-09-21
Ranking (as of 2014-09-21): 379 out of 594
Language: C++

/*
  UVa 11227 - The silver bullet.

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

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <limits>
using namespace std;

const double epsilon = numeric_limits<double>::epsilon();

struct point {
  double x_, y_;

  bool operator==(const point& p) const {
    return fabs(x_ - p.x_) <= epsilon && fabs(y_ - p.y_) <= epsilon;
  }
  bool operator<(const point& p) const {
    return (x_ != p.x_) ? x_ < p.x_ : y_ < p.y_;
  }
};

struct line {
  double a_; // x-coefficient
  double b_; // y-coefficient
  double c_; // constant term

  bool operator<(const line& l) const {
    if (a_ != l.a_)
      return a_ < l.a_;
    else if (b_ != l.b_)
      return b_ < l.b_;
    else
      return c_ < l.c_;
  }
};

void points_to_line(const point& p1, const point& p2, line& l)
{
  if (fabs(p1.x_ - p2.x_) <= epsilon) {
    l.a_ = 1.0; l.b_ = 0; l.c_ = -p1.x_;
  }
  else {
    l.b_ = 1.0;
    l.a_ = -(p1.y_ - p2.y_) / (p1.x_ - p2.x_);
    l.c_ = -(l.a_ * p1.x_) - l.b_ * p1.y_;
  }
}

int main()
{
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    int N;
    cin >> N;
    vector<point> points(N);
    for (int i = 0; i < N; i++)
      cin >> points[i].x_ >> points[i].y_;
    sort(points.begin(), points.end());
    // remove the duplicate points
    for (vector<point>::iterator pi = points.begin(); pi != points.end(); ) {
      vector<point>::iterator pj = pi;
      ++pj;
      if (pj != points.end() && *pi == *pj)
        pi = points.erase(pi);
      else
        ++pi;
    }
    size_t n = points.size();
    map< line, set<point> > lines;
    for (size_t i = 0; i < n - 1; i++)
      for (size_t j = i + 1; j < n; j++) {
        line l;
        points_to_line(points[i], points[j], l);
        pair< map< line, set<point> >::iterator, bool > result =
          lines.insert(make_pair(l, set<point>()));
        result.first->second.insert(points[i]);
        result.first->second.insert(points[j]);
      }
    cout << "Data set #" << t;
    if (n > 1) {
      size_t aligned_max = 0;
      for (map< line, set<point> >::const_iterator li = lines.begin(),
        le = lines.end(); li != le; ++li)
        aligned_max = max(aligned_max, li->second.size());
      cout << " contains " << n << " gnus, out of which a maximum of " <<
        aligned_max << " are aligned.\n";
    }
    else
      cout << " contains a single gnu.\n";
  }
}

UVa 11947 - Cancer or Scorpio

Accepted date: 2014-09-15
Ranking (as of 2014-09-15): 477 out of 562
Language: JAVA

// UVa 11947 - Cancer or Scorpio

import java.util.Scanner;
import java.text.SimpleDateFormat;
import java.text.ParseException;
import java.util.Date;
import java.util.Calendar;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.ListIterator;

class Main {
  public static void main(String[] args) {
    SimpleDateFormat parseFormat = new SimpleDateFormat("MMddyyyy"),
      printFormat = new SimpleDateFormat("MM/dd/yyyy");
    Calendar cal = Calendar.getInstance();
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    for (int i = 1; i <= N; i++) {
      try {
        Date date = parseFormat.parse(sc.next());
        cal.setTime(date);
        cal.add(Calendar.WEEK_OF_YEAR, 40);
        String name = ZodiacSign.getZodiacSign(isLeapYear(cal.get(Calendar.YEAR)),
          cal.get(Calendar.DAY_OF_YEAR));
        System.out.println(i + " " + printFormat.format(cal.getTime()) + " " + name);
      }
      catch (ParseException e) {
      }
    }
  }

  static boolean isLeapYear(int year) {
      return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
  }
}

class ZodiacSign {
  final String name;
  final int begin, end;

  ZodiacSign(String name, int begin, int end) {
    this.name = name; this.begin = begin; this.end = end;
  }

  static final ArrayList<ZodiacSign> zodiacSigns =
    new ArrayList<ZodiacSign>(Arrays.asList(
      new ZodiacSign("capricorn",          1,        20),
      new ZodiacSign("aquarius",          21,   31 + 19),
      new ZodiacSign("pisces",       31 + 20,   59 + 20),
      new ZodiacSign("aries",        59 + 21,   90 + 20),
      new ZodiacSign("taurus",       90 + 21,  120 + 21),
      new ZodiacSign("gemini",      120 + 22,  151 + 21),
      new ZodiacSign("cancer",      151 + 22,  181 + 22),
      new ZodiacSign("leo",         181 + 23,  212 + 21),
      new ZodiacSign("virgo",       212 + 22,  243 + 23),
      new ZodiacSign("libra",       243 + 24,  273 + 23),
      new ZodiacSign("scorpio",     273 + 24,  304 + 22),
      new ZodiacSign("sagittarius", 304 + 23,  334 + 22),
      new ZodiacSign("capricorn",   334 + 23,  334 + 31)
  ));

  static final ArrayList<ZodiacSign> leapYearZodiacSigns =
    new ArrayList<ZodiacSign>(Arrays.asList(
      new ZodiacSign("capricorn",          1,        20),
      new ZodiacSign("aquarius",          21,   31 + 19),
      new ZodiacSign("pisces",       31 + 20,   60 + 20),
      new ZodiacSign("aries",        60 + 21,   91 + 20),
      new ZodiacSign("taurus",       91 + 21,  121 + 21),
      new ZodiacSign("gemini",      121 + 22,  152 + 21),
      new ZodiacSign("cancer",      152 + 22,  182 + 22),
      new ZodiacSign("leo",         182 + 23,  213 + 21),
      new ZodiacSign("virgo",       213 + 22,  244 + 23),
      new ZodiacSign("libra",       244 + 24,  274 + 23),
      new ZodiacSign("scorpio",     274 + 24,  305 + 22),
      new ZodiacSign("sagittarius", 305 + 23,  335 + 22),
      new ZodiacSign("capricorn",   335 + 23,  335 + 31)
  ));

  static String getZodiacSign(boolean leapYear, int dayOfYear) {
    final ArrayList<ZodiacSign> list = (leapYear) ? leapYearZodiacSigns : zodiacSigns;
    String name = "";
    for (ListIterator<ZodiacSign> i = list.listIterator(); i.hasNext(); ) {
      ZodiacSign zs = i.next();
      if (dayOfYear >= zs.begin && dayOfYear <= zs.end) {
        name = zs.name; break;
      }
    }
    return name;
  }
}

UVa 10246 - Asterix and Obelix

Accepted date: 2014-09-14
Ranking (as of 2014-09-14): 76 out of 613
Language: C++

/*
  UVa 10246 - Asterix and Obelix

  To build using Visucal Studio 2012:
    cl -EHsc UVa_10246_Asterix_and_Obelix.cpp
*/

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

const int C_max = 80;
int feasts[C_max + 1];
int fcosts[C_max + 1][C_max + 1], pcosts[C_max + 1][C_max + 1];

void floyd_warshall(int n)
{
  for (int k = 1; k <= n; k++)
    for (int i = 1; i <= n; i++) 
      if (pcosts[i][k] != numeric_limits<int>::max())
        for (int j = 1; j <= n; j++)
          if (pcosts[k][j] != numeric_limits<int>::max()) {
            if (pcosts[i][k] + pcosts[k][j] + max(fcosts[i][k], fcosts[k][j]) <
              pcosts[i][j] + fcosts[i][j]) {
              pcosts[i][j] = pcosts[i][k] + pcosts[k][j];
              fcosts[i][j] = max(fcosts[i][k], fcosts[k][j]);
            }
          }
}

int main()
{
  bool printed = false;
  for (int cn = 1; ; cn++) {
    int C, R, Q;
    scanf("%d %d %d", &C, &R, &Q);
    if (!C && !R && !Q)
      break;
    if (printed)
      putchar('\n');
    else
      printed = true;
    for (int i = 1; i <= C; i++)
      scanf("%d", &feasts[i]);
    for (int i = 1; i <= C; i++)
      for (int j = 1; j <= C; j++)
        if (i != j) {
          pcosts[i][j] = numeric_limits<int>::max();
          fcosts[i][j] = 0;
        }
        else {
          pcosts[i][i] = 0;
          fcosts[i][i] = feasts[i];
        }

    while (R--) {
      int c1, c2, d;
      scanf("%d %d %d", &c1, &c2, &d);
      pcosts[c1][c2] = pcosts[c2][c1] = d;
      fcosts[c1][c2] = fcosts[c2][c1] = max(feasts[c1], feasts[c2]);
    }
    floyd_warshall(C);
    floyd_warshall(C);
    printf("Case #%d\n", cn);
    while (Q--) {
      int c1, c2;
      scanf("%d %d", &c1, &c2);
      int min_d = numeric_limits<int>::max();
      printf("%d\n", ((pcosts[c1][c2] != numeric_limits<int>::max()) ?
        pcosts[c1][c2] + fcosts[c1][c2] : -1));
    }
  }
  return 0;
}

UVa 545 - Heads

Accepted date: 2014-09-10
Ranking (as of 2014-09-10): 137 out of 609
Language: C++

/*
  UVa 545 - Heads

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

#include <cstdio>
#include <cmath>

const int n_max = 9000;

struct probability {
  double x_;
  int y_;
} probabilities[n_max + 1];

int main()
{
  const double eps = 1.0e-9; // without this value, the verdict was WA.
  int n, y = 0;
  double x = 1.0;
  probabilities[0].x_ = x; probabilities[0].y_ = y;
  for (n = 1; n <= n_max; n++) {
    x /= 2.0;
    if (x < 1.0) {
      x *= 10.0;
      y++;
    }
    probabilities[n].x_ = x; probabilities[n].y_ = y;
  }
  int r;
  scanf("%d", &r);
  while (r--) {
    int n;
    scanf("%d", &n);
    printf("2^-%d = %.3lfE-%d\n", n, probabilities[n].x_ + eps, probabilities[n].y_);
  }
  return 0;
}

UVa 743 - The MTM Machine

Accepted date: 2014-09-06
Language: C++

/*
  UVa 743 - The MTM Machine

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

#include <cstdio>
#include <cstring>

const int nr_digits_max = 1000;
char s[nr_digits_max + 1], t[nr_digits_max + 1];

void associate(int si, int length, char* s, char* t)
{
  if (--si >= 0 && s[si] == '3') {
    memcpy(t, s, si);
    memcpy(t + si, s + si + 1, length - si - 1);
    t[length - 1] = '2';
    memcpy(t + length, s + si + 1, length - si); // including '\0'
    associate(si, length * 2 - si - 1, t, s);
  }
  else
    puts(s);
}

bool MTM()
{
  if (strchr(s, '0'))
    return false;
  else {
    int length = strlen(s);
    for (int i = 0; i < length; i++) {
      if (s[i] == '2') {
        if (i < length - 1) {
          // remove '2'
          memcpy(t, s, i);
          memcpy(t + i, s + i + 1, length - i + 1); // including '\0'
          associate(i, length - 1, t, s); 
          return true;
        }
        else
          break;
      }
      else if (s[i] != '3')
        break;
    }
    return false;
  }
}

int main()
{
  while (true) {
    scanf("%s", s);
    if (!strcmp(s, "0"))
      break;
    if (!MTM())
      puts("NOT ACCEPTABLE");
  }
  return 0;
}