USACO 1.3 Combation Lock

Reduce to a search problem, pay attion to the search space. Code can be further optimized.


#include <iostream>
#include <fstream>
#include <iterator>
#include <vector>
#include <string>
#include <cctype>
#include <algorithm>
#include <tuple>
#include <set>

using namespace std;

int wrap(int num, int N) {
if (num <= 0) {
return num + N;
}
if (num > N) {
return num - N;
}
return num;
}

vector<int> getCandidate(int num, int N) {
vector<int> ret;
int range;
if (N == 1) {
range = 0;
} else if (N == 2) {
range = 1;
} else {
range = 2;
}
cout << -range << endl;
for (int i = -range; i <= range; ++i) {
ret.emplace_back(wrap(num + i, N));
}
return ret;
}

int main() {
ifstream fin("combo.in");
ofstream fout("combo.out");

int N;
vector<int> lock(3, 0), master(3, 0);
vector<vector<int>> a, b;
fin >> N;

for (int i = 0; i < 3; ++i) {
fin >> lock[i];
a.emplace_back(getCandidate(lock[i], N));
}

for (int i = 0; i < 3; ++i) {
fin >> master[i];
b.emplace_back(getCandidate(master[i], N));
}

set<tuple<int, int, int>> s;
for (int i = 0; i < a[0].size(); ++i) {
for (int j = 0; j < a[1].size(); ++j) {
for (int k = 0; k < a[2].size(); ++k) {
s.insert(make_tuple(a[0][i], a[1][j], a[2][k]));
}
}
}

for (int i = 0; i < b[0].size(); ++i) {
for (int j = 0; j < b[1].size(); ++j) {
for (int k = 0; k < b[2].size(); ++k) {
s.insert(make_tuple(b[0][i], b[1][j], b[2][k]));
}
}
}

fout << s.size() << endl;

for (auto &item : s) {
cout << get<0>(item) << ","
<< get<1>(item) << ","
<< get<2>(item) << " ";
}
cout << endl;

return 0;
}

USACO 1.2 Dual Palindrome

Another implementation skill test for base conversion.

#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) {
string str;
int base = BASE;
while (number) {
int digit = number % base;
int factor = base / BASE;
digit /= factor;
str.push_back(digit + '0');
number -= digit * factor;
base *= BASE;
}

return str;
}

int main() {
ifstream fin("dualpal.in");
ofstream fout("dualpal.out");

int N, S;
fin >> N >> S;

for (int i = S + 1, j = 0; j < N;) {
int count = 0;
for (int k = 2; k <= 10; ++k) {
if (j > N) break;
string num = getNumber(i, k);
if (isPalindrome(num)) {
++count;
if (count == 2) {
fout << i << std::endl;
++j; ++i;
break;
}
}
}

if (count != 2) ++i;
}

return 0;
}

TopCoder SRM 696

250_Rope_String
class Ropestring {
public:
string makerope(string s) {
vector<int> even, odd;
int size = (int)s.size();
int cur = 0;
for (int i = 0; i < size; ++i) {
if (s[i] == '-')
++cur;
if (s[i] == '.') {
if (i > 0 && s[i - 1] == '-') {
if (cur % 2) {
odd.push_back(cur);
} else {
even.push_back(cur);
}
cur = 0;
}
}
}
if (s[size - 1] == '-') {
if (cur % 2) {
odd.push_back(cur);
} else {
even.push_back(cur);
}
}

sort(odd.begin(), odd.end());
sort(even.begin(), even.end());
string ret;
int count = 0;

for (int i = (int)even.size() - 1; i >= 0; --i) {
int size = even[i];
while (size) {
ret.push_back('-');
++count;
--size;
}
if (i != 0) {
ret.push_back('.'); ++count;
}
}

if (!even.empty() && !odd.empty()) {
ret.push_back('.'); ++count;
}

for (int i = (int)(odd.size() - 1); i >= 0; --i) {
int size = odd[i];
while (size) {
ret.push_back('-');
++count;
--size;
}
if (i != 0) {
ret.push_back('.'); ++count;
}
}

int left = (int)s.size() - count;
while (left) {
ret.push_back('.'); --left;
}
return ret;
}
};
500_Array_Fix
class Arrfix {
public:
int mindiff(vector <int> A, vector <int> B, vector <int> F) {
unordered_map<int, int> hashb;
unordered_map<int, int> hashf;
for (auto &i : B) {
hashb[i]++;
}
for (auto &i : F) {
hashf[i]++;
}

int diff = 0;
int size = (int)A.size();
int used = 0;
for (int i = 0; i < size; ++i) {
if (A[i] == B[i])
continue;
if (hashf[B[i]]) {
hashf[B[i]]--;
++used;
hashb[B[i]]--;
continue;
}
++diff;
}

if (used == (int)F.size())
return diff;

for (auto iter = hashf.begin(); iter != hashf.end(); ++iter) {
int key = iter->first;
int count = iter->second;
if (count == 0) continue;
if (hashb[key]) {
hashb[key]--;
} else {
++diff;
}
}
return diff;
}
};