/*
UVa 12791 - Lap
To build using Visual Studio 2012:
cl -EHsc -O2 UVa_12791_Lap.cpp
*/
#include <cstdio>
int main()
{
int X, Y;
while (scanf("%d %d", &X, &Y) != EOF) {
int d = Y - X;
int lap = Y / d;
if (Y % d)
lap++;
printf("%d\n", lap);
}
return 0;
}
/*
UVa 181 - Hearts
To build using Visual Studio 2012:
cl -EHsc -O2 UVa_181_Hearts.cpp
*/
#include <functional>
#include <algorithm>
#include <cstdio>
using namespace std;
enum {s_Clubs, s_Diamonds, s_Hearts, s_Spades};
enum {d_2 = 2, d_3, d_4, d_5, d_6, d_7, d_8, d_9, d_10,
d_Jack, d_Queen, d_King, d_Ace};
const int nr_suits = s_Spades - s_Clubs + 1, nr_denominations = d_Ace - d_2 + 1,
nr_cards = nr_suits * nr_denominations;
const int nr_players = 5, nr_tricks = 10;
struct card {
int suit_, denomination_;
} cards[nr_cards], player_cards[nr_players];
const int symbols[] = {
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, d_2, d_3, d_4, d_5, d_6, d_7, d_8, d_9, 0, 0, 0, 0, 0, 0,
0, d_Ace, 0, s_Clubs, s_Diamonds, 0, 0, 0, s_Hearts, 0, d_Jack, d_King, 0, 0, 0, 0,
0, d_Queen, 0, s_Spades, d_10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
struct game_suit {
int nr_denominations_;
int denominations_[nr_denominations];
} game[nr_players][nr_suits];
int hearts[nr_players];
int get_trump()
{
card& ci = cards[nr_players * nr_tricks];
card& cj = cards[nr_players * nr_tricks + 1];
if (ci.denomination_ < cj.denomination_)
return cj.suit_;
else if (ci.denomination_ > cj.denomination_)
return ci.suit_;
else
return max(ci.suit_, cj.suit_);
}
void get_leader_card(int pi, int trump)
{
int i = -1;
for (int j = 0; j < nr_suits; j++) {
game_suit& gsj = game[pi][j];
if (!gsj.nr_denominations_)
continue;
if (i == -1)
i = j;
else {
game_suit& gsi = game[pi][i];
int di = gsi.denominations_[gsi.nr_denominations_ - 1],
dj = gsj.denominations_[gsj.nr_denominations_ - 1];
if (di < dj)
i = j;
else if (di == dj && i != trump)
i = j;
}
}
game_suit& gs = game[pi][i];
player_cards[pi].suit_ = i,
player_cards[pi].denomination_ = gs.denominations_[--gs.nr_denominations_];
}
void get_follower_card(int pi, int suit, int trump)
{
int i = -1;
if (game[pi][suit].nr_denominations_)
i = suit;
else if (game[pi][trump].nr_denominations_)
i = trump;
else {
for (int j = 0; j < nr_suits; j++)
if (j != suit && j != trump && game[pi][j].nr_denominations_) {
if (i == -1)
i = j;
else if (game[pi][i].denominations_[game[pi][i].nr_denominations_ - 1] <=
game[pi][j].denominations_[game[pi][j].nr_denominations_ - 1])
i = j;
}
}
game_suit& gs = game[pi][i];
player_cards[pi].suit_ = i,
player_cards[pi].denomination_ = gs.denominations_[--gs.nr_denominations_];
}
int get_winner(int suit, int trump)
{
int i = -1, ti = -1;
for (int j = 0; j < nr_players; j++) {
if (player_cards[j].suit_ == trump) {
if (ti == -1)
ti = j;
else if (player_cards[ti].denomination_ < player_cards[j].denomination_)
ti = j;
}
else if (player_cards[j].suit_ == suit) {
if (i == -1)
i = j;
else if (player_cards[i].denomination_ < player_cards[j].denomination_)
i = j;
}
}
return (ti != -1) ? ti : i;
}
void print_hearts()
{
printf("%3d", hearts[nr_players - 1]);
for (int i = 0; i < nr_players - 1; i++)
printf("%3d", hearts[i]);
putchar('\n');
}
int main()
{
while (true) {
char s[3];
scanf("%s", s);
if (s[0] == '#')
break;
cards[0].suit_ = symbols[s[1]], cards[0].denomination_ = symbols[s[0]];
for (int i = 1; i < nr_cards; i++) {
scanf("%s", s);
cards[i].suit_ = symbols[s[1]], cards[i].denomination_ = symbols[s[0]];
}
int trump = get_trump();
#ifdef DEBUG
printf("trump: %d\n", trump);
#endif
for (int i = 0; i < nr_players; i++) {
hearts[i] = 0;
for (int j = 0; j < nr_suits; j++)
game[i][j].nr_denominations_ = 0;
}
for (int i = 0; i < nr_tricks; i++) // deliver the cards to the players
for (int j = 0; j < nr_players; j++) {
const card& c = cards[i * nr_players + j];
game_suit& gs = game[j][c.suit_];
gs.denominations_[gs.nr_denominations_++] = c.denomination_;
}
for (int i = 0; i < nr_players; i++)
for (int j = 0; j < nr_suits; j++) {
#ifdef DEBUG
printf("player: %d suit: %d demoninations: ", i, j);
#endif
game_suit& gs = game[i][j];
sort(gs.denominations_, gs.denominations_ + gs.nr_denominations_);
#ifdef DEBUG
if (gs.nr_denominations_)
for (int k = 0; k < gs.nr_denominations_; k++)
printf("%d%c", gs.denominations_[k],
((k < gs.nr_denominations_ - 1) ? ' ' : '\n'));
else
putchar('\n');
#endif
}
int leader = 0;
for (int i = 0; i < nr_tricks; i++) {
get_leader_card(leader, trump);
#ifdef DEBUG
printf("trick %d\n player: %d suit: %d demonination: %d\n", i + 1,
leader, player_cards[leader].suit_, player_cards[leader].denomination_);
#endif
int suit = player_cards[leader].suit_;
for (int j = 0; j < nr_players; j++)
if (j != leader) {
get_follower_card(j, suit, trump);
#ifdef DEBUG
printf(" player: %d suit: %d demonination: %d\n",
j, player_cards[j].suit_, player_cards[j].denomination_);
#endif
}
int winner = get_winner(suit, trump);
for (int j = 0; j < nr_players; j++)
if (player_cards[j].suit_ == s_Hearts)
hearts[winner] += player_cards[j].denomination_;
leader = winner;
#ifdef DEBUG
print_hearts();
#endif
}
print_hearts();
}
return 0;
}
/*
UVa 10586 - Polynomial Remains
To build using Visual Studio 2012:
cl -EHsc -O2 UVa_10586_Polynomial_Remains.cpp
*/
#include <cstdio>
const int n_max = 10000;
int coefficients[n_max + 1];
int main()
{
while (true) {
int n, k;
scanf("%d %d", &n, &k);
if (n == -1)
break;
for (int i = 0; i <= n; i++)
scanf("%d", &coefficients[i]);
for (int i = n - k, j = n; i >= 0; i--, j--)
if (coefficients[j]) {
coefficients[i] -= coefficients[j];
coefficients[j] = 0;
}
int i;
for (i = k - 1; i >= 0; i--)
if (coefficients[i])
break;
if (i >= 0) {
for (int j = 0; j <= i; j++) {
printf("%d%c", coefficients[j], ((j < i) ? ' ' : '\n'));
coefficients[j] = 0;
}
}
else
puts("0");
}
return 0;
}
/*
UVa 418 - Molecules
To build using Visual Studio 2012:
cl -EHsc -O2 UVa_418_Molecules.cpp
*/
#include <algorithm>
#include <cstdio>
using namespace std;
const int nr_permutations = 24, nr_chains = 4, nr_elements = 12;
char molecules[nr_chains][nr_elements + 1];
const int orders[nr_permutations][nr_chains] = {
{0, 1, 2, 3}, {0, 1, 3, 2}, {0, 2, 1, 3}, {0, 2, 3, 1},
{0, 3, 1, 2}, {0, 3, 2, 1}, {1, 0, 2, 3}, {1, 0, 3, 2},
{1, 2, 0, 3}, {1, 2, 3, 0}, {1, 3, 0, 2}, {1, 3, 2, 0},
{2, 0, 1, 3}, {2, 0, 3, 1}, {2, 1, 0, 3}, {2, 1, 3, 0},
{2, 3, 0, 1}, {2, 3, 1, 0}, {3, 0, 1, 2}, {3, 0, 2, 1},
{3, 1, 0, 2}, {3, 1, 2, 0}, {3, 2, 0, 1}, {3, 2, 1, 0}
};
int main()
{
while (true) {
scanf("%s", molecules[0]);
if (molecules[0][0] == 'Q')
break;
for (int i = 1; i < nr_chains; i++)
scanf("%s", molecules[i]);
int area = 0;
for (int p = 0; p < nr_permutations; p++) {
const char *vertical_left = molecules[orders[p][0]],
*horizontal_up = molecules[orders[p][1]],
*vertical_right = molecules[orders[p][2]],
*horizontal_down = molecules[orders[p][3]];
for (int i = 1; i < nr_elements - 1; i++)
for (int j = 1; j < nr_elements - 1; j++) {
if (vertical_left[i] != horizontal_up[j])
continue;
for (int jj = j + 2; jj < nr_elements - 1; jj++)
for (int k = 1; k < nr_elements - 1; k++) {
if (horizontal_up[jj] != vertical_right[k])
continue;
for (int ii = i + 2; ii < nr_elements - 1; ii++)
for (int l = 1; l < nr_elements - 1; l++) {
if (vertical_left[ii] != horizontal_down[l])
continue;
int kk = k + ii - i, ll = l + jj - j;
if (kk > 0 && kk < nr_elements - 1 &&
ll > 0 && ll < nr_elements - 1 &&
vertical_right[kk] == horizontal_down[ll]) {
area = max(area, (ii - i - 1) * (jj - j - 1));
}
}
}
}
}
printf("%d\n", area);
}
return 0;
}
/*
UVa 150 - Double Time
To build using Visual Studio 2012:
cl -EHsc -O2 UVa_150_Double_Time.cpp
*/
#include <cstdio>
#include <cstring>
const int nr_chars_max = 15, nr_days_of_week = 7, nr_months = 12;
const char* day_names[nr_days_of_week] = {
"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"
};
const char* month_names[nr_months] = {
"January", "February", "March", "April", "May", "June",
"July", "August", "September", "October", "November", "December"
};
int nr_days[2][nr_months] = {
{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} // leap year
};
int nr_days_of_year[2][nr_months] = {
{31, 59, 90,120,151,181,212,243,273,304,334,365},
{31, 60, 91,121,152,182,213,244,274,305,335,366} // leap year
};
const int start_year = 1582, start_day_of_week = 5 /* Friday */,
julian_calendar_start_days = 273 + 5 /* 5 October */,
gregorian_calendar_start_days = 273 + 15 /* 15 October */;
int get_day_of_week(const char* day)
{
for (int i = 0; i < nr_days_of_week; i++)
if (!strcmp(day, day_names[i]))
return i;
return -1;
}
int get_month(const char* month)
{
for (int i = 0; i < nr_months; i++)
if (!strcmp(month, month_names[i]))
return i;
return -1;
}
bool julian_calendar_leap_year(int year)
{
return !(year % 4);
}
int julian_calendar_number_of_leap_years(int syear, int eyear)
{
// number of leap years between [syear, eyear)
syear--; eyear--;
return eyear / 4 - syear / 4;
}
int julian_calendar_number_of_days(int year, int month, int day)
{
int nr_days = (year - start_year) * 365 +
julian_calendar_number_of_leap_years(start_year, year) -
julian_calendar_start_days;
int leap_year = julian_calendar_leap_year(year) ? 1 : 0;
if (month)
nr_days += nr_days_of_year[leap_year][month - 1];
nr_days += day;
return nr_days;
}
bool gregorian_calendar_leap_year(int year)
{
if (!(year % 400))
return true;
else if (!(year % 100))
return false;
else if (!(year % 4))
return true;
else
return false;
}
int gregorian_calendar_number_of_leap_years(int syear, int eyear)
{
// return the number of leap years between [syear, eyear)
syear--; eyear--;
return (eyear / 4 - eyear / 100 + eyear / 400) -
(syear / 4 - syear / 100 + syear / 400);
}
int gregorian_calendar_number_of_days(int year, int month, int day)
{
int nr_days = (year - start_year) * 365 +
gregorian_calendar_number_of_leap_years(start_year, year) -
gregorian_calendar_start_days;
int leap_year = gregorian_calendar_leap_year(year) ? 1 : 0;
if (month)
nr_days += nr_days_of_year[leap_year][month - 1];
nr_days += day;
return nr_days;
}
int main()
{
while (true) {
int day_of_week, day, month, year, leap_year, j_days, g_days;
char day_name[nr_chars_max + 1], month_name[nr_chars_max + 1];
scanf("%s", day_name);
if (day_name[0] == '#')
break;
scanf("%d %s %d", &day, month_name, &year);
day_of_week = get_day_of_week(day_name), month = get_month(month_name);
j_days = julian_calendar_number_of_days(year, month, day);
if ((start_day_of_week + j_days) % nr_days_of_week == day_of_week) {
// julian calendar
g_days = j_days + gregorian_calendar_start_days;
for (year = start_year; ; year++) {
leap_year = gregorian_calendar_leap_year(year) ? 1 : 0;
if (g_days <= nr_days_of_year[leap_year][nr_months - 1])
break;
g_days -= nr_days_of_year[leap_year][nr_months - 1];
}
for (month = 0; ; month++) {
if (g_days <= nr_days[leap_year][month])
break;
g_days -= nr_days[leap_year][month];
}
printf("%s %d %s %d\n", day_name, g_days, month_names[month], year);
}
else { // gregorian calendar
g_days = gregorian_calendar_number_of_days(year, month, day);
j_days = g_days + julian_calendar_start_days;
for (year = start_year; ; year++) {
leap_year = julian_calendar_leap_year(year) ? 1 : 0;
if (j_days <= nr_days_of_year[leap_year][nr_months - 1])
break;
j_days -= nr_days_of_year[leap_year][nr_months - 1];
}
for (month = 0; ; month++) {
if (j_days <= nr_days[leap_year][month])
break;
j_days -= nr_days[leap_year][month];
}
printf("%s %d* %s %d\n", day_name, j_days, month_names[month], year);
}
}
return 0;
}
/*
UVa 11986 - Save from Radiation
To build using Visual Studio 2012:
cl -EHsc -O2 UVa_11986_Save_from_Radiation.cpp
*/
#include <cstdio>
int main()
{
int T;
scanf("%d", &T);
for (int t = 1; t <= T; t++) {
long long N;
scanf("%lld", &N);
int nr = 0;
for ( ; N; N >>= 1)
nr++;
printf("Case %d: %d\n", t, nr);
}
return 0;
}
/*
UVa 11714 - Blind Sorting
To build using Visual Studio 2012:
cl -EHsc -O2 UVa_11714_Blind_Sorting.cpp
*/
#include <cstdio>
#include <cmath>
int main()
{
long long n;
while (scanf("%lld", &n) != EOF)
printf("%lld\n",
n + static_cast<long long>(ceil(log2(static_cast<double>(n)))) - 2);
return 0;
}
/*
UVa 782 - Contour Painting
To build using Visual Studio 2012:
cl -EHsc -O2 UVa_782_Contour_Painting.cpp
*/
#include <queue>
#include <utility>
#include <cstdio>
#include <cstring>
using namespace std;
const int nr_rows_max = 100, nr_columns_max = 100;
char grid[nr_rows_max + 1][nr_columns_max + 1];
bool visited[nr_rows_max][nr_columns_max];
int main()
{
const int nr_dirs = 4;
const pair<int, int> dirs[nr_dirs] = {
make_pair(1, 0), make_pair(0, 1), make_pair(-1, 0), make_pair(0, -1)
};
int n;
scanf("%d", &n);
while (getchar() != '\n')
;
while (n--) {
int nr_rows = 0, sr = -1, sc;
memset(grid, 0, sizeof(grid));
while (true) {
gets(grid[nr_rows]);
if (grid[nr_rows][0] == '_')
break;
for (char* p = grid[nr_rows]; *p; p++)
if (*p == '*') {
sr = nr_rows, sc = p - grid[nr_rows];
*p = '\0';
}
nr_rows++;
}
memset(visited, 0, sizeof(visited));
queue< pair<int, int> > q;
if (sr != -1) {
visited[sr][sc] = true;
q.push(make_pair(sr, sc));
}
while (!q.empty()) {
pair<int, int> u = q.front();
q.pop();
for (int i = 0; i < nr_dirs; i++) {
int r = u.first + dirs[i].first, c = u.second + dirs[i].second;
if (r >= 0 && r < nr_rows && c >= 0 && c < nr_columns_max) {
if (grid[r][c] != '\0' && grid[r][c] != ' ' && grid[r][c] != '#')
grid[u.first][u.second] = '#';
else if (!visited[r][c]) {
visited[r][c] = true;
q.push(make_pair(r, c));
}
}
}
}
for (int r = 0; r <= nr_rows; r++) {
for (int c = nr_columns_max - 1, lc = -1; c >= 0; c--) {
if (grid[r][c] != '\0' && grid[r][c] != ' ') {
if (lc == -1)
lc = c; // last column
}
else {
if (lc != -1)
grid[r][c] = ' ';
else
grid[r][c] = '\0';
}
}
puts(grid[r]);
}
}
return 0;
}