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;
}

UVa 10912 - Simple Minded Hashing

Accepted date: 2014-01-15
Ranking (as of 2014-01-15): 257 out of 839
Language: C++

/*
  UVa 10912 - Simple Minded Hashing

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

#include <cstdio>

const int L_max = 26, S_max = 351;
int nsc[L_max + 1][S_max + 1][L_max + 1];
  // nsc[l][s][c] is the number of strings of length l, that maps to s 
  // and has a max value of c
int ns[L_max + 1][S_max + 1];
  // ns[l][s] is the number of strings of length l, that maps to s

int main()
{
  for (int s = 1; s <= L_max; s++)
    nsc[1][s][s] = 1;
  for (int l = 2; l <= L_max; l++)
    for (int s = 1; s <= S_max; s++)
      for (int c = 1; c <= L_max; c++)
        for (int i = 1; i < c; i++)
          nsc[l][s][c] += nsc[l - 1][s - c][i];
  for (int l = 1; l <= L_max; l++)
    for (int s = 1; s <= S_max; s++)
      for (int c = 1; c <= L_max; c++)
        ns[l][s] += nsc[l][s][c];

  for (int c = 1; ; c++) {
    int L, S;
    scanf("%d %d", &L, &S);
    if (!L && !S)
      break;
    printf("Case %d: %d\n", c,
      ((L > 0 && L <= L_max && S > 0 && S <= S_max) ? ns[L][S] : 0));
  }
  return 0;
}

UVa 741 - Burrows Wheeler Decoder

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

/*
  UVa 741 - Burrows Wheeler Decoder

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

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

int main()
{
  const int nr_chars_max = 300;
  char d[nr_chars_max + 1], s[nr_chars_max + 1], t[nr_chars_max + 1];
  bool printed = false;
  while (true) {
    int di;
    scanf("%s%d", d, &di);
    if (!strcmp(d, "END") && !di)
      break;
    if (printed)
      putchar('\n');
    di--;
    int length = strlen(d);
    strcpy(s, d);
    sort(s, s + length);
    t[0] = s[di];
#ifdef DEBUG
    printf("%c ", s[di]);
#endif
    int pi;
    for (pi = 0, di--; di >= 0 && s[di] == t[0]; di--)
      pi++;
    for (int ti = 1; ti < length; ti++) {
      for (di = 0; di < length; di++)
        if (d[di] == t[ti - 1]) {
          if (!pi--)
            break;
        }
      t[ti] = s[di];
#ifdef DEBUG
      printf("%c ", s[di]);
#endif
      for (pi = 0, di--; di >= 0 && s[di] == t[ti]; di--)
        pi++;
    }
    t[length] = '\0';
    printed = true;
    printf("%s\n", t);
  }
}

UVa 1260 - Sales

Accepted date: 2014-01-08
Ranking (as of 2014-01-08): 112 out of 600
Language: C++

/*
  UVa 1260 - Sales

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

#include <cstdio>

const int n_max = 1000;

int sales[n_max];

int main()
{
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
      scanf("%d", &sales[i]);
    int c = 0;
    for (int i = 1; i < n; i++)
      for (int j = 0; j < i; j++)
        if (sales[j] <= sales[i])
          c++;
    printf("%d\n", c);
  }
  return 0;
}

UVa 10325 - The Lottery

Accepted date: 2014-01-04
Ranking (as of 2014-01-04): 230 out of 654
Language: C++

/*
  UVa 10325 - The Lottery

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

#include <cstdio>

long long gcd(long long x, long long y)
{
  if (x < y)
    return gcd(y, x);
  else
      return y == 0 ? x : gcd(y, x % y);
}

long long lcm(long long x, long long y)
{
  long long l = x;
  return (l / gcd(x, y)) * y;
}

int main()
{
  const int m_max = 15;
  const int power_of_2s[m_max + 1] = { // power_of_2s[i] is 2^i
    1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768
  };
  int N, M;
  while (scanf("%d %d", &N, &M) != EOF) {
    int numbers[m_max];
    for (int m = 0; m < M; m++)
      scanf("%d", &numbers[m]);
    long long nr = N;
    for (int i = 1; i < power_of_2s[M]; i++) {
      int j = 0, k = 0;
      long long l;
      for (int b = 1; k < M; k++, b <<= 1)
        if (i & b) {
          j++;
          if (j > 1) {
            if ((l = lcm(l, numbers[k])) > N)
              break; // Since N doesn't have factors of l, 
                     // calculating the LCM any further isn't needed.
          }
          else
            l = numbers[k];
        }
      if (k == M) {
        if (j & 1)
          nr -= N / l;
        else
          nr += N / l;
      }
    }
    printf("%lld\n", nr);
  }
  return 0;
}

UVa 10527 - Persistent Numbers

Accepted date: 2014-01-04
Ranking (as of 2014-01-04): 372 out of 638
Language: JAVA

/*
  UVa 10527 - Persistent Numbers
*/

import java.util.Scanner;
import java.math.BigInteger;

class Main {
  static final BigInteger TWO = BigInteger.valueOf(2),
    THREE = BigInteger.valueOf(3),
    FIVE = BigInteger.valueOf(5), SEVEN = BigInteger.valueOf(7);

  public static void main(String[] args) {
    final BigInteger MINUSONE = BigInteger.valueOf(-1);
    int[] numberOfFactors = new int[9 - 0 + 1];
      // numberOfFactors[i] is the number of prime factors for i
      Scanner sc = new Scanner(System.in);
    while (true) {
      BigInteger n = sc.nextBigInteger();
      if (n.equals(MINUSONE))
        break;
      else if (n.equals(BigInteger.ZERO))
        System.out.println("10");
      else if (n.equals(BigInteger.ONE))
        System.out.println("11");
      else if (getNumberOfPrimeFactors(n, numberOfFactors)) {
        StringBuilder sb = new StringBuilder();
        while (true) {
          int d = getNextDidit(numberOfFactors);
          if (d == 0)
            break;
          sb.append((char)(d + '0'));
        }
        if (sb.length() == 1)
          sb.append('1');
        sb.reverse();
        System.out.println(sb);
      }
      else
        System.out.println("There is no such number.");
    }
  }

  static boolean getNumberOfPrimeFactors(BigInteger n, int[] numberOfFactors) {
    numberOfFactors[2] = numberOfFactors[3] =
    numberOfFactors[5] = numberOfFactors[7] = 0;
    while (n.mod(TWO).equals(BigInteger.ZERO)) {
      numberOfFactors[2]++;
      n = n.divide(TWO);
    }
    while (n.mod(THREE).equals(BigInteger.ZERO)) {
      numberOfFactors[3]++;
      n = n.divide(THREE);
    }
    while (n.mod(FIVE).equals(BigInteger.ZERO)) {
      numberOfFactors[5]++;
      n = n.divide(FIVE);
    }
    while (n.mod(SEVEN).equals(BigInteger.ZERO)) {
      numberOfFactors[7]++;
      n = n.divide(SEVEN);
    }
    return n.equals(BigInteger.ONE);
  }

  static int getNextDidit(int[] numberOfFactors) {
    if (numberOfFactors[3] >= 2) {
      numberOfFactors[3] -= 2; return 9;
    }
    else if (numberOfFactors[2] >= 3) {
      numberOfFactors[2] -= 3; return 8;
    }
    else if (numberOfFactors[7] != 0) {
      numberOfFactors[7]--; return 7;
    }
    else if (numberOfFactors[2] != 0 && numberOfFactors[3] != 0) {
      numberOfFactors[2]--; numberOfFactors[3]--; return 6;
    }
    else if (numberOfFactors[5] != 0) {
      numberOfFactors[5]--; return 5;
    }
    else if (numberOfFactors[2] >= 2) {
      numberOfFactors[2] -= 2; return 4;
    }
    else if (numberOfFactors[3] != 0) {
      numberOfFactors[3]--; return 3;
    }
    else if (numberOfFactors[2] != 0) {
      numberOfFactors[2]--; return 2;
    }
    else
      return 0;
  }
}

UVa 10856 - Recover Factorial

Accepted date: 2014-01-03
Ranking (as of 2014-01-03): 235 out of 686
Language: C++

/*
  UVa 10856 - Recover Factorial

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

#include <cstdio>
#include <cstdlib>
#ifdef __ELAPSED_TIME__
#include <ctime>
#endif

const int n_max = 2703663 /* 10000001 */;
int nr_pfs[n_max + 1];
  // nr_pfs[i] is the nmber of prime factors of i
int total_nr_pfs[n_max + 1];
  // total_nr_pfs[i] is the total number of prime factors up to i

int compare_int(const void* i, const void* j)
{
  return *reinterpret_cast<const int*>(i) - *reinterpret_cast<const int*>(j);
}

int main()
{
#ifdef __ELAPSED_TIME__
  clock_t start = clock();
#endif
  nr_pfs[2] = 1;
  for (long long i = 2; i * 2 <= n_max; i++)
    nr_pfs[i * 2] = nr_pfs[i] + 1;
  for (long long i = 3; i <= n_max; i += 2) {
    if (!nr_pfs[i])
      nr_pfs[i] = 1;
    for (long long j = 2; i * j <= n_max; j++)
      nr_pfs[i * j] = nr_pfs[i] + nr_pfs[j];
  }
  for (int i = 2; i <= n_max; i++) {
    total_nr_pfs[i] = total_nr_pfs[i - 1] + nr_pfs[i];
#ifdef DEBUG
    printf("%d: %d %d\n", i, nr_pfs[i], total_nr_pfs[i]);
#endif
  }
#ifdef DEBUG
  printf("%d\n", total_nr_pfs[n_max]);
#endif
#ifdef __ELAPSED_TIME__
  fprintf(stderr, "elapsed time = %lf sec.\n",
    static_cast<double>(clock() - start) / CLOCKS_PER_SEC);
#endif

  for (int tc = 1; ; tc++) {
    int n;
    scanf("%d", &n);
    if (n < 0)
      break;
    printf("Case %d: ", tc);
    int* pi = total_nr_pfs;
    if (n)
      pi = reinterpret_cast<int*>(
        bsearch(&n, total_nr_pfs, n_max + 1, sizeof(int), compare_int));
    if (pi)
      printf("%d!\n", pi - total_nr_pfs);
    else
      puts("Not possible.");
  }
  return 0;
}

UVa 10721 - Bar Codes

Accepted date: 2014-01-02
Ranking (as of 2014-01-02): 598 out of 1156
Language: C++

/*
  UVa 10721 - Bar Codes

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

#include <iostream>
using namespace std;

const int nkm_max = 50;
long long bc[nkm_max + 1][nkm_max + 1][nkm_max + 1];

int main()
{
  int n, k, m;
  for (n = 1; n <= nkm_max; n++)
    for (m = 1; m <= nkm_max; m++)
      if (n <= m)
        bc[n][1][m] = 1;
  for (n = 1; n <= nkm_max; n++)
    bc[n][n][1] = 1;
  for (k = 2; k <= nkm_max; k++)
    for (n = 2; n <= nkm_max; n++)
      for (m = 2; m <= nkm_max; m++)
        if (n >= k && n <= k * m) {
          if (n - k + 1 >= m)
            for (int i = 1; i <= m; i++)
              bc[n][k][m] += bc[n - i][k - 1][m];
          else
            bc[n][k][m] = bc[n][k][m - 1];
        }

  while (cin >> n >> k >> m)
    cout << bc[n][k][m] << endl;
  return 0;
}