Solution Notes: This problem has a nice recursive solution. We first write a recursive function to compute the length of S(k) (given by twice the length of S(k-1) plus the length of the middle section, k+3). Afterwards, we can figure out the nth chracter in S(k) by checking if n lies in the left copy of S(k-1) (in which case we can proceed by recursion), in the middle section, or in the right copy of S(k-1) (in which case we can again proceed by recursion).


#include <stdio.h>

/* Compute the length of S(k) */
int len(int k)
{
  int x;
  if (k==-1) return 0; 
  x = len(k-1);
  return x + k+3 + x;
}

/* Return nth character in S(k) */
char solve(int n, int k)
{
  if (n > len(k)) return solve(n,k+1);
  if (n <= len(k-1)) return solve(n,k-1);
  n = n - len(k-1); /* Discount S(k-1) from beginning of string */
  if (n <= k+3) /* n in middle section? */
    return (n==1) ? 'm' : 'o';
  n = n - (k+3);
  return solve(n,k-1); 
}

int main(void)
{
  int n;
  freopen ("moo.in", "r", stdin);
  freopen ("moo.out", "w", stdout);
  scanf ("%d", &n);
  printf ("%c\n", solve(n,0));
  return 0;
}