奶牛 Bessie 最近在学习字符串操作，它用如下的规则逐一的构造出新的字符串：

喵喵字符串
描述

贡菊最近在学习字符串操作，它用如下的规则逐一的构造出新的字符串：

S(0)=mew

S(1)=S(0)+me+ww+S(0)=mew+me+ww+mew=mewmewwmew

S(2)=S(1)+me+www+S(1)=mewmwwmew+me+www+mewmewwmew=mewmewwmewmewwwmewmewwmew

……

贡菊通过这个规律产生字符串，直到最后产生的那个字符串长度不小于读入的整数 n 才停止。

请问第 n 个字母是什么？

输入
一个整数 n (1≤n≤100)

输出
第 n 个字母

输入样例 1

11
输出样例 1

m
求解不用递推

给出一种比较高效的解法：

#include <iostream>
#include <string>
using namespace std;

int main()
{
    int n;
    cin >> n;
    string s = "mew";
    for(int i=1; ; i++)
    {
        if(s.length() >= n)
        {
            cout << s[n - 1] << endl;
            return 0;
        }
        s = s + "me" + string(i + 1, 'w') + s;
    }
    return 0;
}

n = 100 时，输出 w，运行时间 17ms。

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7458308
• 除此之外, 这篇博客: C语言质数的简单判断和输出中的 题目1：对于给定的一个大于 1 的正整数 N（你可以认为测评机给出的 N 均小于 1000），按从小到大的顺序输出所有小于等于它的质数。输出格式请按从小到大的顺序输出所有小于等于 N 的质数，一个数单独占一行。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 2也是质数，不要遗忘

  #include <stdio.h>
  int prime(int x){
  	int i;
  	for(i=3;i*i<x;i+=2)
  		if(x%i==0)
  			return 0;
  	return 1;
  }
  int main() {
      int i;
      int j;
      int N;
      scanf("%d",&N);
      if(N>=2){
          printf("2\n");
      }
      for(i=3; i<=N; i+=2){
          if(prime(i)){
  			printf("%d\n",i);
  		}
      }
  
      return 0;
  }
  

#include <iostream>
#include <string>
using namespace std;

string S(int n)
{
    if (n == 0)
        return "mew";
    string w = "w";
    for (int i = 0; i < n; i++) 
        w = w + "w";
    return S(n - 1) + "me" + w + S(n - 1);
}

int main()
{
    int n;
    int i = 0;
    string s;
    cin >> n;
    while (1)
    {
        s = S(i++);
        if (s.length() >= n) break;
    }
    cout << s << endl;
    //cout << s.c_str()[n + 1];
    return 0;
}