UVa 12032 - The Monkey and the Oiled Bamboo

Accepted date: 2014-02-15
Ranking (as of 2014-02-15): 27 out of 595
Language: C++

/*
  UVa 12032 - The Monkey and the Oiled Bamboo

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

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

const int n_max = 100000;
int rungs[n_max];

int main()
{
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
      scanf("%d", &rungs[i]);
    int k = rungs[0];
    for (int i = 1; i < n; i++)
      k = max(k, rungs[i] - rungs[i - 1]);
    int j = k;
    if (rungs[0] == j)
      j--;
    for (int i = 1; i < n; i++) {
      int d = rungs[i] - rungs[i - 1];
      if (d == j)
        j--;
      else if (d > j) {
        k++; break;
      }
    }
    printf("Case %d: %d\n", t, k);
  }
  return 0;
}

UVa 11549 - Calculator Conundrum

Accepted date: 2014-02-11
Ranking (as of 2014-02-11): 275 out of 702
Language: C++

/*
  UVa 11549 - Calculator Conundrum

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

#include <set>
#include <cstdio>
#include <cmath>
using namespace std;

int main()
{
  const int power_of_10s[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 
    10000000, 100000000, 1000000000};
  int t;
  scanf("%d", &t);
  while (t--) {
    int n, k;
    scanf("%d %d", &n, &k);
    if (k < 2)
      printf("%d\n", k);
    else {
      int power_of_10 = power_of_10s[n];
      int k_max = power_of_10 - 1, displayed_max = 0;
      set<int> displayed_numbers;
      while (true) {
        if (k == k_max) {
          displayed_max = k; break;
        }
        pair<set<int>::iterator, bool> result = displayed_numbers.insert(k);
        if (!result.second)
          break;
        if (k > displayed_max)
          displayed_max = k;
        long long lk = k;
        lk *= lk;
        int nr_digits = static_cast<int>(log10(static_cast<double>(lk)) + 1.0);
        if (nr_digits > n)
          lk /= power_of_10s[nr_digits - n];
        k = static_cast<int>(lk);
#ifdef DEBUG
        printf("%d\n", k);
#endif
      }
      printf("%d\n", displayed_max);
    }
  }
  return 0;
}

UVa 10518 - How Many Calls?

Accepted date: 2014-01-25
Ranking (as of 2014-01-25): 216 out of 794
Language: C++

/*
  UVa 10518 - How Many Calls?

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

/*
Let nr_calls_fib(n) be the number of calls to evaluate the n-th (n > 0) 
  fibonacci number, then:
  nr_calls_fib(n) = 2 * fib(n) - 1
*/

#include <cstdio>

long long fib_mod(long long n, int m) // calculate fib(n) mod m in O(log2(n))
{
  long long i = 1, h = 1, j = 0, k = 0, t;
  for ( ; n > 0; n >>= 1) {
    if (n & 1) {
      t = j * h % m;
      j = i * h % m + j * k % m + t;
      i = i * k % m + t;
    }
    t = h * h % m;
    h = 2 * k * h % m + t;
    k = k * k % m + t;
  }
  return j;
}

int main()
{
  for (int c = 1; ; c++) {
    long long n;
    int b;
    scanf("%lld %d", &n, &b);
    if (!n && !b)
      break;
    int nr_calls = 1 % b;
    if (n) {
      long long fb = fib_mod(n + 1, b);
      nr_calls = static_cast<int>((2 * fb - 1 + b) % b);
    }
    printf("Case %d: %lld %d %d\n", c, n, b, nr_calls);
  }
  return 0;
}

UVa 893 - Y3K Problem

Accepted date: 2014-01-24
Ranking (as of 2014-01-24): 214 out of 585
Language: C++

/*
  UVa 893 - Y3K Problem

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

#include <iostream>
using namespace std;

inline bool is_leap_year(int year)
{
  if (!(year % 400))
    return true;
  else if (!(year % 100))
    return false;
  else if (!(year % 4))
    return true;
  else
    return false;
}

// return the number of days of given year
int get_number_of_days(int year)
{
  return (is_leap_year(year)) ? 366 : 365;
}

// return the number of days from the first day of given year
int get_number_of_days(int year, int month, int day)
{
  const int nr_days[] =
    {0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334};
    // nr_days[i] is the number of days before the first day of i-th month
  const int nr_days_leap_year[] =
    {0, 0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335};
    // nr_days[i] is the number of days before the first day of i-th month
    // for leap years
  int nd = day;
  nd += (is_leap_year(year)) ? nr_days_leap_year[month] : nr_days[month];
  return nd;
}

// return the month and day from the number of days of given year
void get_month_day(int year, int nr_days, int& month, int& day)
{
  const int nr_month_days[] =
    {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365};
    // nr_month_days[i] is the number of days up to i-th month
  const int nr_month_days_leap_year[] =
    {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335, 366};
    // nr_month_days[i] is the number of days up to i-th month for leap years
  const int* month_days = (is_leap_year(year)) ?
    nr_month_days_leap_year : nr_month_days;
  for (month = 1; ; month++)
    if (month_days[month] >= nr_days)
      break;
  day = nr_days - month_days[month - 1];
}

int main()
{
  while (true) {
    int n, d, m, y;
    cin >> n >> d >> m >> y;
    if (!n && !d && !m && !y)
      break;
    n += get_number_of_days(y, m, d);
    for (int nd = get_number_of_days(y); n > nd; nd = get_number_of_days(++y))
      n -= nd;
    get_month_day(y, n, m, d);
    cout << d << ' ' << m << ' ' << y << endl;
  }
  return 0;
}

UVa 10126 - Zipf's Law

Accepted date: 2014-01-22
Ranking (as of 2014-01-22): 212 out of 588
Language: C++

/*
  UVa 10126 - Zipf's Law

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

#include <iostream>
#include <string>
#include <sstream>
#include <map>
#include <algorithm>
#include <cctype>
using namespace std;

int main ()
{
  string line;
  istringstream iss;

  bool printed = false;
  while (getline(cin, line)) {
    if (printed)
      cout << endl;
    else
      printed = true;
    istringstream iss(line);
    int n;
    iss >> n;
    map<string, int> words;
    while (true) {
      getline(cin, line);
      if (line == "EndOfText")
        break;
      transform(line.begin(), line.end(), line.begin(), (int(*)(int))tolower);
      for (const char* p =  line.c_str(); *p; ) {
        for ( ; *p && !isalpha(*p); p++)
          ;
        const char* q = p;
        for ( ; *p && isalpha(*p); p++)
          ;
        if (p - q) {
          pair<map<string, int>::iterator, bool> result =
            words.insert(make_pair(string(q, p - q), 1));
          if (!result.second)
            result.first->second++;
        }
      }
    }
    bool found = false;
    for (map<string, int>::const_iterator i = words.begin(), e = words.end();
      i != e; ++i)
      if (i->second == n) {
        found = true;
        cout << i->first << endl;
      }
    if (!found)
      cout << "There is no such word.\n";
  }
  return 0;
}

UVa 11634 - Generate random numbers

Accepted date: 2014-01-21
Ranking (as of 2014-01-21): 104 out of 579
Language: C++

/*
  UVa 11634 - Generate random numbers

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

#include <cstdio>
#include <cstring>

const int a0_max = 10000 - 1;
bool numbers[a0_max + 1]; // numbers[i] is true if i has already been produced

int main()
{
  while (true) {
    int a;
    scanf("%d", &a);
    if (!a)
      break;
    memset(numbers, 0, sizeof(numbers));
    int nr = 0;
    while (true) {
      if (numbers[a])
        break;
      numbers[a] = true;
      a *= a;
      a /= 100;
      a %= 10000;
      nr++;
    }
    printf("%d\n", nr);
  }
  return 0;
}

UVa 10528 - Major Scales

Accepted date: 2014-01-18
Ranking (as of 2014-01-18): 125 out of 581
Language: C++

/*
  UVa 10528 - Major Scales

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

#include <cstdio>
#include <cstring>
#include <cctype>

const int nr_notes = 12;

const char* notes[nr_notes] = {
  "C", "C#", "D", "D#", "E", "F",
  "F#", "G", "G#", "A", "A#", "B"
};

const bool scales[nr_notes][nr_notes] = {
  // scales[i][j] is true if i-th scale has j-th note
//  C     C#    D   D#    E   F   F#    G   G#    A   A#    B
  {true,  false,  true, false,  true, true,
    false,  true, false,  true, false,  true},  // C
  {true,  true, false,  true, false,  true,
    true, false,  true, false,  true, false}, // C#
  {false, true, true, false,  true, false,
    true, true, false,  true, false,  true},  // D
  {true,  false,  true, true, false,  true,
    false,  true, true, false,  true, false}, // D#
  {false, true, false,  true, true, false,
    true, false,  true, true, false,  true},  // E
  {true,  false,  true, false,  true, true,
    false,  true, false,  true, true, false}, // F
  {false, true, false,  true, false,  true,
    true, false,  true, false,  true, true},  // F#
  {true,  false,  true, false,  true, false,
    true, true, false,  true, false,  true},  // G
  {true,  true, false,  true, false,  true,
    false,  true, true, false,  true, false}, // G#
  {false, true, true, false,  true, false,
    true, false,  true, true, false,  true},  // A
  {true,  false,  true, true, false,  true,
    false,  true, false,  true, true, false}, // A#
  {false, true, false,  true, true, false,
    true, false,  true, false,  true, true} // B
};

int get_note(const char* s)
{
  for (int i = 0; i < nr_notes; i++)
    if (!strcmp(s, notes[i]))
      return i;
  return -1;
}

int main()
{
  while (true) {
    const int nr_chars_max = 1000;
    char s[nr_chars_max + 1];
    gets(s);
    if (!strcmp(s, "END"))
      break;
    bool impossible_scales[nr_notes];
    memset(impossible_scales, 0, sizeof(impossible_scales));
    for (char *p = s, *q = s; *q; q = p) {
      for ( ; *p && !isspace(*p); p++)
        ;
      if (p - q) {
        if (*p) {
          *p++ = '\0';
          for ( ; *p && isspace(*p); p++)
            ;
        }
        int n = get_note(q);
        for (int i = 0; i < nr_notes; i++)
          if (!scales[i][n])
            impossible_scales[i] = true;
      }
    }
    bool printed = false;
    for (int i = 0; i < nr_notes; i++)
      if (!impossible_scales[i]) {
        if (printed)
          putchar(' ');
        else
          printed = true;
        printf("%s", notes[i]);
      }
    putchar('\n');
  }
  return 0;
}