USACO

USACO 1.2 Palindrome Square

This problem is very straightforward to solve, just pay attention to implementation details.

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool isPalindrome(string str) {
  for (int i = 0, j = str.size() - 1; i < j; ++i, --j) {
    if (str[i] != str[j]) return false;
  }

  return true;
}

string getNumber(int number, int BASE, const vector<int> &table) {
  string str;
  int base = BASE;
  while (number) {
    int digit = number % base;
    int factor = base / BASE;
    digit /= factor;
    str.push_back(table[digit]);
    number -= digit * factor;
    base *= BASE;
  }

  reverse(str.begin(), str.end());
  return str;
}

int main() {

  vector<int> table = { '0' , '1' , '2' , '3' , '4' , '5' , '6' , '7' , '8' , '9' ,
    'A' , 'B' , 'C' , 'D' , 'E' , 'F' , 'G' , 'H' , 'I' , 'J' } ;

  ifstream fin("palsquare.in");
  ofstream fout("palsquare.out");

  int BASE;
  fin >> BASE;
  for (int i = 1; i <= 300; ++i) {
    string num = getNumber(i * i, BASE, table);
    if (isPalindrome(num)) {
      fout << getNumber(i, BASE, table) << " ";
      fout << num << std::endl;
    }
  }

  return 0;
}
USACO

USACO 1.2 Name That Number

This is a search problem and the key is to figure out the search space. Given the input number, we can generate all possible combinations of the valid words and use these words as search space. The other approach is to generate all possible numbers from the input dictionary and then use these numbers as search space. Obviously, given the input constraints (a list of fewer than 5,000 acceptable cattle names), the number search space is more practical.

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>

using namespace std;

string name2number(string name){
  char c = 0;
  int value = 0;
  ostringstream buf;

  for(auto c : name){
    if(c > 'Q')
      value = (c - 1 - 'A') / 3 + 2;
    else
      value = (c - 'A') / 3 + 2;

    buf << value;
  }

  return buf.str();
}

int main() {
  ofstream fout("namenum.out");
  ifstream fin("namenum.in");
  ifstream dict_fin("dict.txt");

  string value;
  fin >> value;

  string name;
  bool not_found = true;
  while(dict_fin >> name){
    string number = name2number(name);
    if(number != value)
      continue;
    fout << name << endl;
    not_found = false;
  }

  if(not_found)
    fout<<"NONE"<<endl;

  dict_fin.close();
  fin.close();
  fout.close();
  return 0;
}

USACO

USACO 1.2 Transformation

Brutal force search… and a Hexo bug that prevent syntax being highlighted!

#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

typedef vector<vector<char> > MATRIX;

void rotateMatrix90(MATRIX &matrix) {
  auto size = matrix.size();
  for (int i = 0; i < size; ++i) {
    for (int j = i + 1; j < size; ++j) {
      swap(matrix[i][j], matrix[j][i]);
    }
    reverse(matrix[i].begin(), matrix[i].end());
  }
}

void rotateMatrix180(MATRIX &matrix) {
  rotateMatrix90(matrix);
  rotateMatrix90(matrix);
}

void rotateMatrix270(MATRIX &matrix) {
  rotateMatrix90(matrix);
  rotateMatrix180(matrix);
}

void reflectMatrixHorizontal(MATRIX &matrix) {
  int size = static_cast<int>(matrix.size());
  for (int i = 0, j = size - 1; i < j; ++i, --j) {
    for (int k = 0; k < size; ++k)
      swap(matrix[k][i], matrix[k][j]);
  }
}

void initializeMatrix(MATRIX &matrix, ifstream &fin) {
  auto demension = matrix.size();
  for (int i = 0; i < demension; ++i) {
    for (int j = 0; j < demension; ++j) {
      fin >> matrix[i][j];
    }
  }
}

int main () {
  string str;
  ifstream fin ("transform.in");
  ofstream fout ("transform.out");

  int demension;
  fin >> demension;
  MATRIX matrix(demension, vector<char>(demension, ' '));
  initializeMatrix(matrix, fin);

  MATRIX baseline(demension, vector<char>(demension, ' '));
  initializeMatrix(baseline, fin);

  MATRIX old = matrix;

  rotateMatrix90(matrix);
  if (baseline == matrix) {
    fout << 1 << std::endl;
    return 0;
  }

  matrix = old;
  rotateMatrix180(matrix);
  if (baseline == matrix) {
    fout << 2 << std::endl;
    return 0;
  }

  matrix = old;
  rotateMatrix270(matrix);
  if (baseline == matrix) {
    fout << 3 << std::endl;
    return 0;
  }

  matrix = old;
  reflectMatrixHorizontal(matrix);
  if (baseline == matrix) {
    fout << 4 << std::endl;
    return 0;
  }

  MATRIX reflected = matrix;
  rotateMatrix90(matrix);
  if (matrix == baseline) {
    fout << 5 << std::endl;
    return 0;
  }

  matrix = reflected;
  rotateMatrix180(matrix);
  if (matrix == baseline) {
    fout << 5 << std::endl;
    return 0;
  }

  matrix = reflected;
  rotateMatrix270(matrix);
  if (matrix == baseline) {
    fout << 5 << std::endl;
    return 0;
  }

  matrix = old;
  if (matrix == baseline) {
    fout << 6 << std::endl;
    return 0;
  }

  fout << 7 << std::endl;
  return 0;
}