UVa 11464 - Even Parity

Accepted date: 2015-10-20
Ranking (as of 2015-10-20): 18 out of 815
Language: C++

/*
  UVa 11464 - Even Parity

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

#include <cstdio>

const int N_max = 15;
int N, min_count, cells[N_max][N_max], transformations[N_max][N_max];

void transformation(int c, int count)
{
  if (c == N) {
    for (int i = 0; i < N - 1; i++)
      for (int j = 0; j < N; j++) {
        int p = 0;
        if (i)
          p += transformations[i - 1][j];
        if (j)
          p += transformations[i][j - 1];
        if (j < N - 1)
          p += transformations[i][j + 1];
        transformations[i + 1][j] = (p & 1) ? 1 : 0;
        if (!transformations[i + 1][j] && cells[i + 1][j]) // transformation of 1 to 0
          return;
        else if (transformations[i + 1][j] != cells[i + 1][j]) {
          if (++count >= min_count)
            return;
        }
      }
    min_count = count;
#ifdef DEBUG
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        printf("%d%c", transformations[i][j], ((j < N - 1) ? ' ' : '\n'));
    printf("%d %d\n", count, min_count);
#endif
  }
  else {
    int cc = cells[0][c];
    transformations[0][c] = cc;
    transformation(c + 1, count);
    if (!min_count)
      return;
    if (!cc && count + 1 < min_count) {
      transformations[0][c] = 1;
      transformation(c + 1, count + 1);
    }
  }
}

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        scanf("%d", &cells[i][j]);
    min_count = N * N + 1;
    transformation(0, 0);
    printf("Case %d: %d\n", t, ((min_count > N * N) ? -1 : min_count));
  }
  return 0;
}

UVa 11157 - Dynamic Frog

Accepted date: 2015-10-19
Ranking (as of 2015-10-19): 35 out of 945
Language: C++

/*
  UVa 11157 - Dynamic Frog

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

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

const int N_max = 100;

struct stone {
  char type_;
  int m_;
} stones[N_max + 2] = {{'B', 0}};

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int N, D;
    scanf("%d %d", &N, &D);
    stones[N + 1].type_ = 'B';
    stones[N + 1].m_ = D;
    for (int n = 1; n <= N; n++) {
      char s[16];
      scanf("%s", s);
      stones[n].type_ = s[0], stones[n].m_ = atoi(s + 2);
    }
#ifdef DEBUG
    for (int n = 0; n <= N + 1; n++)
      printf("%c-%d%c", stones[n].type_, stones[n].m_, ((n <= N) ? ' ' : '\n'));
#endif
    int max_d = 0;
    if (N) {
#ifdef DEBUG
      puts("left to right");
#endif
      for (int i = 0; i <= N; ) {
        if (stones[i + 1].type_ == 'B') {
          max_d = max(max_d, stones[i + 1].m_ - stones[i].m_);
#ifdef DEBUG
          printf("%d - %d: %d %d\n",
            i, i + 1, stones[i + 1].m_ - stones[i].m_, max_d);
#endif
          i++;
        }
        else {
          max_d = max(max_d, stones[i + 2].m_ - stones[i].m_);
#ifdef DEBUG
          printf("%d - %d: %d %d\n",
            i, i + 2, stones[i + 2].m_ - stones[i].m_, max_d);
#endif
          i += 2;
          if (stones[i].type_ == 'S')
            stones[i].type_ = 0; // will not exist on the way back to the left bank
        }
      }
#ifdef DEBUG
      puts("right to left");
#endif
      for (int i = N + 1; i > 0; ) {
        int j = i - 1;
        for ( ; j > 0 && !stones[j].type_; j--)
          ;
        max_d = max(max_d, stones[i].m_ - stones[j].m_);
#ifdef DEBUG
        printf("%d - %d: %d %d\n", i, j, stones[i].m_ - stones[j].m_, max_d);
#endif
        i = j;
      }
    }
    else
      max_d = D;
    printf("Case %d: %d\n", t, max_d);
  }
  return 0;
}

UVa 10980 - Lowest Price in Town

Accepted date: 2015-10-15
Ranking (as of 2015-10-15): 211 out of 559
Language: C++

/*
  UVa 10980 - Lowest Price in Town

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

#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <algorithm>
#include <cstdio>
using namespace std;

const int M_max = 20, K_max = 100;

struct item_price {
  int N_;
  double P_;
} item_prices[M_max];

double lowest_prices[K_max + 1];

int main()
{
  for (int case_nr = 1; ; case_nr++) {
    string s;
    istringstream iss;
    if (!getline(cin, s))
      break;
    iss.str(s);
    double price;
    int M;
    iss >> price >> M;
    iss.clear();
    for (int i = 0; i < M; i++) {
      getline(cin, s);
      iss.str(s);
      iss >> item_prices[i].N_ >> item_prices[i].P_;
      iss.clear();
    }
    for (int k = 1; k <= K_max; k++) {
      double p = price * k;
      for (int i = 0; i < M; i++) {
        const item_price& ip = item_prices[i];
        p = min(p, ip.P_ * (k + ip.N_ - 1) / ip.N_);
        for (int j = 1; j <= ip.N_; j++)
          if (k - j >= 0)
            p = min(p, lowest_prices[k - j] + ip.P_);
          else
            break;
      }
      lowest_prices[k] = p;
#ifdef DEBUG
      printf("%d: %lf\n", k, p);
#endif
    }
    cout << "Case " << case_nr << ":\n";
    getline(cin, s);
    iss.str(s);
    int K;
    while (iss >> K)
      cout << "Buy " << K << " for $" << fixed << setprecision(2) <<
        lowest_prices[K] << endl;
    iss.clear();
  }
  return 0;
}

UVa 1213 - Sum of Different Primes

Accepted date: 2015-10-14
Ranking (as of 2015-10-14): 460 out of 821
Language: C++

/*
  UVa 1213 - Sum of Different Primes

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

#include <cstdio>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif

const int n_max = 1120, k_max = 14, nr_primes_max = 187;
const int primes[nr_primes_max] = {
     2,    3,    5,    7,   11,   13,   17,   19,   23,   29,
    31,   37,   41,   43,   47,   53,   59,   61,   67,   71,
    73,   79,   83,   89,   97,  101,  103,  107,  109,  113,
   127,  131,  137,  139,  149,  151,  157,  163,  167,  173,
   179,  181,  191,  193,  197,  199,  211,  223,  227,  229,
   233,  239,  241,  251,  257,  263,  269,  271,  277,  281,
   283,  293,  307,  311,  313,  317,  331,  337,  347,  349,
   353,  359,  367,  373,  379,  383,  389,  397,  401,  409,
   419,  421,  431,  433,  439,  443,  449,  457,  461,  463,
   467,  479,  487,  491,  499,  503,  509,  521,  523,  541,
   547,  557,  563,  569,  571,  577,  587,  593,  599,  601,
   607,  613,  617,  619,  631,  641,  643,  647,  653,  659,
   661,  673,  677,  683,  691,  701,  709,  719,  727,  733,
   739,  743,  751,  757,  761,  769,  773,  787,  797,  809,
   811,  821,  823,  827,  829,  839,  853,  857,  859,  863,
   877,  881,  883,  887,  907,  911,  919,  929,  937,  941,
   947,  953,  967,  971,  977,  983,  991,  997, 1009, 1013,
  1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069,
  1087, 1091, 1093, 1097, 1103, 1109, 1117
};

int nr_ways[n_max + 1][k_max + 1][nr_primes_max];

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  for (int i = 0; i < nr_primes_max; i++)
    nr_ways[primes[i]][1][i] = 1;
  for (int k = 2; k <= k_max; k++) {
    for (int n = 1; n <= n_max; n++)
      for (int i = 0; i < nr_primes_max; i++) {
        int nr = nr_ways[n][k - 1][i];
        if (nr)
          for (int j = i + 1; j < nr_primes_max; j++)
            if (n + primes[j] <= n_max)
              nr_ways[n + primes[j]][k][j] += nr;
      }
#ifdef DEBUG
    for (int n = 1; n <= n_max; n++) {
      bool printed = false;
      for (int i = 0; i < nr_primes_max; i++)
        if (nr_ways[n][k][i]) {
          printed = true;
          printf("[%d][%d][%d]:%d ", n, k, primes[i], nr_ways[n][k][i]);
        }
      if (printed)
        putchar('\n');
    }
#endif
  }
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif
  while (true) {
    int n, k;
    scanf("%d %d", &n, &k);
    if (!n && !k)
      break;
    int nr = 0;
    for (int i = 0; i < nr_primes_max; i++)
      nr += nr_ways[n][k][i];
    printf("%d\n", nr);
  }
  return 0;
}

UVa 10453 - Make Palindrome

Accepted date: 2015-10-13
Ranking (as of 2015-10-13): 14 out of 1216
Language: C++

/*
  UVa 10453 - Make Palindrome

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

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

const int nr_chars_max = 1000;
enum {upper_left, upper, left};
int c[nr_chars_max + 1][nr_chars_max + 1], b[nr_chars_max + 1][nr_chars_max + 1];

struct cs { // common subsequence
  int i_, j_;
} css[nr_chars_max + 1];

void trace_lcs(const char* s, int i, int j, int& ctr)
{
  if (!i || !j)
    return;
  if (b[i][j] == upper_left) {
    trace_lcs(s, i - 1, j - 1, ctr);
    ctr++;
    css[ctr].i_ = i, css[ctr].j_ = j;
#ifdef DEBUG
    printf("s[%d] t[%d]:%c ", i, j, s[i]);
#endif
  }
  else if (b[i][j] == upper)
    trace_lcs(s, i - 1, j, ctr);
  else
    trace_lcs(s, i, j - 1, ctr);
}

int main()
{
  char s[nr_chars_max + 2], t[nr_chars_max + 2];
  while (gets(s + 1)) {
    int n = strlen(s + 1);
    if (!n) {
      puts("0");
      continue;
    }
    reverse_copy(s + 1, s + n + 1, t + 1);
    t[n + 1] = '\0';
    // calculate the Longest Common Subsequrnce of s and t
    for (int i = 0; i <= n; i++)
      for (int j = 0; j <= n; j++)
        c[i][j] = 0;
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++)
        if (s[i] == t[j]) {
          c[i][j] = c[i - 1][j - 1] + 1;
          b[i][j] = upper_left;
        }
        else if (c[i - 1][j] > c[i][j - 1]) {
          c[i][j] = c[i - 1][j];
          b[i][j] = upper;
        }
        else {
          c[i][j] = c[i][j - 1];
          b[i][j] = left;
        }
#ifdef DEBUG
    printf("%s\n%s\n", s + 1, t + 1);
    printf("%d\n", c[n][n]);
#endif
    int ctr = 0;
    trace_lcs(s, n, n, ctr);
#ifdef DEBUG
    putchar('\n');
#endif
    printf("%d ", n - ctr);
    char u[nr_chars_max * 2 + 2];
    int i = 1, j = 1, k = 1;
    for (int csi = 1; csi <= ctr; csi++) {
      if (i < css[csi].i_)
        do
          u[k++] = s[i++];
        while (i < css[csi].i_);
      if (j < css[csi].j_)
        do
          u[k++] = t[j++];
        while (j < css[csi].j_);
      u[k++] = s[css[csi].i_];
      i++, j++;
    }
    if (i <= n)
      do
        u[k++] = s[i++];
      while (i <= n);
    if (j <= n)
      do
        u[k++] = t[j++];
      while (j <= n);
    u[k] = '\0';
    printf("%s\n", u + 1);
  }
  return 0;
}

UVa 10164 - Number Game

Accepted date: 2015-10-10
Ranking (as of 2015-10-10): 10 out of 481
Language: C++

/*
  UVa 10164 - Number Game

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

#include <cstdio>

const int N_max = 1024;
int N, n, numbers[2 * N_max], solutions[N_max];

bool number_game(int ni, int nr, int s)
{
  if (nr == N)
    return !(s % N);
  else if (ni < n) {
    solutions[nr] = numbers[ni];
    if (number_game(ni + 1, nr + 1, s + numbers[ni]))
      return true;
    if (number_game(ni + 1, nr, s))
      return true;
  }
  return false;
}

int main()
{
  while (true) {
    scanf("%d", &N);
    if (!N)
      break;
    n = 2 * N - 1;
    for (int i = 0; i < n; i++)
      scanf("%d", &numbers[i]);
    if (number_game(0, 0, 0)) {
      puts("Yes");
      for (int i = 0; i < N; i++)
        printf("%d%c", solutions[i], ((i < N - 1) ? ' ' : '\n'));
    }
    else
      puts("No");
  }
  return 0;
}

UVa 10817 - Headmaster's Headache

Accepted date: 2015-10-07
Ranking (as of 2015-10-07): 13 out of 636
Language: C++

/*
  UVa 10817 - Headmaster's Headache

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

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#ifdef DEBUG
#include <cstdio>
#endif
using namespace std;

const int N_max = 100, S_max = 8;
const int pow3s[S_max + 1] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561};

void read_input(int& c, vector<int>& subjects)
{
  string line;
  getline(cin, line);
  istringstream iss(line);
  iss >> c;
  int s;
  while (iss >> s)
    subjects[s - 1]++;
}

int get_index(int s, const vector<int>& subjects)
{
  int index = 0;
  for (int i = 0; i < s; i++)
    index += ((subjects[i] > 2) ? 2 : subjects[i]) * pow3s[i];
  return index;
}

void get_subjects(int index, int s, vector<int>& subjects)
{
  int i;
  for (i = 0; i < s && index; i++, index /= 3)
    subjects[i] = index % 3;
  for ( ; i < s; i++)
    subjects[i] = 0;
}

#ifdef DEBUG
void print_cost(int s, const vector<int>& subjects, int cost)
{
  putchar('[');
  for (int i = 0; i < s; i++) {
    if (i)
      putchar(' ');
    printf("%d", subjects[i]);
  }
  printf("]:%d ", cost);
}
#endif

int main()
{
  while (true) {
    string line;
    getline(cin, line);
    istringstream iss(line);
    int S, m, n;
    iss >> S >> m >> n;
    iss.clear();
    if (!S)
      break;
    int icost = 0;
    vector<int> isubjects(S, 0);
    while (m--) {
      int c;
      read_input(c, isubjects);
      icost += c;
    }
#ifdef DEBUG
    printf("%3d ", 0);
    print_cost(S, isubjects, icost);
    putchar('\n');
#endif
    int s = pow3s[S];
    vector< vector<int> > costs(n + 1, vector<int>(s, -1));
    costs[0][get_index(S, isubjects)] = icost;
    for (int i = 1; i <= n; i++) {
      int c;
      vector<int> subjects(S, 0), psubjects(S);
      read_input(c, subjects);
      for (int j = 0; j < s; j++)
        if (costs[i - 1][j] != -1) {
          if (costs[i][j] == -1)
            costs[i][j] = costs[i - 1][j];
          else
            costs[i][j] = min(costs[i][j], costs[i - 1][j]);
          get_subjects(j, S, psubjects);
          bool employ = false;
          for (int k = 0; k < S; k++)
            if (subjects[k] && psubjects[k] < 2) {
              employ = true;
              psubjects[k]++;
            }
          if (employ) {
            int k = get_index(S, psubjects);
            if (costs[i][k] == -1)
              costs[i][k] = costs[i - 1][j] + c;
            else
              costs[i][k] = min(costs[i][k], costs[i - 1][j] + c);
          }
        }
#ifdef DEBUG
      printf("%3d ", i);
      for (int j = 0; j < s; j++) {
        if (costs[i][j] != -1) {
          get_subjects(j, S, subjects);
          print_cost(S, subjects, costs[i][j]);
        }
      }
      putchar('\n');
#endif
    }
    cout << costs[n][s - 1] << endl;
  }
  return 0;
}