class Solution
{
public:
	string convert(string s, int numRows)
	{
		if (numRows == 1)
			return s;
		int len = s.size();
		if (len <= numRows)
			return s;
		int cycle_len = 2 * numRows - 2;
		int full_cycles = len / cycle_len;
		int left = len % cycle_len;
		string r;
		int i;
		for (i = 0; i < full_cycles; ++i)
		{
			r += s[i * cycle_len];
		}
		if (left)
			r += s[i * cycle_len];
		for (i = 0; i < numRows - 2; ++i)
		{
			int j;
			for (j = 0; j < full_cycles; ++j)
			{
				r += s[j * cycle_len + i + 1];
				r += s[j * cycle_len + i + 1 + cycle_len - 2 * (i + 1)];
			}
			if (left)
			{
				if (j * cycle_len + i + 1 < len)
					r += s[j * cycle_len + i + 1];
				if (j * cycle_len + i + 1 + cycle_len - 2 * (i + 1) < len)
					r += s[j * cycle_len + i + 1 + cycle_len - 2 * (i + 1)];
			}
		}
		for (i = 0; i < full_cycles; ++i)
			r += s[i * cycle_len + numRows - 1];
		if (left >= numRows)
			r += s[i * cycle_len + numRows - 1];
		return r;
	}
};