/*
UVa 13130 - Cacho
To build using Visual Studio 2015:
cl -EHsc -O2 UVa_13130_Cacho.cpp
*/
#include <cstdio>
int main()
{
int T;
scanf("%d", &T);
while (T--) {
int a1, a2, a3, a4, a5;
scanf("%d %d %d %d %d", &a1, &a2, &a3, &a4, &a5);
puts(
(a1 == 1 && a2 == 2 && a3 == 3 && a4 == 4 && a5 == 5 ||
a1 == 2 && a2 == 3 && a3 == 4 && a4 == 5 && a5 == 6) ? "Y" : "N");
}
return 0;
}
Used trie.
During the construction of trie, counted the number of occurrences of each trie node and
also calculated the goodness for the node.
/*
UVa 11488 - Hyper Prefix Sets
To build using Visual Studio 2015:
cl -EHsc -O2 UVa_11488_Hyper_Prefix_Sets.cpp
*/
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int nr_letters = '1' - '0' + 1, nr_chars_max = 200;
struct trie_node {
static int max_goodness;
int ctr_;
trie_node* children_[nr_letters];
trie_node() : ctr_(0) {
memset(children_, 0, sizeof(children_));
}
~trie_node() {
for (int i = 0; i < nr_letters; i++)
delete children_[i];
}
void insert(const char* s);
void calculate_goodness(int length);
};
int trie_node::max_goodness;
void trie_node::insert(const char* s)
{
trie_node* p = this;
for (int i = 0, length = strlen(s); i < length; i++) {
int j = s[i] - '0';
if (!p->children_[j])
p->children_[j] = new trie_node();
p = p->children_[j];
p->ctr_++;
max_goodness = max(max_goodness, (i + 1) * p->ctr_);
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
trie_node::max_goodness = 0;
trie_node* root = new trie_node();
while (n--) {
char s[nr_chars_max + 1];
scanf("%s", s);
root->insert(s);
}
printf("%d\n", trie_node::max_goodness);
delete root;
}
return 0;
}
/*
UVa 298 - Race Tracks
To build using Visual Studio 2015:
cl -EHsc -O2 UVa_298_Race_Tracks.cpp
*/
#include <queue>
#include <limits>
#include <cstdio>
using namespace std;
const int infinite = numeric_limits<int>::max();
const int X_max = 30, Y_max = 30, v_min = -3, v_max = 3, vc_min = -1, vc_max = 1;
const int nr_vs = v_max - v_min + 1;
int nr_hops[X_max][Y_max][nr_vs][nr_vs];
// nr_hops[x][y][vx - v_min][vy - v_min] is the number of hops at (x, y)
// with the velocity of (vx, vy)
bool obstacles[X_max][Y_max]; // obstacles[x][y] is true if there is an obstacle at (x, y)
struct path {
int x_, y_, vx_, vy_, nr_;
path(int x, int y, int vx, int vy, int nr) : x_(x), y_(y), vx_(vx), vy_(vy), nr_(nr) {}
};
int main()
{
int N;
scanf("%d", &N);
while (N--) {
int X, Y;
scanf("%d %d", &X, &Y);
for (int i = 0; i < X; i++)
for (int j = 0; j < Y; j++) {
obstacles[i][j] = false;
for (int vi = 0; vi < nr_vs; vi++)
for (int vj = 0; vj < nr_vs; vj++)
nr_hops[i][j][vi][vj] = infinite;
}
int sx, sy, fx, fy;
scanf("%d %d %d %d", &sx, &sy, &fx, &fy);
int P;
scanf("%d", &P);
while (P--) {
int x1, x2, y1, y2;
scanf("%d %d %d %d", &x1, &x2, &y1, &y2);
for (int i = x1; i <= x2; i++)
for (int j = y1; j <= y2; j++)
obstacles[i][j] = true;
}
queue<path> q;
nr_hops[sx][sy][-v_min][-v_min] = 0;
q.push(path(sx, sy, -v_min, -v_min, 0));
while (!q.empty()) {
path p = q.front();
q.pop();
#ifdef DEBUG
printf("(%d, %d) with v(%d, %d): %d\n",
p.x_, p.y_, p.vx_ + v_min, p.vy_ + v_min, p.nr_);
#endif
int nr = p.nr_ + 1;
for (int vcx = vc_min; vcx <= vc_max; vcx++) {
int vx = p.vx_ + v_min + vcx;
if (vx < v_min || vx > v_max)
continue;
int x = p.x_ + vx;
if (x < 0 || x >= X)
continue;
for (int vcy = vc_min; vcy <= vc_max; vcy++) {
int vy = p.vy_ + v_min + vcy;
if (vy < v_min || vy > v_max)
continue;
int y = p.y_ + vy;
if (y < 0 || y >= Y || obstacles[x][y])
continue;
if (nr_hops[x][y][vx - v_min][vy - v_min] <= nr)
continue;
#ifdef DEBUG
printf(" (%d, %d) with v(%d, %d): %d\n",
x, y, vx + v_min, vy + v_min, nr);
#endif
nr_hops[x][y][vx - v_min][vy - v_min] = nr;
q.push(path(x, y, vx - v_min, vy - v_min, nr));
}
}
}
int nr = infinite;
for (int vi = 0; vi < nr_vs; vi++)
for (int vj = 0; vj < nr_vs; vj++)
if (nr_hops[fx][fy][vi][vj] < nr)
nr = nr_hops[fx][fy][vi][vj];
if (nr < infinite)
printf("Optimal solution takes %d hops.\n", nr);
else
puts("No solution.");
}
return 0;
}
/*
UVa 1600 - Patrol Robot
To build using Visual Studio 2015:
cl -EHsc -O2 UVa_1600_Patrol_Robot.cpp
*/
#include <queue>
#include <limits>
#include <cstdio>
#include <cstring>
using namespace std;
const int infinite = numeric_limits<int>::max();
const int m_max = 20, n_max = 20, k_max = 20;
const int nr_dirs = 4;
const int dirs[nr_dirs][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int obstacles[m_max][n_max];
// obstacles[i][j] is 1 if there is an obstacle at cell(i, j), 0 otherwise
int nr_moves[m_max][n_max][k_max + 1];
// nr_moves[i][j][k] is the minimum number of moves from (0, 0) to (i, j)
// with the turbo mode used for k cells
struct path {
int i_, j_, k_, nr_;
path(int i, int j, int k, int nr) : i_(i), j_(j), k_(k), nr_(nr) {}
};
int main()
{
int ns;
scanf("%d", &ns);
while (ns--) {
int m, n, k;
scanf("%d %d", &m, &n);
scanf("%d", &k);
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
scanf("%d", &obstacles[i][j]);
for (int l = 0; l <= k; l++)
nr_moves[i][j][l] = infinite;
}
queue<path> q;
nr_moves[0][0][0] = 0;
q.push(path(0, 0, 0, nr_moves[0][0][0]));
while (!q.empty()) {
path p = q.front(); q.pop();
#ifdef DEBUG
printf("[%d][%d][%d]: %d\n", p.i_, p.j_, p.k_, p.nr_);
#endif
for (int d = 0; d < nr_dirs; d++) {
int i = p.i_ + dirs[d][0], j = p.j_ + dirs[d][1], l = p.k_;
if (i < 0 || i >= m || j < 0 || j >= n)
continue;
if (obstacles[i][j]) {
if (l + 1 <= k && p.nr_ + 1 < nr_moves[i][j][l + 1]) {
nr_moves[i][j][l + 1] = p.nr_ + 1;
q.push(path(i, j, l + 1, nr_moves[i][j][l + 1]));
}
}
else {
if (p.nr_ + 1 < nr_moves[i][j][0]) {
nr_moves[i][j][0] = p.nr_ + 1;
q.push(path(i, j, 0, nr_moves[i][j][0]));
}
}
}
}
int nr = infinite;
for (int l = 0; l <= k; l++)
if (nr_moves[m - 1][n - 1][l] < nr)
nr = nr_moves[m - 1][n - 1][l];
printf("%d\n", (nr < infinite) ? nr : -1);
}
return 0;
}
/*
UVa 12893 - Count It
To build using Visual Studio 2015:
cl -EHsc -O2 UVa_12893_Count_It.cpp
*/
#include <cstdio>
long long count_it(long long n)
{
if (!n)
return 0;
long long cn = count_it(n / 2);
if (n & 1)
cn++;
return cn;
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
long long n;
scanf("%lld", &n);
printf("%lld\n", count_it(n));
}
return 0;
}
/*
UVa 210 - Concurrency Simulator
To build using Visual Studio 2015:
cl -EHsc -O2 UVa_210_Concurrency_Simulator.cpp
*/
#include <iostream>
#include <string>
#include <sstream>
#include <deque>
#include <cstring>
using namespace std;
const int nr_programs_max = 10, nr_statements_max = 26;
enum {st_assignment, st_output, st_lock, st_unlock, st_end};
const int nr_statement_types = st_end - st_assignment + 1;
struct statement {
int type_;
int variable_, value_;
};
struct program {
int current_; // current statement
int remaining_; // number of remaining statements
statement statements_[nr_statements_max];
} programs[nr_programs_max];
const int nr_variables = 'z' - 'a' + 1;
int values[nr_variables];
int nr_programs, execution_times[nr_statement_types], quantum;
deque<int> ready_queue, blocked_queue;
int main()
{
string s;
getline(cin, s);
istringstream iss(s);
int nr_cases;
iss >> nr_cases;
iss.clear();
while (nr_cases--) {
getline(cin, s); // a blank line
getline(cin, s);
iss.str(s);
iss >> nr_programs;
for (int i = 0; i < nr_statement_types; i++)
iss >> execution_times[i];
iss >> quantum;
iss.clear();
memset(values, 0, sizeof(values));
for (int i = 0; i < nr_programs; i++) {
program& p = programs[i];
p.current_ = p.remaining_ = 0;
do {
getline(cin, s);
iss.str(s);
string t, u;
iss >> t;
statement& st = p.statements_[p.remaining_++];
if (t == "print") {
iss >> u;
st.type_ = st_output, st.variable_ = u[0] - 'a';
}
else if (t == "lock")
st.type_ = st_lock;
else if (t == "unlock")
st.type_ = st_unlock;
else if (t == "end")
st.type_ = st_end;
else {
st.type_ = st_assignment, st.variable_ = t[0] - 'a';
iss >> u >> st.value_;
}
iss.clear();
} while (p.statements_[p.remaining_ - 1].type_ != st_end);
#ifdef DEBUG
cout << i << ": " << p.remaining_ << " stateemtns\n";
#endif
ready_queue.push_back(i);
}
bool locked = false;
while (!ready_queue.empty()) {
int i = ready_queue.front();
ready_queue.pop_front();
program& p = programs[i];
int q = quantum;
bool blocked = false;
do {
statement& st = p.statements_[p.current_];
q -= execution_times[st.type_];
switch (st.type_) {
case st_assignment:
values[st.variable_] = st.value_;
p.current_++, p.remaining_--;
break;
case st_output:
cout << i + 1 << ": " << values[st.variable_] << endl;
p.current_++, p.remaining_--;
break;
case st_lock:
if (locked) {
blocked_queue.push_back(i);
q = -1, blocked = true;
}
else {
locked = true;
p.current_++, p.remaining_--;
}
break;
case st_unlock:
if (!blocked_queue.empty()) {
int j = blocked_queue.front();
blocked_queue.pop_front();
ready_queue.push_front(j);
}
locked = false;
p.current_++, p.remaining_--;
break;
case st_end:
p.current_++, p.remaining_--;
break;
}
#ifdef DEBUG
cout << i + 1 << ": " << p.current_ << ' ' << p.remaining_ << ' ' << q << endl;
#endif
} while (p.remaining_ && q > 0);
if (p.remaining_&& !blocked)
ready_queue.push_back(i);
}
if (nr_cases)
cout << endl;
}
return 0;
}
/*
UVa 12908 - The book thief
To build using Visual Studio 2015:
cl -EHsc -O2 UVa_12908_The_book_thief.cpp
*/
#include <cstdio>
#include <cmath>
int main()
{
while (true) {
int s;
scanf("%d", &s);
if (!s)
break;
int n = static_cast<int>(ceil((-1.0 + sqrt(1.0 + 8.0 * s)) / 2.0));
if (n * (n + 1) / 2 == s)
n++;
printf("%d %d\n", n * (n + 1) / 2 - s, n);
}
return 0;
}